Once you are done with all columns, do the rows, and then the boxes. Once you are done with all numbers up to 9, repeat the process with the next column. If there is only one such cell, then you can enter the 1 in that cell. Check in how many places you can enter the number 1 without violating the Sudoku condition. You know that each column, row and box must contain the number 1 at the end. There is another method that immediately comes to mind to the beginner Sudoku solver: look at a particular column (or row, or box). Let’s call this method the candidate-checking method. However, there might be a point where you get stuck with this method: once you have considered each cell at least once since last entering a number, you can be sure that this method will not solve the puzzle for you. It is natural to go through all cells in typewriter order and make this check, and if possible add enter the number in the corresponding field. If there is only one candidate, then you enter that number. In other words, you check which numbers may go in a certain cell. When you did your first Sudoku puzzle, you probably noticed that you can solve some Sudoku puzzles by taking each number from 1 to 9 in turn and by observing that a certain field can only contain a certain number. Our ultimate goal is to introduce an algorithm that allows a person to solve any Sudoku puzzle on paper, or say (with confidence!) that there is no solution. We will now look at some solving methods that work well on paper. Something else is annoying about this algorithm: it’s virtually impossible to do on paper, there are just too many numbers that need to be entered and erased. Certainly nothing I could impress my dad with. In practice, it turns out that the algorithm is quite slow: my own implementation in Matlab was about as fast as a human on most puzzles, sometimes a lot slower. The previous activity suggests that we have found a solving algorithm that is in theory very useful. Also explain how we could modify the algorithm to find every solution to a given puzzle. Its rating is “fiendish”.Īctivity 7: Explain in a paragraph or two why our algorithm will find a solution to any Sudoku puzzle with a solution.
I tested my code using the following puzzle.
To solve a Sudoku puzzle, download the two files, enter the Sudoku matrix that you want the algorithm to solve at the top of solve_sudoku.m (an example for the formatting is included in the file), save, and run solve_sudoku.m. The code comes in two parts: anydouble.m, which checks whether there are any numbers that appear twice in any row, column or 3x3 box, and solve_sudoku.m, which is the main file. It’s not optimized for speed, but for readability. If you know MATLAB (or any imperative programming language), you might like look at my MATLAB implementation of the algorithm. If not, then erase the 9 from the corrent cell, call the previous cell in the enumeration the new “current cell”, and continue with step 3. In case b: if the current cell is the first cell in the enumeration, then the Sudoku puzzle does not have a solution. If not, then go back to step 2 with the “current cell” being the next cell.
you have reached 9 and still violate the Sudoku condition.Ĥ.In case a: if the current cell was the last enumerated one, then the puzzle is solved. the entry does not violate the Sudoku condition, or untilī. If this violates the Sudoku condition, try entering a 2, then a 3, and so forth, untilĪ. 1.Enumerate all empty cells in typewriter order (left to right, top to bottom)Ģ.Our “current cell” is the first cell in the enumeration.ģ.Enter a 1 into the current cell.