How To Crack Sudoku Using Python

Siddharth Isaiah

1 min read

Sudoku is a fun logic-based puzzle in which the objective is to fill a 9×9 grid with digits from 1-9 in such a way that no digit is repeated in the same row, column or 3×3 box.

In this post, I will show you how we can solve sudoku using a backtracking algorithm.

What is Backtracking?

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems,
that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

 Donald E. Knuth (1968). The Art of Computer Programming. Addison-Wesley.

A backtracking approach is a step better than a naive brute force search algorithm. In a brute force search, we would have to generate all possible variations of a sudoku board and then choose a valid solution. With backtracking, we only keep valid boards so at any given time the sudoku grid is always correct.

The Algorithm

  1. Find the first empty square
  2. If there are no empty square that means that the board is full and since we only keep valid solutions, the sudoku is solved and we are done! Return True.
  3. If an empty square exists – try filling it with a number from [1-9]
  4. Check to see if the board is valid (the number is not repeated in the same row, column or 3×3 box)
  5. If we have a valid board from step 4, Goto Step 1
  6. If we don’t have a valid board from step 4, un-assign the number from the square and backtrack to step 3, trying with a different number
  7. If you have reached this step- there is no solution. Return False.

The Code

Let’s begin coding. First, we need a way to represent the sudoku board, we can do this using a 2D array, we will also need some helper functions to check if a board is valid and another function to print the solved board for us.

This is just one way of solving sudoku, for a more efficient algorithm be sure to check out this essay by Peter Norvig. It uses constraint propagation and search, to solve the worlds hardest sudoku puzzles in a tenth of a second!

Related posts:

Leave a Reply

Your email address will not be published. Required fields are marked *