YasSS - Yet Another (Simple|Stupid) Sudoku Solver
On my common project page I already introduced YasSS. Here is a more detailed description.
What is YasSS?
YasSS is a command line C++ program that solves given Sudokus.
The actual work is done in a class the encapsulates all the functionality, so it should be easy to set up another GUI for it.
Documentation
You can read the yasss man page and the yasss-curses man page online.
How It Works
YasSS stores the Sudoku field in a two-dimensional array. For each cell there is stored which numbers can be entered there.
The actual solver is discussed below.
Header File of Class Sudoku
If a cell contains a zero, it is empty.
#ifndef _MORITZ_FIELD_
#define _MORITZ_FIELD_
#include <iostream>
// a Sudoku playing field implemented as a 2d fixed size array
// contains consistency checks and a solver.
class sudoku {
public:
sudoku();
// creates a field with in ital data. 0 means "not set".
// Note that the first coordinate is considered as x, so if
// you create an array char f= {{1 ,2 ...}, {..}} you will get
// the transposed sudoku field. but don't worry, sudoku is
// invariant under transposition
sudoku(char init_data[9][9]);
sudoku(char* init_data);
// creates a field with initial data. 0 means "not set".
// Note that the first coordinate is considered as x, so if
// you create an array char f= {{1 ,2 ...}, {..}} you will get
// the transposed sudoku field. but don't worry, sudoku is
// invariant under transposition
sudoku(int init_data[9][9]);
// generates a rather simplistic output to the given stream
// call as pretty_print(cout) or something like that...
void pretty_print(std::ostream &handle);
// just print all chars in one row
void print(std::ostream &handle);
// sets item (x, y) to val
// assumes that it is doesn't lead to an intermediate
// conflict with sudoku rules
// which is equivalent to saying it requires
// allowed_set(val, x, y) to be true
void set_item(char val, int x, int y);
// get entry at position (x, y)
// 0 means "unset"
int get_item(int x, int y);
// returns true if it doesn't lead to a direct error if you
// set (x, y) to val
// If data[x][y] != 0 the return value is
// true if val == data[x][y]
bool allowed_set(char val, int x, int y);
// try to solve the puzzle. Returns true on success.
bool solve();
// returns true if there is no zero entry left, e.g. the
// problem is solved correctly.
bool is_solved();
// returns true if there is no possibility to continue without
// violating rule
bool is_stuck();
protected:
// contains 0 for unset values and the corresponding value
// if the value is set
char data[9][9];
// allowed[x][y][i] is true if and only if it is possible to
// set data[x][y] to i+1 without conjuring an immediate
// collision.
// If data[x][y] == i != 0 then allowed[x][y][i] is true,
// allowed[x][y][j] = false for j != i
bool allowed[9][9][9];
bool simple_solve();
bool simple_solve1();
bool simple_solve2();
// returns either an is_solved or a stuck() version of *this
bool backtrack();
void null_init();
int recursion_depth;
void set_recursion_depth(int rd) {recursion_depth = rd;};
};
Implementation
Now comes the interesting part. The boring functions are not included, you can find them in in the source distribution.
.Let's start simple..
bool sudoku::allowed_set(char val, int x, int y){
return allowed[x][y][val - 1];
}
You only have to remember that there is no entry for the zero in the
allowed array, so you have to substract 1.
Inserting a number
Now the code for inserting a number and updating its dependencies:
void sudoku::set_item(char val, int x, int y){
// a few checks for debugging purposes
assert(allowed_set(val, x, y));
assert(data[x][y] == 0);
assert(val >= 1);
assert(val <= 9);
// enter value
data[x][y] = val;
// update dependencies...
// ... in the columns and rows
for(int i = 0; i < 9; i++){
allowed[x][i][val - 1] = false;
allowed[i][y][val - 1] = false;
}
// in the 3x3 sub grid
int x_orig = 3 * (int) (x/3);
int y_orig = 3 * (int) (y/3);
for (int i = x_orig; i < x_orig + 3; i++){
for (int j = y_orig; j < y_orig + 3; j++){
allowed[i][j][val - 1] = false;
}
}
// ... and where the number was entered
for (int i = 0; i < 9; i++)
allowed[x][y][i] = false;
allowed[x][y][val - 1] = true;
}
Simple Solve 1
Now we actually start to solve Sudokus.
In each cell we look if there is only one number possible:
bool sudoku::simple_solve1(){
// looks at every place in the lattice if there is a only one number
// possible. If so, the appropriate number is set.
bool res = false;
for (int x = 0; x < 9; x++){
for (int y = 0; y < 9; y++){
if ((int) data[x][y] == 0){
int c = 0;
//int x0 = 0, y0 = 0, i0 = 0;
int i0 = 0;
for (int i = 0; i < 9; i++){
if (allowed[x][y][i]){
// x0 = x;
// y0 = y;
i0 = i;
c++;
}
}
if (c == 1){
set_item(i0 + 1, x, y);
res = true;
} // for i
} // if (data != 0)
} // for y
} // for x
return res;
}
It looks a bit scary because there are three nested loops, but the logic is simple.
Simple Solve 2
The next part works differently: each entity (e.g. column, row, 3x3 sub grid) is searched if there is only one place left for a number.
bool sudoku::simple_solve2(){
// searches if there is any row/column/3x3-square where there is a
// number which can be placed in only one position.
// If it finds such a number it is set.
bool res = false;
for (int x = 0; x < 9; x++){
int vcount[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
for (int y = 0; y < 9; y++){
if (data[x][y] == 0) {
for (int i = 0; i < 9; i++){
if (allowed[x][y][i]){
vcount[i]++;
}
}
} else {
// any number < 1 will do...
vcount[data[x][y] - 1] = 10;
} // if
} // for y
for (int i = 0; i < 9; i++){
if (vcount[i] == 1){
// Hurray
// We know that there is only one possible
// place for number i+1 to put
// we've got to find it:
for (int k = 0; k < 9; k++){
if (allowed[x][k][i]){
set_item(i+1, x, k);
res = true;
}
}
}
} // for i
} // for x
// now we've got to do the hole damn thing for the columns:
for (int y = 0; y < 9; y++){
int hcount[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
for (int x = 0; x < 9; x++){
if (data[x][y] == 0) {
for (int i = 0; i < 9; i++){
if (allowed[x][y][i]){
hcount[i]++;
}
}
} else {
// any number < 1 will do...
hcount[data[x][y] - 1] = 10;
} // if
} // for y
for (int i = 0; i < 9; i++){
if (hcount[i] == 1){
// Hurray
// We know that there is only one possible
// place for number i+1 to put
// we've got to find it:
for (int k = 0; k < 9; k++){
if (allowed[k][y][i]){
set_item(i+1, k, y);
res = true;
}
}
}
} // for i
} // for x
// now it's getting really nasty. Do the same for the 3x3-sub squares:
// (It's not nasty in principle, you just have to be careful not to
// confound some indices)
for (int xb = 0; xb < 9; xb += 3){
for (int yb = 0; yb < 9; yb += 3){
int rcount[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
for (int i = 0; i < 9; i++){
int x = xb + i % 3;
int y = yb + (int) i/3;
if (data[x][y] == 0){
for (int k = 0; k < 9; k++){
if (allowed[x][y][k]){
rcount[k] ++;
}
} // for k
} else {
rcount[data[x][y] - 1] = 10;
} // if data == 0
} // for i
for (int i = 0; i < 9; i++){
if (rcount[i] == 1){
for (int k = 0; k < 9; k++){
int x = xb + k % 3;
int y = yb + (int) k/3;
if (allowed[x][y][i]){
set_item(i+1, x, y);
}
}
res = true;
} // if rcount[i] == 1
} // for i
} // for yb
} // for xb
return res;
} // function
The last part looks really ugly - but it is not more complicated then the ones before.
Backtracking
With backtracking we can solve every Sudoku:
bool sudoku::backtrack(){
if (is_stuck()){
return false;
}
// cerr << "Recursion depth: " << recursion_depth << "\n";
for (int x = 0; x < 9; x++){
for (int y = 0; y < 9; y++){
if (data[x][y] == 0){
for (int i = 0; i < 9; i++){
if (allowed[x][y][i]){
sudoku tmp = *this;
tmp.set_item(i+1, x, y);
tmp.set_recursion_depth(recursion_depth + 1);
if (tmp.solve()){
*this = tmp;
return true;
}
}
}
return false;
}// if data == 0
} // for y
} // for x
return false;
}
Backtracking isn't difficult. The code may look a bit complex, so here is the algorithm in textual form:
- Search a place where there is no number entered yet.
- Search a number that could possibly fit.
- Copy the whole field and enter the number into the copy.
- Solve the copy (recursively).
- If solving doesn't work, use your original field (not the copy) and try the next number.
That's it.
Bringing it Together
Now all we need is a little function that calls the different solvers appropriately.
bool sudoku::solve(){
simple_solve();
if (is_stuck()){
return false;
}
if (is_solved()){
return true;
} else {
return backtrack();
}
}
bool sudoku::simple_solve(){
bool res = false;
bool flag = true;
while (flag){
flag = simple_solve1();
flag = simple_solve2() || flag;
if (flag){
res = true;
}
} // while
return res;
} // function
Generating Sudokus
Generating Sudokus is not an exact science. An easy way to generate Sudokus is the following:
- Chose a random place and a random number within the field.
- If it is possible to insert the number at the chosen place without immediate violation of Sudoku rules, do it.
- Repeat steps 1 and 2 until
k=26numbers are inserted. - Check if the resulting Sudoku has a uniq solution. If it has no solution at all, discard it and start with an empty field and step 1.
- If it has multiple solutions, repeat steps 1, 2 and 4.
- If it has exactly one solution, you are done.
Choosing the Parameter k
Choice of the parameter k has severely impact on
performance.
If you chose a small k<25 it takes long to generate
a Sudoku because you often have to check if a Sudoku has multiple
solutions. To do that, you have to use backtracking, which is slow
when there are not many Sudokus given.
If you chose a large k>35, the probability is high
to generate a Sudoku which has no solution at all. Therefore you have
to discard many solutions.
k=26 seems to be a good choice. On average 70 Sudokus
are discarded before a valid one is found, on my laptop that takes
about 26 milliseconds.
- Time needed to generate a Sudoku, in half logarithmic scale.
Speed
On my Notebook (with Pentium M 1.5 GHz) YasSS needs about 1.1 millisecond to solve a minimal Sudoku on average, and 80ms to generate a Sudoku.
Behaviour
Per default only the first solution is found,
if others should exist they are ignored. When the -c Option
is given, the number of solutions is printed.
Download
You can get the latest version here.
Older versions
Miscellaneous
If you start YasSS with an empty Sudoku it will print out the following Sudoku:
