Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Help me please!

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
fissh

Joined: 08 Jun 2005
Posts: 2
:

Items
PostPosted: Wed Jun 08, 2005 11:54 am    Post subject: Help me please! Reply with quote

Hallo!

I generate the puzzle with: http://act365.com/sudoku/

Please help me with next hints (with explanation)

036|090|210
027|010|009
090|520|008

752|649|831
048|070|052
013|852|000

200|064|003
300|080|100
009|030|700


The solution is: (but I don't understand - no logic) record marked with ***

1. The value 5 in Box [3,1] must lie in Column 3.
The value 6 in Box [3,1] must lie in Column 2.
The value 8 in Box [3,1] must lie in Column 2.
The values 3, 6 and 7 occupy the cells (3,6), (3,7) and (3,8) in some order.
The value 4 in Box [1,1] must lie in Row 3.
The values 2 and 9 occupy the cells (8,4) and (8,8) in some order.
The cell (1,9) is one of 2 candidates for the value 4 in Row 1.
************************************************************
********* 2. The value 6 is the only candidate for the cell (2,8). ******
************************************************************
3. The value 7 is the only candidate for the cell (1,4).
4. The value 8 is the only candidate for the cell (1,6).
5. The value 3 is the only candidate for the cell (2,6).
6. The value 5 is the only candidate for the cell (2,7).
7. The value 9 is the only candidate for the cell (7,7).
8. The value 1 is the only candidate for the cell (7,4).
9. The value 6 is the only candidate for the cell (5,7).
10. The value 8 is the only candidate for the cell (7,8).
11. The value 2 is the only candidate for the cell (8,8).
12. The value 5 is the only candidate for the cell (9,6).
13. The value 4 is the only candidate for the cell (9,8).
Back to top
View user's profile Send private message
MadOverlord

Joined: 01 Jun 2005
Posts: 80
:
Location: Wilmington, NC, USA

Items
PostPosted: Thu Jun 09, 2005 12:11 am    Post subject: Re: Help me please! Reply with quote

The statements up to the leap of faith are true. At that point, you have to do a forcing chain to solve the problem.

A forcing chain is close to recursion, and for some problems it can be so exhaustive that it might as well be, but it can be done by human beings with some breadcrumb to note squares.

It works like this:

Pick a square that has only two values, call them <AB>. Assume the square is <A>. Then look for a squares of format <AC>.

Example: the square has possibilities <12>. You choose <1>. If you can find a square in the row/col/block that is <1x>, you know it must be a <x>.

If you don't find an <AC> square, look to see if there's only one other square that can contain <B>. If so, your choice of <A> has "pinned" it as <B>.

Example: the square has possibilities <12>. You choose <1>. If there's only one other square in the r/c/b that can hold a <2>, you know it must be that.

If you don't follow pinned squares, then you're doing the algorithm I call Simple Forced Chain; that won't solve this problem.

Drop a breadcrumb on the new square you've just found and set a value for, and repeat the process. You're not crossing off possibilities as you go, just using the ones you had when you started the algorithm.

The idea is to wander around the board until you get back to your original start square. If you do so, and the value you force into that square is not the one you started with, you've got an inconsistancy, and you know your original guess was WRONG. You can now cross that guess off the possibilities and proceed.

It should be stated that I think the Simple Forced Chain algorithm is right at the limit of what is reasonable to expect human players to be able to reasonable "execute". Pinned Chains is probably over that line, and on some puzzles it takes long enough to execute that it's clearly equivalent to recursion.

Okay, if you run the algorithm past your problem, what you get is:

Code:

Deduction pass 1; 42 squares solved; 39 remaining.

 Rule 3 : 2 squares in row 3 form a simple locked pair.
  The following squares share possibilities <14>:

   R3C1
   R3C3

  Thus, possibilities <14> can be removed from
  the rest of the row.

   R1C7 - removing <4> from <346> leaving <36>.
   R1C8 - removing <4> from <467> leaving <67>.

Deduction pass 2; 42 squares solved; 39 remaining.

 Rule 3 : 2 squares in column 1 form a simple locked pair.
  The following squares share possibilities <69>:

   R5C1
   R6C1

  Thus, possibilities <69> can be removed from
  the rest of the column.

   R1C9 - removing <6> from <14568> leaving <1458>.

Deduction pass 3; 42 squares solved; 39 remaining.

 Rule 3 : 2 squares in block 1 form a simple locked pair.
  The following squares share possibilities <14>:

   R3C1
   R3C3

  Thus, possibilities <14> can be removed from
  the rest of the block.

   R1C1 - removing <4> from <458> leaving <58>.
   R1C4 - removing <4> from <458> leaving <58>.

Deduction pass 4; 42 squares solved; 39 remaining.

 Rule 3 : 2 squares in column 1 form a simple locked pair.
  The following squares share possibilities <58>:

   R1C1
   R2C1

  Thus, possibilities <58> can be removed from
  the rest of the column.

   R1C9 - removing <5> from <1458> leaving <148>.
   R1C9 - removing <8> from <1458> leaving <145>.

Deduction pass 5; 42 squares solved; 39 remaining.

 Rule 3 : 2 squares in column 1 form a simple locked pair.
  The following squares share possibilities <58>:

   R1C1
   R2C1

  Thus, possibilities <58> can be removed from
  the rest of the column.

   R1C9 - removing <5> from <145> leaving <14>.

Deduction pass 6; 42 squares solved; 39 remaining.

 Rule 4 : A set of 2 squares can be constrained.
  The following squares share possibilities <29>:

   R8C4
   R8C8

  No other squares in row 8 have those
  possibilities.  Thus, any additional possibilties
  they have can be eliminated.

   R8C4 - removing <7> from <279> leaving <29>.
   R8C8 - removing <46> from <2469> leaving <29>.

Deduction pass 7; 42 squares solved; 39 remaining.

 Rule 10 : Found a pinned chain.  If we assume that
  square R3C1 is <1> then we can make the
  following chain of conclusions:

   R3C3 must be <4>, which means that
   R8C3 must be <5>, which means that
   R8C6 must be <7>, which means that
   R1C6 must be <8>, which means that
   R1C1 must be <5>, which means that
   R2C1 must be <8>, which means that
   R2C7 is pinned to <5>, which means that
   R7C7 must be <9>, which means that
   R7C3 is pinned to <5>, which means that
   R9C1 is pinned to <1>, which means that
   R3C1 must be <4>.

  Since this is logically inconsistent,
  R3C1 cannot be <1>.

 Reconstraining R3C3 fixes its value at <1>.
 Reconstraining R9C1 fixes its value at <1>.
 Reconstraining R7C3 fixes its value at <5>.
 Reconstraining R8C3 fixes its value at <4>.
 Reconstraining R7C7 fixes its value at <9>.
 Reconstraining R7C8 fixes its value at <8>.
 Reconstraining R8C8 fixes its value at <2>.
 Reconstraining R5C7 fixes its value at <6>.
 Reconstraining R7C2 fixes its value at <7>.
 Reconstraining R8C4 fixes its value at <9>.
 Reconstraining R9C4 fixes its value at <2>.
 Reconstraining R9C6 fixes its value at <5>.
 Reconstraining R8C6 fixes its value at <7>.

 Reconstraining R5C1 fixes its value at <9>.
 Reconstraining R3C7 fixes its value at <3>.
 Reconstraining R6C7 fixes its value at <4>.
 Reconstraining R6C9 fixes its value at <7>.
 Reconstraining R6C8 fixes its value at <9>.
 Reconstraining R7C4 fixes its value at <1>.
 Reconstraining R8C2 fixes its value at <6>.
 Reconstraining R5C4 fixes its value at <3>.
 Reconstraining R9C2 fixes its value at <8>.
 Reconstraining R8C9 fixes its value at <5>.
 Reconstraining R1C6 fixes its value at <8>.
 Reconstraining R1C9 fixes its value at <4>.

 Reconstraining R1C1 fixes its value at <5>.
 Reconstraining R1C4 fixes its value at <7>.
 Reconstraining R2C8 fixes its value at <6>.
 Reconstraining R9C9 fixes its value at <6>.
 Reconstraining R3C8 fixes its value at <7>.
 Reconstraining R2C6 fixes its value at <3>.
 Reconstraining R9C8 fixes its value at <4>.
 Reconstraining R2C7 fixes its value at <5>.
 Reconstraining R3C6 fixes its value at <6>.
 Reconstraining R6C1 fixes its value at <6>.
 Reconstraining R2C4 fixes its value at <4>.
 Reconstraining R5C6 fixes its value at <1>.

 Reconstraining R2C1 fixes its value at <8>.

Deduction pass 8; 81 squares solved; 0 remaining.
Back to top
View user's profile Send private message Visit poster's website AIM Address
Simes

Joined: 08 Apr 2005
Posts: 71
:
Location: North Yorkshire, UK

Items
PostPosted: Thu Jun 09, 2005 11:15 am    Post subject: Reply with quote

For any lurkers, this thread is repeated on another forum http://www.sudoku.com/forums/viewtopic.php?p=2640

Simes
_________________
Simes
www.sadmansoftware.com/sudoku
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron