The New Sudoku Players' Forum

[Carcul]

Hi Tso.

Here is a possible solution for puzzle #2:

1. [r9c3]-7-[r9c6]-4-[r3c6]=4=[r3c9]=9=[r4c9]-9-[r4c7]-2-[r4c3]-7-[r9c3], => r9c3<>7.

2. [r9c6]-4-[r3c6]=4=[r3c9]=3=[r9c9]-3-[r9c3]-4-[r9c6], => r9c6<>4.

3. [r7c1|r8c1](-8-[r9c2]-3-[r9c9])-8-[r1c1|r3c1|r3c3]-2,3,9-[r2c3]-6-[r6c3]=6=[r5c2]=3=[r5c1]-3-[r1c1|r3c1]-2,9-[r3c3]-3-[r3c9], => r7c1,r8c1<>8.

(this is a "grouped" single implication network: if r7c1 or r8c1 is "8", then column 9 would have no "3").

4. [r2c3]=6=[r6c3]-6-[r5c2]=6=[r5c9]=4=[r5c8]-4-[r1c8|r2c8]-8-[r2c6|r2c7]-3,9-[r2c3], => r2c3<>3,9.

5. [r1c1|r3c1]-9-[r3c3]=9=[r8c3]=4=[r9c3]=3=[r9c9]=5=[r8c8]=7=[r7c8]-7-[r7c1]-9-[r1c1|r3c1], => r1c1,r3c1<>9 and that solve the puzzle.

Regards, Carcul

[aeb]

Hmm. In my opinion POM is a technique for solving POM puzzles. One uses backtrack/recursion/trial-and-error to go from a given Sudoku puzzle to the start of the corresponding POM puzzle. Sometimes a difficult Sudoku puzzle is already solved by doing this backtrack that produces the possible number patterns, and no further POM work is required.

Hi Aeb, Your statement puzzles me as I have no idea what a 'POM puzzle' is. Further, even with my limited knowledge, I know POM doesn't use backtrack, recursion and trial-and-error.

Hmm - I keep pointing you at this website - look at the two pages
http://homepages.cwi.nl/~aeb/games/sudoku/solving23.html
http://homepages.cwi.nl/~aeb/games/sudoku/solving24.html
What is a Sudoku puzzle? You know.
What is a POM puzzle? I think you know, but just to be sure: a POM puzzle is a jigsaw puzzle - you are give a number of jigsaw pieces labeled 1, a number of pieces labeled 2, etc. Your job is to find 9 pieces with labels 1-9 that fit together and form a 9x9 square.
How does one go from a Sudoku puzzle to a POM puzzle? I think you know, but just to be sure: one enumerates all possible patterns for each of the 9 digits. This process involves recursion, although it may be a short recursion in easy cases.
The second page quoted above shows a somewhat difficult Sudoku that is already solved by giving the digit patterns - the fact that some digits cannot be in some places suffices, afterwards one uses singles only. This demonstrates that the starting point of the POM techniques is not the Sudoku puzzle, but the Sudoku puzzle plus knowledge of the digit patterns. And obtaining all possible patterns is essentially backtrack / recursion / trial-and-error.

[Wolfgang]

Hi Carcul,

The paranthesis denote ramifications of the "main" implication stream, or, more exactly, multiple implications...

I have still problems to read the loops. As an example, loop 2 for puzzle 6 says

[r7c1]=2=[r1c1]-2-[r1c5]=2=[r2c4]{-2-[r8c4](-3-[r8c78]-5-[r9c9])-3-[r7c4]-1-[r7c1|r7c3]}-2-[r2c9]-9-[r9c9]-8-[r9c3](-3-[r7c1])-3-[r7c3]-7-[r6c3]-1-[r6c1]-5-[r7c1], => r7c1<>1,3,5 => r7c1=2.

Please can you explain in words, what happens in parentheses here:
-2-[r8c4](-3-[r8c78]-5-[r9c9])-3-[r7c4] ?

btw i cannot follow [sorry/typo:] aeb's deduction too, there seem some things missing..

[Jeff]

Hmm - I keep pointing you at this website - look at the two pages

Hi Aeb, MJ is the originator of POM and I have been following its development from day 1, started from another forum, and I know exactly how it works. I did visit the web sites you recommended and read your articles, but whether I did or not, it should affect my opinion.

How does one go from a Sudoku puzzle to a POM puzzle? I think you know, but just to be sure: one enumerates all possible patterns for each of the 9 digits. This process involves recursion, although it may be a short recursion in easy cases............... This demonstrates that the starting point of the POM techniques is not the Sudoku puzzle, but the Sudoku puzzle plus knowledge of the digit patterns. And obtaining all possible patterns is essentially backtrack / recursion / trial-and-error.

Sorry, I don't know how to go from a Sudoku puzzle to a POM puzzle until you spelled it out. This is your own idea which is not published before. I always think that identifying all possible solution patterns is part of POM, and I still do. MJ didn't specifically demarcate these processes in his description, and he is the originator of the technique. To me, identifying solution patterns is a systematic process; it may be tedious, but definitely not backtrack, recursion and/or trial-and-error.

[Carcul]

Hi Tso.

Here is a possible solution for puzzle #1 (I apologize for the complicated steps 8 and 9, but, for the moment, I cannot spot a simpler solution):

1. [r7c9]=5=[r7c1]-5-[r8c1|r7c2|r8c2|r9c2]-1-[r8c3]-8-[r8c8|r8c9]=8=[r7c9], => r7c9<>1,3,9; r7c3, r9c3<>1.

2. [r1c8]=5=[r1c9]-5-[r7c9]-8-[r7c3]-2-[r7c4]=2=[r1c4]-2-[r1c8], => r1c8<>2.

3. [r1c8]=5=[r1c9]-5-[r7c9]=5=[r7c1]=3=[r7c7]-3-[r9c8]-7-[r1c8], => r1c8<>7.

4. [r8c2]=4=[r7c2]-4-[r7c4]-2-[r7c3]-8-[r8c3]-1-[r8c2], => r8c2<>1.

5. [r8c9]=1=[r8c3]=8=[r7c3]-8-[r7c9]-5-[r8c9], => r8c9<>5.

6. [r1c9]=5=[r7c9]=8=[r7c3]-8-[r8c3]-1-[r3c3]=1=[r2c2]=8=[r1c2]-8-[r1c9], => r1c9<>8.

7. [r2c2]=8=[r1c2]-8-[r1c8]-5-[r1c9]=5=[r7c9]=8=[r7c3]-8-[r8c3]-1-[r3c3]=1=[r2c2], => r2c2<>9.

8. [r3c8](-7-[r1c7|r1c9|r3c7])-7-[r9c8](-3-[r7c7])-3-[r9c1]=3=[r7c1]=5=[r7c9]-5-[r1c9](=5=[r1c8]=8=[r1c2]-8-[r2c2]-1-[r7c2])(-9-[r3c7])-9-[r1c7](-6-[r3c7]: r3c7=1)-6-[r1c4]-2-[r7c4]-4-[r7c2]-9-[r7c7](r7c7=1), => r3c8<>7.

9. [r2c8]{=2=[r3c8](-2-[r3c3])-2-[r3c6]-9-[r9c6]}{(-8-[r8c8])-8-[r1c8]-5-[r8c8]-7-[r9c8]-3-[r7c7|r9c9]}-8-[r2c2](-1-[r2c7])-1-[r3c3]-6-[r9c3]-2-[r9c6]-1-[r9c9]-9-[r7c7]-1-[r3c7]=1=[r3c9]=4=[r3c8]=2=[r2c8], => r2c8<>8.

10. [r8c2]=7=[r1c2]=8=[r2c2]=1=[r3c3]-1-[r8c3]-8-[r7c3]-2-[r7c4]-4-[r8c4]=4=[r8c2],
=> r1c2<>9, r7c1<>2, r7c6<>2, r8c2<>9.

11. (a) [r7c2]=4|2=[r9c6]-2-[r3c6]-9-[r7c6]-1-[r7c2], => r7c2<>1
(b) [r9c6]=2|4=[r7c2]=9=[r9c2]-9-[r9c6], => r9c6<>9.

12. [r7c7]=3=[r7c1]-3-[r9c1|r9c3]-2-[r9c6]-1-[r7c6]-9-[r7c7], r7c7<>9.

13. [r3c7]-9-[r1c7]=9=[r1c1]=2=[r1c4]-2-[r3c6]-9-[r3c7], => r3c7<>9.

14. [r3c1]=7=[r8c1]-7-[r8c2]-4-[r8c4]-6-[r8c5]-9-[r7c6]=9=[r3c6]-9-[r3c1], => r3c1<>9 and that solve the puzzle.

Tso, thank you for these very interesting and chalenging puzzles.

Regards, Carcul

[Carcul]

Hi Wolfgang.

Please can you explain in words, what happens in parentheses here: -2-[r8c4](-3-[r8c78]-5-[r9c9])-3-[r7c4] ?

The "-2-[r8c4]" makes r8c4=3: on one hand, this makes r7c4=1 eliminating "1" from r7c1 (and from r7c3); on the other hand, this eliminates "3" from the almost locked set r8c7/r8c8 which in turn eliminates "5" from r9c9 (thus "preparing" this node for the main implication stream).

Regards, Carcul

[aeb]

I always think that identifying all possible solution patterns is part of POM, and I still do. To me, identifying solution patterns is a systematic process; it may be tedious, but definitely not backtrack, recursion and/or trial-and-error.

As you wish. Don't forget that also recursion is a systematic process. What you do is: pick a digit d in row 1 in all possible ways; for each of the possible choices, pick a digit d in row 2 that does not conflict with that in row 1; for each of the possible choices in rows 1,2 pick ... You can program that as recursion, as backtrack along the tree of partial transversals, as a 9-fold nested for-loop, whatever.
It is impossible to fight over this question for 9x9 Sudoku since all is finite.
One could for example also solve Sudokus by simple inspection of the list of all 6670903752021072936960 possible completed Sudokus to see which one is the right one. That may be tedious, but definitely not backtrack, recursion and/or trial-and-error. If on the other hand one views this POM technique on 9x9 Sudoku as the special case of the POM technique for NxN Sudoku, then recursion / backtrack is definitely required to find all possible digit patterns. And for N=9 one uses recursion to depth 9.

[Graeme]

Harvard wrote:

I can't follow your solver, and it looks to me as it has a wrong xy-wing in your deduction.

Absoultely right, thanks Harvard. The line: "XY-Wing (using cells D7, E8 & G7) removed candidate {3} from cell D7" is obvious rubbish. I added XYZ-wing to by XY-Wing about a week ago, and inadvertently bypassed the test to prevent the 3 cells involved being a=XY, b=XZ and c=XW. Consequently the common candidate between cells b and c (X) was removed from intersecting cells, including cell a!.

All fixed now, and yes, XY-Wing is no longer part of the solution.

regards,
Graeme

[Wolfgang]

..almost locked set r8c7/r8c8 ..

Thanks, i missed that from step 1 follows that r8c3=9 and r8c7<>9.

[Jeff]

Hi Aeb, Thanks for you explanation. Based on your explanation, I can understand your interpretation on 'recursion' and 'backtrack'. In that sense, I do agree with you that 'recursion' and 'backtrack' can apply to POM as they also apply to all other solving techniques from hidden single to forcing chains to a considerable extent.

I am looking forward to your explanation on how 'trial & error' relates to POM?

[aeb]

Hi Aeb, Thanks for you explanation. Based on your explanation, I can understand your interpretation on 'recursion' and 'backtrack'. In that sense, I do agree with you that 'recursion' and 'backtrack' can apply to POM as they also apply to all other solving techniques from hidden single to forcing chains to a considerable extent.

I disagree. The reason that people are not entirely happy with recursion is that deep recursion on a branching tree will visit an exponential number of nodes, something that is not easy to do for a human. And even if is is doable, it is certainly not fun. In order to check that something is a hidden single I have to check the cells in the same row/column/box, that is 20 cells. In order to check that a given list of digit patterns is complete you have to check thousands of patterns. That is the result of the 9 deep recursion. For example, the example I gave, that is magically solved once you assume the digit patterns given, has 2184 patterns for the digit 9. Writing down these patterns is a long and boring procedure, much longer and much more boring than solving the sudoku by backtrack.

I am looking forward to your explanation on how 'trial & error' relates to POM?

Let me withdraw this phrase in this context.

[Jeff]

Based on your explanation, I can understand your interpretation on 'recursion' and 'backtrack'. In that sense, I do agree with you that 'recursion' and 'backtrack' can apply to POM as they also apply to all other solving techniques from hidden single to forcing chains to a considerable extent.

I disagree. The reason that people are not entirely happy with recursion is that deep recursion on a branching tree will visit an exponential number of nodes, something that is not easy to do for a human.

Hi Aeb, Thanks for your patience again. Now I know what you are talking about. You are relating not just 'recursion', but 'deep recursion' with POM. In this case, I am not qualified to pass any judgment since I am not familiar with 'deep recursion'. My simple mind simply treats all kinds of recursions as 'recursion' and if a recursion can be done by hand, then it cannot be all that bad. So, you are saying that for a difficult grid, the kind of POM recursion involved would be a 'deep recursion' and this would be beyond human ability. I can certainly relate to that.

[Carcul]

Hi Tso.

Here is an alternative solution for puzzle #4 (without eliminating the "3" from r2c5):

[r5c9]-3-[r7c9]-9-[r9c7]-3-[r9c5]-2-[r9c6]-5-[r9c1]-9-[r4c1]-1-[r5c3|r6c3]-6,9-[r5c4]=6=[r5c3]-6-[r6c3]-9-[r6c4]=9=[r3c4]=2=[r5c4]-2-[r5c8]-3-[r5c9], => r5c9<>3 which solve the puzzle (paying attention to the X-Wing on "9" that emerges).

Regards, Carcul