1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
INGAR'S 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. This is my first attempt.
This program uses the Qt 4.x library for its user interface, you will need
to have it installed to run the program.
BUILDING INSTRUCTIONS
Basic building instructions
autoreconf -i
mkdir build
cd build
../configure
make
The binary will be called 'sudoku' and 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
sudoku grid (9x9) 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 allows you to save the current sudoku puzzle to the current file.
The SAVE AS 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 solve a single random empty cell,
using the sudoku rules only.
The GUESS option will solve a single random empty 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 as required.
The VALIDATE option will verify if the current puzzel is valid.
SAVE GAME FILE FORMAT
The file format is extremely simple: the files can be opened and edited
with a text editor. Note that empty (unsolved) positions are saved as well.
Value 0 indicates an empty cell.
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 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 no more cells left with just one possibility.
From there, it will pick a random empty cell and fill it with one of the remaining possibilities.
From there it recurses 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 (GPL).
Copyright (c) 2012-2013
ingar@telenet.be
htpt://ingar.satgnu.net
|
