aboutsummaryrefslogblamecommitdiffstats
path: root/readme.rst
blob: b3f51e538cd3b06de61b49ca7b05d9c1f377ec79 (plain) (tree)




























                                                                                

               



                                                                                    
               













































                                                                                
               



                                                                                
Translating Sudoku
##################

Using `Wikipedia's <https://en.wikipedia.org/wiki/Sudoku>`_ 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
<https://trends.google.com/trends/explore?date=all&geo=US&q=sudoku>`_ 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
:code:`sudoku.sdm`, with each line representing an unsolved puzzle. Each line
is an 81 digit string with :code:`0` representing an unanswered elements in the
matrix. For example, this line from :code:`sudoku.sdm`:

.. code-block::
   
   060000300400700000000000080000008012500600000000000050082000700000500600000010000

Equals this puzzle, we humans would see:

.. code-block::

   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 :code:`<language>/sudoku.*`, with the extension appropriate
for the language. (eg: python == :code:`.py`, Cython == :code:`.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.

.. code-block:: python

   _, 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.

.. code-block::

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