The Advertiser, great newspaper as it is (that was sarcasm) has been plugging Sudoku puzzles of late. For the uninitiated, a sudoku puzzle is a 9×9 grid, that is broken up into 9 smaller 3×3 squares.
Each row, column, and 3×3 grid contains all of the digits 1-9, and (obviously) each row, column and small grid contains each digit only once. The trick is to work out which ones go where.
It’s all about logic, and working out which digits will not fit. So, I thought I would write a small python program to do it. I was prompted to do this by a puzzle I was working on on the way home, and I thought to myself “this puzzle appears to not have enough information for me to continue”. So, I started marking 9 marks in each box, showing which values could fit and not fit into each box. This was time consuming, but should be easy enough to do programmatically.
Once you have this down, it’s simple to see if there are any boxes where only one value can go, or any rows, columns or squares where there is only once slot a particular digit can fit. And my program did just this. (I actually made an object-oriented one, that uses classes for cells, and puzzles, and methods for checking rows, columns, squares, etc).
But, I seem to be missing one logical leap. The first puzzle I tried got solved with a few iterations of my program, but the other two I brought home get stuck. And one of these was one I solved earlier today, so I cannot recall how I was able to make the leap of logic my program cannot.
The missing logical leap:
If a row contains 2 cells that have 2 possible answers, and the answers are the same for both cells, then those two numbers cannot appear anywhere else on that row. For instance if both cells could be 5 or 8 (if one is 5 then the other is 8 ), then there cannot be another 5 or 8 in that row. Similarly for each column, and for each 3×3 block.
Similarly, if there are 3 cells in a set with the same 3 possible answers, then no other cell in that set can contain any of those possible answers.
3 weeks, 1 day after the fact.
Excellent!
This might be a little harder to implement than it is to explain, however.
3 weeks, 1 day after the fact.
Also, the above logical requirement also holds true (obviously) for each 3×3 grid.
4 weeks, 1 day after the fact.
I’ve written a Visual Basic program to test that theory (in Microsoft Excel, version XP - would be happy to send it to you ), and found a few more “logical leaps” are needed.
The first is an variation of the original thought I offered :
If a set (a row or a column or a 3×3 block) contains 2 numbers as possible answers in 2 cells (even if there are other possible numbers in those 2 cells), and if those are the only 2 cells where those numbers can occur, then each of those 2 cells must contain one of the 2 numbers, and no other number is correct in either of those 2 cells.
Similarly for 3 numbers in 3 cells, and 4 in 4, and so on.
Example: one cell is 1 or 5 or 8 ;
another cell is 2 or 5 or 8 ;
numbers 5 and 8 have been eliminated from all the other cells in that set.
And even with that logic (done manually, befcause I haven’t got around to programming it yet) I’ve found a puzzle that cannot be solved using just those rules, so there must be another logical leap. The only way I could finish it was to work as far as possible using logic, then make a guess, then check if that led to a solution or to a contradiction. Here’s the puzzle.
? 9 ? ? ? 4 ? ? 7
? ? ? ? ? 7 9 ? ?
8 ? ? ? ? ? ? ? ?
4 ? 5 8 ? ? ? ? ?
3 ? ? ? ? ? ? ? 2
? ? ? ? ? 9 7 ? 6
? ? ? ? ? ? ? ? 4
? ? 3 5 ? ? ? ? ?
2 ? ? 6 ? ? ? 8 ?
The logic can process as far as this :
? 9 ? ? 8 4 ? ? 7
? ? ? ? ? 7 9 ? 8
8 ? 7 ? ? ? ? ? ?
4 ? 5 8 ? ? ? ? ?
3 ? 9 ? ? ? 8 ? 2
1 ? ? ? ? 9 7 ? 6
? ? 6 ? ? ? ? ? 4
? ? 3 5 ? ? ? ? ?
2 ? ? 6 ? ? ? 8 ?
I can post the solution if you’d like.
1 month after the fact.
Some puzzles cannot be solved via logic alone - they require ‘testing’ a value (or pair of values) and seeing if that value will result in a contradiction. If there is a contradiction, try another value (or swap the values).
Ths would require more in my program that I have allowed for. I have not capability to say ‘test mode, remember what these values look like’, but it should be easy enough to do: just use a copy of the data.
I too haven’t gotten around to programming my 2/2,3/3 etc logic.
I wouldn’t mind seeing your program - it might be fun to see if it can be done in Excel without Visual Basic…
1 month after the fact.
We have a Sudoku solver that uses all the rules you mentioned, plus it finds groups of numbers that eliminate other potential values and more advanced methods like x-wing logic.
We have applied this to 3×3 and 4×4 Sudoku to great effect. Even a large 4×4 Sudoku variant can be solved in less than a third of a second.
1 month, 3 weeks after the fact.
over the weekend i started a 16*16 grid but lost patience and wrote a mini solver (in java though) with a much simpler appraoch.
my algorythm works incrementally:
1- for each cell it looks how many values are possible (i.e. not in the line, column or mini grid). If there is only 1 value possible then it put it down otherwise it just moves on to the next cell.
2- it keeps cycling through the grid until all values are found or no value can be found for a particular cell or no cell was resolve since the last cycle.
3- If no cell was resolve since the last cycle then it means we have to do a bit of guessing so it just create a new instance of the solver to which it passes the latest state of the grid + the guessed value fo the 1st blank cell. If the new solver succeed then it get the solved grid back, otherwise it tries another value and so on. if it runs out of possible values then it means that the grid cannot be solved.
1 month, 3 weeks after the fact.
I have listed the methods my sudoku solver currently uses on the site, I know it doesnt have all the loical methods yet but it does a fairly good job I think!
Gwerdy Sudoku Solver
1 month, 3 weeks after the fact.
Have a look at the macros in
http://www.brightonandhove.org/sudoku/solver5c.xls
they’re quite self explanatory and may fill some of your logic gaps.
2 months, 1 week after the fact.
I have just created my own Sudoku solver, mine works as followed:
- It checkes wich cell had only 1 possibility, and filss those cells (chekking for horizontle and verticale row and the square (of 3×3) the cell is in.
- When no cells cant be filled, it searches per square (3×3) and saves for every empty cell the possible numbers it can contain. Then he compares the numbers and when there is a number that is only possible in 1 cell, that cell gets that number.
Example: In a square are 3 empty cells. The possible numbers that can be in those cells are:
cell 1: 1,2,3
cell 2: 1,3
cell 3: 1,3
Then cell 1 must contain “2″.
I’ve written the program in java, and made it after I read one in the newspaper.
2 months, 1 week after the fact.
I have written a sudoku solver in visual basic.
I use a 81 by 10 array to store the possible values for a 9 by 9 grid. The first 9 values store the possible outcomes. The 10th value stores the search level.
The solver check the rows, columns and 3* 3 grids for impossible values. When there is only one possible outcome, the cell is filled with that number.
When there are no more cell with only one possibility, I look for cells that contain 2 possible outcomes. The level of play is incremented by 1. I test the smallest possible value first until the game is over or there is no more cells with one possible outcomes. The level of play is incremented by 1 and so on. Another array is used to keep an history of the cell tested, value tested and level of play.
At one stage I may come up with unfilled cells where there is no more solution and no cells with 2 possible outcomes. The solver eliminates the cells filled at the latest level, try the second possibility.
If the solver is unsucessful, it decreases the level of search and tries the second value of the cell chosen at the previous level.
P.S: Unfortunately English is my third language. If all these explanations seems confusing, I may send the source code in visual basic
2 months, 1 week after the fact.
I was thinking about writing a solver for fun, my method was going to be to write a function that tests the puzzle, then just brute force the dang thing (pick either rows or columns, fill an array with the initial values, then just go through every different possibility for each column or row until the checker comes back happy). Possibly, if the brute force method was too slow (prolly not tho), I was going to make the algorithm smarter. I realize its not nearly as much fun as what y’all are doing, but it would prolly be quicker and easier to write. (I was thinking about multithreading the thing too, lol)
2 years, 9 months after the fact.