# How To Crack Sudoku Using Python

Siddharth Isaiah

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 file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/usr/bin/env python def print_board(board): for row in board: for col in row: print(col, end=" ") print("\n") def find_empty_square(board): """ Return a tuple containing the row and column of the first empty square False if no squares are empty """ for i, row in enumerate(board): for j, square in enumerate(row): if square == 0: return (i, j) return False def num_in_row(board, row, num): """True if num is already in the row, False otherwise""" return num in board[row] def num_in_col(board, col, num): """True if num is already in the column, False otherwise""" return num in [row[col] for row in board] def num_in_box(board, row, col, num): """ row and col should be the top-left coordinates of the box True if num is already in the 3x3 box, False otherwise """ return num in [board[row+i][col+j] for i in range(3) for j in range(3)] def safe_position(board, row, col, num): """ A safe position is one in which a number can be placed without being repeated in the same row, column or 3x3 box True if position is safe, False otherwise """ return not num_in_row(board, row, num) \ and not num_in_col(board, col, num) \ and not num_in_box(board, row - row %3, col - col %3, num) def solve_sudoku(board): """Returns True if a solution exists False otherwise""" next_empty_square = find_empty_square(board) if not next_empty_square: # The board is full/solved return True row, col = next_empty_square for num in range(1, 10): if safe_position(board, row, col, num): board[row][col] = num if solve_sudoku(board): return True board[row][col] = 0 # invalid position, unnasign the number return False # backtrack and try another number def main(): grid = [[0,2,6,0,0,0,8,1,0], [3,0,0,7,0,8,0,0,6], [4,0,0,0,5,0,0,0,7], [0,5,0,1,0,7,0,9,0], [0,0,3,9,0,5,1,0,0], [0,4,0,3,0,2,0,5,0], [1,0,0,0,3,0,0,0,2], [5,0,0,2,0,4,0,0,9], [0,3,8,0,0,0,4,6,0]] if solve_sudoku(grid): print_board(grid) else: print("No solution exists!") if __name__ == '__main__': main()
view raw sudoku.py hosted with ❤ by GitHub

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!