aboutsummaryrefslogtreecommitdiffstats

Translating Sudoku

Using Wikipedia's definition:

Sudoku (数独 sūdoku, digit-single), originally called Number Place) is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called "boxes", "blocks", or "regions") contain all of the digits from 1 to 9.

It was a big deal before the internet reached our cell phones. However, for computer scientists, sudoku is a type of combinatorial optimization problem that can be "solved" in a number of ways.

For me, sudoku is a great puzzle to help me learn the basics of a new language. It's just complicated enough to keep my interest as well as easy enough to focusing on the code instead of the algorithm.

The Puzzles

All of the unsolved sudoku puzzles (all 49,151 of them) are stored in sudoku.sdm, with each line representing an unsolved puzzle. Each line is an 81 digit string with 0 representing an unanswered elements in the matrix. For example, this line from sudoku.sdm:

060000300400700000000000080000008012500600000000000050082000700000500600000010000

Equals this puzzle, we humans would see:

 0  6  0 | 0  0  0 | 3  0  0
 4  0  0 | 7  0  0 | 0  0  0
 0  0  0 | 0  0  0 | 0  8  0
---------+---------+---------
 0  0  0 | 0  0  8 | 0  1  2
 5  0  0 | 6  0  0 | 0  0  0
 0  0  0 | 0  0  0 | 0  5  0
---------+---------+---------
 0  8  2 | 0  0  0 | 7  0  0
 0  0  0 | 5  0  0 | 6  0  0
 0  0  0 | 0  1  0 | 0  0  0

The Solvers

Each solver is named <language>/sudoku.*, with the extension appropriate for the language. (eg: python == .py, Cython == .pyc)

What lies below are the notes about each solver's language.

Python

The python Sudoku solver uses a search algorithm to find unanswered elements in the matrix with the least possibilities.

_, i = min((len(n), i) for i, n in enumerate(matrix) if len(n) > 1)

This increases the chance of randomly picking the correct number for the cell (eg: 2 possibilities == 50% chance, vs 9 possibilities == ~11%) and increasing the overall probability of guessing the correct answer rather than by brute force alone.

We then use constraint propagation to eliminate possibilities of unanswered cells and to quickly find conflicts where we will need to backtrack.

Usage

After installing python, pass the 81 digit string as an argument in your terminal to get the solved string returned.

$ python sudoku.py 0600003004007000000000000800000080125006000000000000500...
 9618453274587231692371695847963584125246918738132749561824367953795826416...