Solve Any Sudoku With 10 Lines of Python Code

Some time ago I was talking with a friend who is hooked on Sudoku puzzles. The conversation went nowhere, because my friend was busy thinking about Sudoku. So I thought to myself, if I solve all Sudoku puzzles at once, perhaps my friend can pull his head out of his arse and normal conversations can resume. And because the puzzle is such a simple one, I bet him that I could do it in only 10 lines of code in my favourite programming language: Python.

A few hours of work, here is the solution I came up with - it is not perfect, it is just brute force, and not particularly elegant. But it fits into 10 lines of Python code, and serves as an interesting case study in list comprehension in Python.

The task is to solve sudoku of all sizes and complexities, and giving all solutions if there are multiple. Input and output code do not count as part of the 10 lines, only that part that solves the puzzle counts towards the 10 lines.

Input
The easiest, but perhaps most inelegant, way to input the Sudoku board, is to put it directly into the Python code like this:

1:  input_board = [   
2:                  5,3,0,0,7,0,0,0,0,  
3:                  6,0,0,1,9,5,0,0,0,  
4:                  0,9,8,0,0,0,0,6,0,  
5:                  8,0,0,0,6,0,0,0,3,  
6:                  4,0,0,8,0,3,0,0,1,  
7:                  7,0,0,0,2,0,0,0,6,  
8:                  0,6,0,0,0,0,2,8,0,  
9:                  0,0,0,4,1,9,0,0,5,  
10:                 0,0,0,0,8,0,0,7,9  
11:                  ]  
12:    
13:  board_size = 9  
14:  subsquare_width = 3  
15:  subsquare_height = 3  
16:    

As you can see, the board is just a list/array of numbers, where 0 means a field is blank, and whatever other number means whatever other number is pre-filled in as part of the puzzle. I also have three variables giving the size of the board, the width and height of the subsquare.

Output
Simple command line output sounded the easiest to me, but rather than simply print the board as an array/list of numbers - which would be very difficult to interpret, I created a pretty-print function:

1:  def prettyprint(board, board_size):  
2:      print  
3:      for i in range(board_size):  
4:          print board[i*board_size:i*board_size+board_size]  
5:    

Which creates an output that resembles the playing board. Of course, it would be possible to make the output nicer and more readable, but this should be good enough for now.

Solution
And now to the meat of the problem: solving the board. My solution is a recursive function, which finds the first available blank, creates a list of legal entries for that position based on the current board configuration, fills in each one in turn and calls itself. If there are no blanks on the board, the program has reached a solution.

In pseudo-code, something like:

1:  def solve(board):  
2:    if no more blanks:  
3:      print solution  
4:    find first blank  
5:    find a list of possible values for the blank  
6:    for each possible value:  
7:      insert possible value into board  
8:      solve(board)  

Firstly, how to identify the first known blank? Well, since blanks are represented by 0, and the board is a straightforward Python list, we can just call the index function: i = board.index(0). If no entry with 0 exists, this call will throw an exception, which is perfect, because if there are no blanks, then we know we have arrived at a solution, so we can just print it:

1:  def solve(board):  
2:      try: i = board.index(0)  
3:      except: prettyprint(board, board_size); return  
4:    

Secondly, when we have found a blank, we must find out which numbers we could possibly fill in. And this is the most intriguing part of the solution. In the global space, we first create three boards with the same label for each column, row and subsquare, like this:

1:  col_labels = [i%board_size for i in range(len(input_board))]  
2:  row_labels = [i/board_size for i in range(len(input_board))]  
3:  sqr_labels = [(board_size/subsquare_width)*(row_labels[i]/subsquare_height)+col_labels[i]/subsquare_width for i in range(len(input_board))]  
4:    

The reason for this will be obvious in a moment, just bear with me. To get a better idea, let's see what these three codes create. In our 9x9 example with 3x3 subsquares, the three lines of code directly above create three dummy-boards that look like this:

1:  col_labels = [   
2:                  0,1,2,3,4,5,6,7,8,  
3:                  0,1,2,3,4,5,6,7,8,  
4:                  0,1,2,3,4,5,6,7,8,  
5:                  0,1,2,3,4,5,6,7,8,  
6:                  0,1,2,3,4,5,6,7,8,  
7:                  0,1,2,3,4,5,6,7,8,  
8:                  0,1,2,3,4,5,6,7,8,  
9:                  0,1,2,3,4,5,6,7,8,  
10:                 0,1,2,3,4,5,6,7,8  
11:                  ]  
12:    
13:  row_labels = [   
14:                  0,0,0,0,0,0,0,0,0,  
15:                  1,1,1,1,1,1,1,1,1,  
16:                  2,2,2,2,2,2,2,2,2,  
17:                  3,3,3,3,3,3,3,3,3,  
18:                  4,4,4,4,4,4,4,4,4,  
19:                  5,5,5,5,5,5,5,5,5,  
20:                  6,6,6,6,6,6,6,6,6,  
21:                  7,7,7,7,7,7,7,7,7,  
22:                  8,8,8,8,8,8,8,8,8  
23:                  ]  
24:    
25:  sqr_labels = [   
26:                  0,0,0,1,1,1,2,2,2,  
27:                  0,0,0,1,1,1,2,2,2,  
28:                  0,0,0,1,1,1,2,2,2,  
29:                  3,3,3,4,4,4,5,5,5,  
30:                  3,3,3,4,4,4,5,5,5,  
31:                  3,3,3,4,4,4,5,5,5,  
32:                  6,6,6,7,7,7,8,8,8,  
33:                  6,6,6,7,7,7,8,8,8,  
34:                  6,6,6,7,7,7,8,8,8  
35:                  ]     
36:    

These three dummy-boards enables us to quickly generate a list of numbers that are illegal to insert in a blank space like so:

1:      bag = [board[j] for j in filter(lambda x: (col_labels[i]==col_labels[x]) or (row_labels[i]==row_labels[x]) or (sqr_labels[i]==sqr_labels[x]),range(len(board)))]  
2:    

The filter method creates a list of board positions that have the same column, the same row and the same subsquare as the blank space we are currently considering filling in. Then, with a for-loop in list-comprehension-style, we pick out the entries in those positions. This could be split into several lines to make it more readable, but this is one of the shortcuts I used to fit it into 10 lines. I apologise for the ugliness of it.

Now that we have a list of numbers that are not permitted in the current blank space, we simply need to run through each of the possibilities except those, try inserting the possibility into the board and move on to the next blank and do the same thing:

1:      for j in filter(lambda x: x not in bag, range(1,board_size+1)):  
2:          board[i] = j; solve(board); board[i] = 0  
3:    

And that simple procedure, ladies and gentlemen, can create all the solutions to all Sudoku ever created.

Complete Solution
For those who want to experiment, pin back your lug'oles, drop the following code into a file, mess with it, and then run it through your Python interpreter:

1:  input_board = [   
2:                  7,0,0,4,0,9,0,0,6,  
3:                  5,0,9,0,8,6,1,2,0,  
4:                  1,4,0,0,0,0,0,0,0,  
5:                  6,5,0,8,0,0,0,0,0,  
6:                  0,2,4,9,0,1,5,6,0,  
7:                  0,0,0,0,0,2,0,1,8,  
8:                  0,0,0,0,0,0,0,8,7,  
9:                  0,7,5,2,4,0,6,0,1,  
10:                  2,0,0,3,0,7,0,0,5  
11:                  ]  
12:    
13:  board_size = 9  
14:  subsquare_width = 3  
15:  subsquare_height = 3  
16:    
17:  def prettyprint(board, board_size):  
18:      print  
19:      for i in range(board_size):  
20:          print board[i*board_size:i*board_size+board_size]  
21:    
22:  col_labels = [i%board_size for i in range(len(input_board))]  
23:  row_labels = [i/board_size for i in range(len(input_board))]  
24:  sqr_labels = [(board_size/subsquare_width)*(row_labels[i]/subsquare_height)+col_labels[i]/subsquare_width for i in range(len(input_board))]  
25:    
26:  def solve(board):  
27:      try: i = board.index(0)  
28:      except: prettyprint(board, board_size); return  
29:      bag = [board[j] for j in filter(lambda x: (col_labels[i]==col_labels[x]) or (row_labels[i]==row_labels[x]) or (sqr_labels[i]==sqr_labels[x]),range(len(board)))]  
30:      for j in filter(lambda x: x not in bag, range(1,board_size+1)):  
31:          board[i] = j; solve(board); board[i] = 0  
32:        
33:  solve(input_board)  
34:    

Unless the number of solutions is very large, this will only take a fraction of a second to run on any computer. Enjoy!

Please feel free to use this code as you wish. If you use this solution for anything fun/interesting/at-all, please provide a link to this page from yours, and drop me a comment!