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:

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:

  1. Chose a random place and a random number within the field.
  2. If it is possible to insert the number at the chosen place without immediate violation of Sudoku rules, do it.
  3. Repeat steps 1 and 2 until k=26 numbers are inserted.
  4. 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.
  5. If it has multiple solutions, repeat steps 1, 2 and 4.
  6. 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, depending
		on the parameter k. In half logarithmic scale the curve
		resembles a parable with minimum at k=28 at t=0.026s. At k=20
		and k=35 the time is a few seconds.
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: