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]
