## Solver problems

Programs which generate, solve, and analyze Sudoku puzzles
I too have encountered puzzles that I am only able to solve by trial & error.

I have been playing Sudoku for a few months now, and early on I decided to write a computer program for either checking my results, or determining the solution if I got stuck. I started with just two rules, and gradually added more, to the current state of five rules; however, I have encountered five puzzles that are unsolvable by this rule set.

I just started reading this forum, and I'm not sure if my rules correspond to any of the techniques listed on the forum, but I am curious if the BUG technique is what I'm missing in my rule set. I am currently trying to understand the technique, to see if I can apply it as a computer rule, but in the meantime, I thought I'd share the basic approach of the program and the five puzzles that result in incomplete solutions, in case anyone can confirm whether or not I am missing techniques which will solve the puzzles.

Cheers,
Ed

Computer rules:
1. For each empty cell, create a list of numbers not already in the row, column or box of that cell. If the list results in only one number, mark the cell as solved, add that number to the row, column and box lists of used numbers, and remove that number from the list of possible numbers for all other unsolved cells.
2. For each empty cell, merge the lists of used numbers from the row, column and box of that cell. If the resulting list contains one less that the total numbers in the puzzle, then there is a unique solution for this cell. Mark the cell as solved, add that number to the row, column and box lists of used numbers, and remove that number from the list of possible numbers for all other unsolved cells.
3. For each possible number, test every row, column and box to see if that number is unused and only a possibility in a single cell. If so, mark the cell as solved, add that number to the row, column and box lists of used numbers, and remove that number from the list of possible numbers for all other unsolved cells.
4. For each box, check all unused numbers to see if the number can only exist in a single row or column of the box. If so, remove that number as a possibility from all other empty cells in same row or column of the other two boxes that share that row or column
5. This last rule, which I call "Remove false possibilities", is a mini trial and error. Identify all the empty cells in each row, cell and box. Loop through the cells for each of the above. On each loop, loop through the possible numbers for the current cell. Assert the current number as the solution. If that assertion causes any of the other cells to result in an empty possibilities set, then the assertion is false and that number should be removed from the set of possibilities for that cell.

Restart at step one, as long as some progress was made in any of the five steps; otherwise, quit as unsolved.

Below are five puzzles declared unsolvable by the above rules.

Puzzle, Newark Star-Ledger, 2005-12-28:
Code: Select all
`7   _   6      3   _   _      5   _   4      _   _   4      _   6   _      _   _   8      _   _   8      _   2   _      _   _   3      _   _   3      6   _   _      _   4   _      _   9   _      _   _   _      _   3   _      _   _   _      _   _   4      1   -   _      _   _   _      _   1   _      7   _   _      8   _   _      _   5   _      4   _   _      1   _   7      _   _   8      3   _   9   `

Computer generated solution:
Code: Select all
`7   [21]   6      3   8   9      5   [21]   4      [2935]   [235]   4      1   6   [75]      [29]   [27]   8      [95]   [15]   8      4   2   [75]      [96]   [617]   3      [25]   [87]   3      6   9   1      [28]   4   [275]      4   9   1      [85]   7   2      [86]   3   [65]      6   [87]   [25]      [85]   3   4      1   9   [275]      [235]   4   [25]      9   1   [63]      7   8   [26]      8   [23]   9      7   5   [63]      4   [26]   1      1   6   7      2   4   8      3   5   9   `

Puzzle, Newark Star-Ledger, 2005-12-09:
Code: Select all
`_   _   _      _   7   _      _   _   4      _   _   _      _   4   _      3   2   8      _   _   _      _   _   8      _   9   _      1   _   6      _   _   -      _   5   _      7   _   _      _   3   _      _   _   9      _   5   _      _   _   _      8   _   2      _   8   _      2   _   _      _   _   _      5   6   1      _   8   _      _   _   _      3   _   _      _   6   _      _   _   _      `

Computer generated solution:
Code: Select all
`8   [913]   [935]      [963]   7   2      [615]   [61]   4      6   [917]   [975]      [915]   4   [915]      3   2   8      2   [413]   [435]      [63]   [15]   8      7   9   [615]      1   [93]   6      8   2   [97]      4   5   [37]      7   2   8      [45]   3   [45]      [61]   [61]   9      [49]   5   [493]      [917]   [91]   6      8   [37]   2      [49]   8   [497]      2   [915]   [491375]   [9615]   [437]   [615]      5   6   1      [497]   8   [4937]      2   [437]   [37]      3   [497]   2      [49175]   6   [49175]      [915]   8   [15]      `

Puzzle, Newark Star-Ledger, 2005-11-18:
Code: Select all
`_   _   1      7   _   9      _   _   _      _   7   _      _   3   _      _   _   _      5   _   _      _   _   1      _   7   _      3   2   _      _   9   _      _   _   _      _   1   4      _   _   _      5   2   _      _   _   _      _   5   _      _   1   8      _   6   _      8   _   _      _   _   5      _   _   _      _   7   _      _   8   _      _   _   _      9   _   2      1   _   _      `

Computer generated solution:
Code: Select all
`[24]   [483]   1      7   [28]   9      6   5   [243]      [249]   7   [296]      [465]   3   [65]      8   [49]   1      5   [483]   [2963]      [46]   [28]   1      [29]   7   [243]      3   2   5      1   9   8      4   6   7      8   1   4      3   6   7      5   2   9      6   9   7      2   5   4      3   1   8      [249]   6   [29]      8   1   3      7   [49]   5      1   [43]   [93]      [65]   7   [65]      [29]   8   [24]      7   5   8      9   4   2      1   3   6      `

Puzzle, Newark Star-Ledger, 2005-11-09:
Code: Select all
`_   3   _      _   _   _      _   _   4      _   2   _      _   _   _      7   _   5      _   _   5      _   4   1      2   _   8      _   _   1      9   7   _      _   _   _      _   _   _      _   _   _      _   _   _      _   _   _      _   2   8      3   _   _      3   _   4      5   6   _      8   _   _      5   _   2      _   _   _      _   4   _      9   _   _      _   _   _      _   7   _      `

Computer generated solution:
Code: Select all
`1   3   7      [28]   [85]   [25]      [96]   [96]   4      4   2   8      [63]   [93]   [96]      7   1   5      6   9   5      7   4   1      2   3   8      [28]   [65]   1      9   7   3      4   [2865]   [26]      [28]   [46]   3      [461]   [15]   [465]      [91]   [298]   7      7   [465]   9      [461]   2   8      3   [65]   [61]      3   [17]   4      5   6   [297]      8   [29]   [291]      5   [817]   2      [813]   [9813]   [97]      [961]   4   [9613]      9   [81]   6      [24813]   [813]   [24]      5   7   [213]      `

Puzzle, Newark Star-Ledger, 2005-10-09:
Code: Select all
`_   1   7      _   _   _      3   _   _      3   _   _      5   _   _      _   4   _      _   _   _      _   9   _      _   _   2      _   3   _      _   1   _      8   _   _      _   8   _      _   6   _      _   9   _      _   _   2      _   5   _      _   1   _      9   _   _      _   7   _      _   _   _      _   5   _      _   _   2      _   _   4      _   _   8      _   _   _      5   6   _      `

Computer generated solution:
Code: Select all
`[285]   1   7      [48]   [248]   6      3   [85]   9      3   [29]   [96]      5   [28]   [17]      [617]   4   [8617]      [4865]   [46]   [465]      [137]   9   [137]      [617]   [875]   2      [4675]   3   [4965]      [2497]   1   [497]      8   [27]   [675]      [4175]   8   [415]      [2437]   6   [437]      [247]   9   [375]      [467]   [97]   2      [4937]   5   8      [467]   1   [637]      9   [46]   [4613]      [48613]   7   5      [21]   [283]   [81]      [617]   5   [613]      [8613]   [83]   2      9   [837]   4      [2417]   [27]   8      [4913]   [43]   [4913]      5   6   [17]`
eguy

Posts: 2
Joined: 29 December 2005

The Techniques experienced Sudoku solvers use to solve these puzzles are explained in detail at the links below.

Simple Sudoku

All Sudoku Puzzles (from pappocom) have the property that they can be solved by logic alone, and have a unique solution.

once you are up to speed on these techniques, you shouldn't find it very difficult to complete these puzzles.

For the first puzzle i can see a X-Wing in 2
Crazy Girl

Posts: 189
Joined: 08 November 2005

Don't worry about BUG just yet. No advanced tactics are needed for any of the five puzzles you posted. You are unlikely to get to the point where you can apply BUG until you've mastered the intermediate patterns.
tso

Posts: 798
Joined: 22 June 2005

Crazy Girl wrote:The Techniques experienced Sudoku solvers use to solve these puzzles are explained in detail at the links below.

Simple Sudoku

All Sudoku Puzzles (from pappocom) have the property that they can be solved by logic alone, and have a unique solution.

once you are up to speed on these techniques, you shouldn't find it very difficult to complete these puzzles.

For the first puzzle i can see a X-Wing in 2

Thanks for the links. I added X-Wing to my programming rules, and that solved three out of the five previously "unsolvable" puzzles. I'm checking out the remaining techniques now.

Cheers,
Ed
eguy

Posts: 2
Joined: 29 December 2005