sudokuru

Ruby Sudoku puzzle solver at the speed of light.

The Goal

• Solves a given Sudoku puzzle. A Box-map file is taken into account when solving, if provided.

Execution

Within the sudokuru folder:

$ ruby sudokuru.rb <path to puzzle file> <path to optional box map file>

To see every single solving step:

$ env DEBUG=yes ruby sudokuru.rb <path> <path>

To change the allowed solving time (default is 60 seconds):

$ env RUNTIME=42 ruby sudokuru.rb <path> <path>

In the absence of a file path provided, sudokuru will default to:

$ ruby sudokuru.rb ./puzzles/sample_input.txt

To run the specs:

$ rake test

Puzzle Input Formatting

Input puzzles should be common file types (.txt, .rb, etc.), one row per line, formatted:

  1-3-              1_3_              1 3               1 3-
  -14-              _14_               14               -14_
  24-3      or      24_3      or      24 3      or      24-3
  --2-              __2_                2               _ 2-
 dashes         underscores          spaces             mixed

With digits 1-9 and the blank characters "-", "_", and spaces allowed only.

Errors will be returned if the data is not properly formatted, with directions to fix:

ERROR: Row 7 (-324-9--3) contains duplicate values. Please fix and rerun.

Box Map Input Formatting

Box map files should also be common file types (.txt, .rb, etc.), one row per line, formatted:

         AABB
         AABB
         CCDD
         CCDD
 Capitalized Alphabet

No wildcard box values allowed. Only capitalized alphabet characters.

Errors will be returned if the data is not properly formatted, or if there are duplicates:

Error details:

  AAA------  -28------
  AAA------  -16------
  A--------  ---------
  AA-------  13-------
  ---------  ---------
  ---------  ---------
  ---------  ---------
  ---------  ---------
  ---------  ---------

ERROR: Box A (-28-16-13) contains duplicate values. Please fix and rerun.

Results

If formatting is correct, puzzle will be processed until sucessful, or will error-out if solution is not found within RUNTIME value (default is 60 seconds).

SUCCESS! Solution found in: 0.015643 seconds.

  534678912
  672195348
  198342567
  859761423
  426853791
  713924856
  961537284
  287419635
  345286179

Application Milestones

Execution:

• A default input.txt file at the app's location should be present.
• User can provide a specific file path as part of execution.

Input (diagnostic checks on validity and formatting):

• Same number of "rows" in txt file as number of "columns" (characters).
• Only digits 1-9 and allowed "blank" characters are present, none larger than the puzzle size.
• No duplicate digits are already present in puzzle rows/columns.
• No duplicate digits in 9x9 puzzle sub-boxes.
• Tests for each input check.

Implementation:

• Find starting row/column by calculating which one has the greatest number of pre-filled items.
• Find starting index (via the most filled complementary slice relative to the prime slice).
• Attempt to fill a given cell, and solve the puzzle. Backtrack when solution is not found and retry new values.

Scaling Solutions:

• 2x2 puzzles.
• ...
• 9x9 puzzles.

Stretch Goals:

• Use mirror file with box map (A-I) characters to determine boxes.
• Add a variable for determining when the puzzle finder will time out (currently hardcoded to 60 seconds).
• Rails app.
• Ability to use photo of sudoku puzzle, and OCR loads the data for solving.
• Smartphone app.