|
View previous topic :: View next topic |
Author |
Message |
| fissh
| Joined: 08 Jun 2005 | Posts: 2 | : | | Items |
|
Posted: Wed Jun 08, 2005 11:54 am Post subject: Help me please! |
|
|
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 |
|
|
| MadOverlord
| Joined: 01 Jun 2005 | Posts: 80 | : | Location: Wilmington, NC, USA | Items |
|
Posted: Thu Jun 09, 2005 12:11 am Post subject: Re: Help me please! |
|
|
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 |
|
|
| Simes
| Joined: 08 Apr 2005 | Posts: 71 | : | Location: North Yorkshire, UK | Items |
|
|
Back to top |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|