aboutsummaryrefslogtreecommitdiffstats
path: root/readme.rst
diff options
context:
space:
mode:
Diffstat (limited to 'readme.rst')
-rw-r--r--readme.rst87
1 files changed, 87 insertions, 0 deletions
diff --git a/readme.rst b/readme.rst
new file mode 100644
index 0000000..1fac58e
--- /dev/null
+++ b/readme.rst
@@ -0,0 +1,87 @@
+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:: terminal
+
+ 060000300400700000000000080000008012500600000000000050082000700000500600000010000
+
+Equals this puzzle, we humans would see:
+
+.. code-block:: terminal
+
+ 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:: terminal
+
+ $ python sudoku.py 0600003004007000000000000800000080125006000000000000500...
+ 9618453274587231692371695847963584125246918738132749561824367953795826416...
+