**diff options**

author | Bryan Brattlof <bryanbrattlof@gmail.com> | 2019-09-10 17:50:20 -0500 |
---|---|---|

committer | Bryan Brattlof <bryanbrattlof@gmail.com> | 2019-09-10 17:50:20 -0500 |

commit | 1f03a920288ed566fb79a3a30d7c29bc19b61e41 (patch) | |

tree | df2b0c0f031ff253aff6f00cffaf71bba95d9262 /readme.rst | |

download | sudoku-1f03a920288ed566fb79a3a30d7c29bc19b61e41.tar.gz sudoku-1f03a920288ed566fb79a3a30d7c29bc19b61e41.tar.bz2 |

batman! ... initial commit

Diffstat (limited to 'readme.rst')

-rw-r--r-- | readme.rst | 87 |

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... + |