Skip to content

hbldh/dlxsudoku

Repository files navigation

DLXSudoku

Build and Test PyPi version PyPi license Coverage Status

Sudoku Solver written in pure Python with no dependencies.

It solves Sudokus of sizes N x N by pure induction as far as is possible, and then uses an optional Dancing Links brute force solver, when the basic induction is not enough.

Installation

Install with pip:

pip install dlxsudoku

Testing

Tests can be run using pytest:

pytest tests/

The tests make a HTTP request to a file containing several Sudokus on Project Euler.

Usage

A Sudoku stored in a file can be solved as such:

from dlxsudoku import Sudoku

s = Sudoku.load_file('path/to/sudoku.sud')
s.solve(verbose=True, allow_brute_force=True)

Alternatively, if your Sudoku is stored in string variable it can be solved in the following fashion:

from dlxsudoku import Sudoku

sudoku_string_1 = "030467050920010006067300148301006027400850600090200400005624001203000504040030702"
sudoku_string_2 = "# Example Sudoku\n" + \
                  "*72****6*\n" + \
                  "***72*9*4\n" + \
                  "*9*1****2\n" + \
                  "*******4*\n" + \
                  "82*4*71**\n" + \
                  "**9*6*8**\n" + \
                  "***9**6**\n" + \
                  "**3*72*9*\n" + \
                  "*6*843*7*"

s1 = Sudoku(sudoku_string_1)
s1.solve()
print(s1.to_oneliner())

s2 = Sudoku(sudoku_string_2)
s2.solve()
print(s2)

DLXSudoko treats a Sudoku with multiple solutions as a faulty one and raises a dlxsudoku.exceptions.SudokuHasMultipleSolutionsError exception in such a situation.

Use from terminal

DLXSudoku also installs a console entry point. Can solve Sudokus from string or from path:

solve-sudoku --sudoku 030467050920010006067300148301006027400850600090200400005624001203000504040030702

or

solve-sudoku --path "path/to/sudoku.sud"

Sudoku formatting

A Sudoku file or string should be structured in the following manner:

# Optional comment or metadata
*72****6*
***72*9*4
*9*1****2
*******4*
82*4*71**
**9*6*8**
***9**6**
**3*72*9*
*6*843*7*

or as a one-liner:

030467050920010006067300148301006027400850600090200400005624001203000504040030702

Any character other than [1-9] may be used as a placeholder for unknowns.

References

The Dancing Links code has been adapted from Algorithm X in 30 lines!, only modified slightly to accommodate class structure and Python 2.6.