From 0885301d3292b565cce51be4514572a6d02e54b6 Mon Sep 17 00:00:00 2001 From: Stijn Buys Date: Thu, 26 May 2022 18:52:25 +0200 Subject: Documentation cleanup. Added a few interesting examples. --- README.md | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 102 insertions(+) create mode 100644 README.md (limited to 'README.md') diff --git a/README.md b/README.md new file mode 100644 index 0000000..6bef1dc --- /dev/null +++ b/README.md @@ -0,0 +1,102 @@ + +# Sudoku Solver + +I'm not a fervent sudoku solver but I always wanted to try implementing a program +to solve the puzzles faster than I can.The program uses Qt 5 for its user interface, +you will need to have it installed to build or run the program. + +## Building + +Basic building instructions: + + autoreconf -i + mkdir build + cd build + ../configure --with-qt-includes=/usr/include/qt + make + +The binary is called 'sudoku' and will be located in the 'src' directory. +You can run it from within the build directory: + + src/sudoku + +## Usage + +Running the program will show the main window, which consists of a basic +9x9 sudoku grid and a number of menu options. + +### Game menu + +The *New* option will clear the current game + +The *Load* option allows you to load a previously loaded game. + +The *Save* option allows you to save the current sudoku puzzle to the current file. + +The *Save As* option allows you to save the current sudoku puzzle to a new file. + +The *Revert* option will reload the current file from disk. + +The *Quit* option will close the program. + +### Move menu + +The *Step* option will try to solve a single random unsolved cell, +using the sudoku rules only. + +The *Guess* option will try to solve a single random unsolved cell, +and will guess (search) for a solution as required. + +The *Solve Rules* option will try to solve the game, +using sudoku rules only. + +The *Find Solution* option will try to solve the game, +and will guess (search) for a solution where required. + +The *Validate* option will verify if the current puzzle is valid. + +### Settings menu + +* The *Mark solveable* option will, if enabled, mark cells that can be solved without guessing in yellow. + +## Save game file format + +The file format is extremely simple: +the files can be opened and edited with a text editor. +Unsolved positions are saved as well and are indicated by zeroes. + +Example: + + 0 0 0 8 0 2 9 0 0 + 0 0 0 9 0 7 3 6 0 + 4 0 9 0 0 0 0 0 7 + + 0 8 0 0 0 5 0 4 6 + 1 3 0 0 7 8 0 0 0 + 0 0 0 2 0 0 0 7 0 + + 3 4 6 1 2 0 7 0 0 + 0 1 0 0 0 0 6 0 2 + 0 5 0 0 8 0 0 0 0 + +While the file format is optimized for readability, the program will +actually ignore extra whitespace while loading a file. This allows you to +load games from a simple file with a sequence of 81 numbers. + +## Algorithm + +The constraint solver will try to find a solution by applying +two sets of sudoko constraints: the sudoku elimination rules, +where every number from 1 to 9 can only appear once in every row, column and subgrid, +and the sudoko inclusion rules, where every number has to appear exactly once +in every row, column and subgrid. + +The search solver will apply constraints until there are no cells left with a unique solution. +From there, it will pick a random unsolved cell, fill it with one of the remaining possibilities +and recurse into the next iteration. + +## Copyright + +This sudoku solver was written by Stijn "Ingar" Buys and is available under +the terms and conditions of the GNU Public License, version 3 or higher. + -- cgit v1.2.3