~sschwarzer/sudoku-solver

sudoku-solver/README.md -rw-r--r-- 3.7 KiB
fc2397a8Stefan Schwarzer Adapt artifacts for changed build target directory 5 months ago

#Sudoku solver

#Overwiew

This repository implements a simple Sudoku solver, written in Racket. Different from most other solvers, this one can generate a GraphViz dot file that shows the solution process.

After installing the package sudoku-solver (see below for installation instructions), you can run the solver on an input file with

$ sudoku-solver <input-path>

The expected input format looks like this:

53- -7- ---
6-- 195 ---
-98 --- -6-

8-- -6- --3
4-- 8-3 --1
7-- -2- --6

-6- --- 28-
--- 419 --5
--- -8- -79

Whitespace can be added for readability, but is ignored when parsing the input.

If a solution exists, the program will print the input from the file and the output for the solved Sudoku board. The program uses the first solution it finds and doesn't check for any others.

Here's an example run processing the puzzle from the Sudoku Wikipedia article:

$ sudoku-solver games/sudoku-solver/examples/wikipedia_article.txt
Input:

53- -7- ---
6-- 195 ---
-98 --- -6-

8-- -6- --3
4-- 8-3 --1
7-- -2- --6

-6- --- 28-
--- 419 --5
--- -8- -79

Solution:

534 678 912
672 195 348
198 342 567

859 761 423
426 853 791
713 924 856

961 537 284
287 419 635
345 286 179

There are several command line options, described in the help output:

sudoku-solver [ <option> ... ] <file-path>
 where <option> is one of
  --color : 
    Colorize values of the solution.
  --stats : 
    Print solver statistics.
    These consist of:
    - solver runtime
    - number of needed digit guesses
    - number of times the solver encountered each recursion level. When the
      solver consecutively tries the digits 1 to 9 at one recursion level, the
      count for that level is only increased by one, not by the number of
      digits tried. The initial recursion level of the solver is 1.
  --progress-text-file <text-file> : 
    Create a text file of the solution process.
    The format of the lines is "board-index --guess--> next-board-index".
    Board indices are numbered row-wise from 0 for the upper-left corner to 80
    for the lower-right corner of the board/grid. The line means that the
    solver could make a feasible guess `guess` at `board-index` that made it
    possible to continue with guesses at `next-board-index`. The lines are
    indented according to the recursion level.
  --progress-dot-file <dot-file> : 
    Create a DOT file for processing by Graphviz's `dot` command.
    The generated diagram shows the solution process. The interpretation of the
    graph is analoguous to the text output from `--progress-text-file` (see
    above).
  --help, -h : Show this help

Here's an example for the --progress-dot-file output turned into a PDF file. If you have GraphViz installed, you can turn a dot into a PDF file with

$ dot -T pdf -o output-file.pdf input-file.dot

For most graphs, you'll need a PDF viewer that can handle large files.

Enter tickets for bugs and improvement suggestions on Sourcehut.

#Installation

#With Racket

If you have Racket installed, you can install the package with

$ raco pkg install sudoku-solver

and run the program with

$ racket -l games/sudoku-solver -- [options] <file-path>

The actual solver is in games/sudoku-solver/solver.rkt.

#Without Racket

There are precompiled binaries for different platforms.