Simple Sudoku Solver in Python

Question

This is my naive approach on implementing a Sudoku solver, which is okay for simple Sudokus like this:

puzzle = [[5,3,0,0,7,0,0,0,0],
        [6,0,0,1,9,5,0,0,0],
        [0,9,8,0,0,0,0,6,0],
        [8,0,0,0,6,0,0,0,3],
        [4,0,0,8,0,3,0,0,1],
        [7,0,0,0,2,0,0,0,6],
        [0,6,0,0,0,0,2,8,0],
        [0,0,0,4,1,9,0,0,5],
        [0,0,0,0,8,0,0,7,9]]

However, it is rather slow for hard Sudokus like this:

[[9, 0, 0, 0, 8, 0, 0, 0, 1],
 [0, 0, 0, 4, 0, 6, 0, 0, 0],
 [0, 0, 5, 0, 7, 0, 3, 0, 0],
 [0, 6, 0, 0, 0, 0, 0, 4, 0],
 [4, 0, 1, 0, 6, 0, 5, 0, 8],
 [0, 9, 0, 0, 0, 0, 0, 2, 0],
 [0, 0, 7, 0, 3, 0, 2, 0, 0],
 [0, 0, 0, 7, 0, 5, 0, 0, 0],
 [1, 0, 0, 0, 4, 0, 0, 0, 7]]

The challenge description is:

Write a function that will solve a 9x9 Sudoku puzzle. The function will take one argument consisting of the 2D puzzle array, with the value 0 representing an unknown square.

The Sudokus tested against your function will be "insane" and can have multiple solutions. The solution only needs to give one valid solution in the case of the multiple solution sodoku.

It might require some sort of brute force.

Tests: 100 random tests and 5 assertions per test

Time limit: 12sec

My code:

def sudoku(board):
    (x, y) = find_empty_cell(board)
    if (x, y) == (-1, -1):
        return True

    for i in {1,2,3,4,5,6,7,8,9}:
        if valid(x,y,i,board):
            board[x][y] = i
            if sudoku(board):
                return board
            board[x][y] = 0


def valid(x,y,n,board):
    #check row and column
    for i in range(9):
        if board[x][i] == n or board[i][y] == n:
            return False

    #check box
    new_x = x//3 * 3
    new_y = y//3 * 3
    for i in range(3):
        for j in range(3):
            if board[new_x + i][new_y + j] == n:
                return False

    return True



def find_empty_cell(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i,j)

    return (-1,-1)

I am trying to succeed in passing a coding challenge in a competitive platform, which my specific code times out.

Answer 1

I am going to provide a much more over-the-top strategies to deal with Sudoku rather than outright code snippets so you can try it out on your own. [Also I am avoiding code-refactor, so that you can focus on Algorithm first, and then we will talk about Code Design, and finally implementation]

However, if you need more explicit help or I am not clear enough, leave a comment, and I would provide more details as needed.

So, the first thing I noticed about your program is that you implement a simple way to select which cell to fill: Find the first empty one, and try filling that.

There is a much more efficient way to do this: find the cell which has only one Value, and fill that first, this will lead you to fill in first few digits of board pretty quickly, and constrain your solution space.

For this: Just iterate over every cell, and store it in dict what are possible values this cell can have. Naively: A Cell C can have only values which are not available in its row, its column and its box. This will lead to something like this:

A1 -- {1, 3, 5}
A2 - {1, 6}
A3 - {6}

and so on...

Now, fun fact! You found out that A3 has only one value, so you fill in that. What this means is that you can now remove 6 from A row and 3rd column as well the box, which will further give 1-value cells, and you can repeat this process till there are no 1-value cells are left.

This will give tremendous speed improvements over your current solution.

But we are not done yet!

---

Moving forward, there are two ways to go:

• Improve our function which determines the values for cell. Remember, our naive function was that a cell has values which are not in row, cell and box. But in Sudoku, we apply other logics as well. For example if both A2 and A3 has value of {2, 4}, then we know that no other cell in A row can have value of 2 and 4, and we can remove it. There are several such strategies which can help you out. This is how Humans solve Sudoku

• Next is Computer's way. Now, you already have a solution which is close to this, which is to have a backtracking mechanism. However, instead of selecting cell randomly, select a cell with least possible values to fill in the random value. For example if you have to choose between A2 which has 2 choices and A4 which has 3 possible choices, fill in A2 first.

---

These will result in very fast Sudoku solvers :)

Answer 2

This is a classic constraint satisfaction problem.

There are a couple of general techniques you can use to greatly speed up the search for a solution:

• constraint propagation --- using the constraints of the game to immediately rule out possible values a variable can take; and

• variable ordering --- being clever about deciding which variable to attempt to assign next.

In Sudoku, the variables are the cells, and the possible values are the digits, 1-9.

You may wish to use a more refined search-state representation. With your current representation, a cell is either filled in or isn't, but you might be better off keeping track of all the possible values the cell could have (initially, the set {1, 2, ..., 9}), which would allow you to incrementally rule out values.

The improved algorithm would be a backtracking search, like the one you already have, but at each node of the search tree you apply constraint propagation to immediately rule out some of the options. If you reach a state in which all of the values of a variable have been ruled out, you know the sudoku is not solvable from that state, so you backtrack.

Constraint Propagation

An inference procedure looks at the present search state, and uses knowledge of the constraints to eliminate possible assignments. You can make full use of a procedure by repeatedly applying it until it produces no change.

Here are a couple of inference procedures you might apply:

• When the value of a cell has been deduced, you can remove that value from all other cells in the same unit (row, column, or box).

• When two cells in a unit have been reduced to the exact same pair of possible values, you can rule those values out for all other cells in the same unit. This is known as the 'naked pairs' strategy.

There are other strategies you might want to try implementing, although you will get diminishing returns.

Variable Ordering

This one's simple: simply choose the most constrained variable first -- that is, the cell with the least options. Intuitively, this is likely to rule out bad assignments earlier, resulting in a larger portion of the search tree being pruned by backtracking.

---

Leave a comment if there's anything I haven't explained clearly.

You can find an excellent write-up on Sudoku solving here.

Answer 3

I did this once in javascript, think the fastest algorithm was:

• create your board
• visit each cell, if it is empty, iterate through all possible values
• if the board has an inconsistency, take the next value
• if all values are used up, it cannot be solved
• if the value is valid, go directly to the next cell

basically a depth-search-first, creating the board that will be the solution. each inconsistency only goes back one step and tries the next possible value there, so you have very little overhead for checking one scenario.

edit: okay, that is called backtracking according to wikipedia:

https://en.wikipedia.org/wiki/Sudoku_solving_algorithms<

what i think is faster than your solution:

• you don't iterate the whole board to find the next empty cell because you already know that the previous ones are filled.

• you can just check the "adjecent cells" (same row, same column, same box) to see if the entered value is in them. no need to check the whole board for correctness. maybe you should check it once in the beginning just to be sure the problem is not bonkers already.

okay, think i am wrong again, you already know that the values are good because you used the "adjecent cells" to calculate the possible values.

i think i wasn't even keeping the possible values as lookup table, could be too much overhead to maintain them. just read them directly fom the board. or try both and see what's faster. you want to learn coding, so trying out stuff and measuring your solutions is a very good technique.

good luck / have fun!

Answer 4

• For each positions (row, col), eliminate unnecessary values in row,
  col, block by using set difference. This will shorten your code.

  e.g.

  {1,2,3,4,5,6,7,8,9}.difference(puzzle[row,:]) # for row   
  
  {1,2,3,4,5,6,7,8,9}.difference(puzzle[:,col]) # for col 
  
  r = row//3*3, c = col//3*3,  
  {1,2,3,4,5,6,7,8,9}.difference(puzzle[r:r+3,c:c+3]) # for block 3x3 
  

  For any (row, col), the only possible values will be
  the intersection set of the above three sets.

  Complete code at https://github.com/chanshukwong/sodoku