Simple Sudoku Solver in Python 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.
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 :)