Sudoku Solver

This program solves any sudoku puzzle using backtracking (depth-first search).

Command-line usage

$ python sudoku.py -h

usage: sudoku.py [-h] [-i INPUT] [-ns | -p | -df] [puzzle]

positional arguments:
  puzzle                81 character string representing sudoku

optional arguments:
  -h, --help            show this help message and exit
  -i INPUT, --input INPUT
                        Input text file containing 81 char sudoku string, one
                        per line
  -ns, --nostat         Do not print solver's statistics
  -p, --prettyprint     Pretty print sudoku and its solution in 2D
  -df, --dfprint        Print sudoku and its solution in dataframe-friendly
                        format. Headers included

Running a Simple Example

The following is an example of a 9x9 sudoku grid (ascii art). The clues are represented by filled cells and cells to be solved (empty) by '.'

.  1  .  |  .  .  8  |  .  .  .
3  .  4  |  7  2  1  |  6  9  .
.  .  6  |  .  .  .  |  .  1  .
--------------------------------
.  .  .  |  9  .  2  |  5  3  .
.  4  2  |  1  .  3  |  7  8  .
.  3  5  |  8  .  6  |  .  .  .
--------------------------------
.  9  .  |  .  .  .  |  1  .  .
.  2  1  |  3  8  7  |  4  .  9
.  .  .  |  5  .  .  |  .  2  .

For our solver, the simplest representation of input sudoku is an 81-character string. This is generated by reading the grid row-by-row. Filled cells are represented by digits [1-9] and unfilled cells by any character. Therefore, the sudoku above will be represented as:

.1...8...3.472169...6....1....9.253..421.378..358.6....9....1...213874.9...5...2.

To solve this, run the solver as:

$ python sudoku.py .1...8...3.472169...6....1....9.253..421.378..358.6....9....1...213874.9...5...2.
.1...8...3.472169...6....1....9.253..421.378..358.6....9....1...213874.9...5...2.

>719638254354721698286495317678942531942153786135876942893264175521387469467519823
>>Solved in 0.011s with max depth 0

The solution is displayed as an 81-character string. The solver also shows execution time and max depth of recursion tree.

Pretty Print

To pretty print sudoku solution in a 2D grid format (again ascii-ish) on the command-line, use -p option.

$ python sudoku.py -p 9715..842..69...1....8.2..95.....79...76.83...28.....57..1.5....4...91..819..7254

          Input #1
  9  7  1  |  5  .  .  |  8  4  2
  .  .  6  |  9  .  .  |  .  1  .
  .  .  .  |  8  .  2  |  .  .  9
  --------------------------------
  5  .  .  |  .  .  .  |  7  9  .
  .  .  7  |  6  .  8  |  3  .  .
  .  2  8  |  .  .  .  |  .  .  5
  --------------------------------
  7  .  .  |  1  .  5  |  .  .  .
  .  4  .  |  .  .  9  |  1  .  .
  8  1  9  |  .  .  7  |  2  5  4

          Solution
  9  7  1  |  5  3  6  |  8  4  2
  2  8  6  |  9  7  4  |  5  1  3
  3  5  4  |  8  1  2  |  6  7  9
  --------------------------------
  5  6  3  |  4  2  1  |  7  9  8
  4  9  7  |  6  5  8  |  3  2  1
  1  2  8  |  7  9  3  |  4  6  5
  --------------------------------
  7  3  2  |  1  4  5  |  9  8  6
  6  4  5  |  2  8  9  |  1  3  7
  8  1  9  |  3  6  7  |  2  5  4

>>Solved in 0.004s with max depth 0

Batch Handling

-i option allows a file as an input, with each line containing 81-character string.

$ python sudoku.py -i easy_10_sudoku.txt

.1...8...3.472169...6....1....9.253..421.378..358.6....9....1...213874.9...5...2.
> 719638254354721698286495317678942531942153786135876942893264175521387469467519823
>>Solved in 0.010s with max depth 0
9715..842..69...1....8.2..95.....79...76.83...28.....57..1.5....4...91..819..7254
> 971536842286974513354812679563421798497658321128793465732145986645289137819367254
>>Solved in 0.004s with max depth 0
[Output truncated]

Test Cases

• Huge thanks to this site for providing a collection of some easy and mostly hard sudoku puzzles. I have used them for testing purposes.
• I also tested this solver using the 10 most difficult sudoku puzzles according to AIroot technique. Thanks, Arto Inkala.

Observations

• Published sudoku puzzles have only ONE solution. This solver does NOT complain if an input sudoku can have multiple solutions (technically, invalid input). It will still give you one of the n possible solutions depending on the backtracking path in the tree.
• According to this insightful paper, there is no 16-clue sudoku. That is, there must be at least 17 cells provided as clues for a sudoku to have a unique solution. This solver does NOT check for this. Given a sudoku with less than 17 clues (or interestingly, even with no clues), the solver produces a possible solution. This is the artifact of my backtracking implementation.

$ python sudoku.py .................................................................................
.................................................................................
>712348956389567124456192837138425769264719385975836412897651243523984671641273598
>>Solved in 0.148s with max depth 47

• The solver hits the max depth of 47 in the recursion tree above when no clues are given. I am curious to find a sudoku puzzle where the solver goes beyond 47. In other words, what is the max depth this solver will hit in the worst-case scenario? Clearly it must be less than 81.