Posts Tagged ‘ Sudoku

Yet another recursive Sudoku solver

I haven’t published in two years and all I post today in a lousy Sudoku solver. Not that building one was essentially difficult. I always do some puzzle-driven program when I’m bored and just to prove myself that I can shake boredom out of me, I’ve decided to code it, publish it, transform it into some kind of tutorial and finally put it to rest so I can find something more productive to do. Nothing revolutionary here and not the fastest one around (I didn’t check, but I’m pretty damn sure it’s not). But as usual, someone may find it useful.

This is a tutorial on making a recursive Sudoku solver. It will brute force every number from 1 to 9 on an empty cell, starting from the first cell, until all free cells are filled and the Sudoku is resolved. It is written in C++. It assumes that the starting grid is correct and will provide only one solution.

Let’s start.

Loading and storing the grid.

First we need some way to store our grid and parse it. A simple grid in a text file should do it.

6 . 5 . . 3 . 4 .
. . . 9 4 . 5 . .
. 2 . . 5 . . . 3
. 9 . 8 . . . . 6
. . . . . . . . .
2 . . . . 6 . 9 .
3 . . . 7 . . 2 .
. . 8 . 1 9 . . .
. 7 . 3 . . 8 . 4

I use dots to represent empty cells. White-space (either “space” or “line feed”) will be ignored by the parser.

// A simple data reader: ASCII-based data from 1 to 9, 
// white-space separated, up to v.size() characters
// (a Sudoku grid has 81 values). You can either put '0'
// or '.' to represent an empty cell.
istream& operator >> (istream& iss, vector<int>& v)
{
	for (int i=0; i < v.size(); i++)
	{
		char x;
		iss >> x;

		if (x == '.')
			v[i] = 0;
		else
			v[i] = (int)(x - '0');
	}

	return iss;
}

As you can see, I overload an operator to create a simple call from the file stream to the vector. We parse each item as a char. Then determine if the cell is busy or free and transform the value to 0 if it’s the latter.

You can simply create your data file and do:

#include <fstream>
#include <vector>

using namespace std;

vector<int> grid;
grid.resize(81);
ifstream file("data");
file >> grid;

and everything is stored in the vector.

Printing the grid isn’t necessary, but I develop almost exclusively on CLI so it’s always nice to have a function that dumps any array onto the terminal or file just to check out things.

Validation routines

I’ve decided that the easiest way to keep these routines short and simple is to separate the validation of unique values, in a line or box, from determining all the available positions each line or box has.

Whether it’s from horizontal lines, vertical lines or in boxes, uniq() is essentially a function that verifies whether or not a list has unique numbers.

A single function should be useful for all checks. A bitset is a wonderful tool in C++ for this kind of trick.

// Check if a vector has unique numbers
// (but ignore zeros)
bool uniq(const vector<int>& vect)
{
   bitset<9> mybits;

   for (int i=0; i<9; i++)
   {
      int val = vect[i];

      // If value is 0 (empty), ignore
      if (val)
      {
         // If number is already found in the vector, 
         // the uniqueness test failed.
         if (mybits.test(val-1))
            return false;

         // Set number (base-0)
         mybits.set(val-1);
      }
   }

   return true;
}

Next, a generic function that will provide the vector for the above function is built. Note that this function doesn’t care if the check is horizontal or vertical or box bound, it will accept a group of positions, gather all values from those positions, and submit them to the uniq() function.

// Given a vector of grid positions, store their values 
// in a vector and check if they are unique.
bool Check(vector<int> pos)
{
	vector<int> vect;

	for (int i=0; i<pos.size(); i++)
		vect.push_back(grid[pos[i]]);

	return uniq(vect);
}

Naturally, the Check() function will be called by specific functions that deal with horizontal and vertical lines and boxes. These will group positions according to the current cell.

// Check the values of the row where <i> is located.
bool CheckHorz(int i)
{
	int j = i/9*9;	// row starting at no. j
	int k = j+9;	// row ending at no. k

	vector<int> pos;

	while (j < k)
		pos.push_back(j++);

	return Check(pos);
}

// Check the values of the column where <i> is located.
bool CheckVert(int i)
{
	int j = i%9;	// column starting at no. j

	vector<int> pos;

	while (j < MAX)
	{
		pos.push_back(j);
		j+=9;
	}

	return Check(pos);
}

As you can see, horizontal and vertical positions are trivial to calculate. The box-bound positions need a little help on this matter. I tried fantastical algorithms to offset small boxes around the grid, but a good old stencil is the best way to create an error-free list.

vector<int> boxes {

	0, 0, 0, 1, 1, 1, 2, 2, 2,
	0, 0, 0, 1, 1, 1, 2, 2, 2,
	0, 0, 0, 1, 1, 1, 2, 2, 2,
	3, 3, 3, 4, 4, 4, 5, 5, 5,
	3, 3, 3, 4, 4, 4, 5, 5, 5,
	3, 3, 3, 4, 4, 4, 5, 5, 5,
	6, 6, 6, 7, 7, 7, 8, 8, 8,
	6, 6, 6, 7, 7, 7, 8, 8, 8,
	6, 6, 6, 7, 7, 7, 8, 8, 8,
};

// Check the values of the box where <i> is located.
bool CheckBox(int i)
{
	int box = boxes[i];		// Get box no. at location i
	vector<int> pos;

	for (int j=0; j<MAX; j++)
	{
		if (box == boxes[j])
			pos.push_back(j);
	}

	return Check(pos);
}

Yes, I could have hard-coded the actual positions of each box into the grid and avoid the extra 72 iterations each time. But this is a nice visual presentation of the problem. Feel free to change this when you will be bored. 🙂

Solving the grid

Solving the grid is just a matter of jumping onto a cell, set the value to 1, check if it passes the three tests above and then go to the next cell – or simply change the current value to the next one in line and test again. If it still fails, this means that some of the numbers we set on previous cells are incorrect, we need to go back one step, change to the next value, come back and start again with new values. We can also go back all the way to the beginning if we have to and change the first number we put on cell 0 in order to solve the puzzle. If the current cell already has a value, one that was assigned by the original puzzle, then we jump to the next cell without hesitation.

void Solve(int i)
{
	// If we reach this, the Sudoku is solved.
	if (i == MAX)
	{
		PrintGrid(grid);
		exit(0);
	}

	// If cell already has a value, go to next cell
	if (grid[i])
		Solve(i+1);
	else
	{
		// We will iterate through all numbers and
		// set the current grid with this value.
		// If it passes all tests, we will go to 
		// the next cell.
		// If not, we simply set the cell back to <empty> and
		// go back to the previous cell.
		for (int j=1; j<=9; j++)
		{
			grid[i] = j;

			if (CheckBox(i) && CheckVert(i) && CheckHorz(i))
				Solve(i+1);
		}

		// Set to empty.
		grid[i] = 0;
	}
}

Once the supplied parameter reaches the magic number of MAX (or 81), then the Sudoku is solved. Print and abort. Mission accomplished.

Here’s the answer to the above grid, BTW:

6 1 5 7 8 3 2 4 9 
7 8 3 9 4 2 5 6 1 
4 2 9 6 5 1 7 8 3 
1 9 4 8 2 7 3 5 6 
8 3 6 5 9 4 1 7 2 
2 5 7 1 3 6 4 9 8 
3 6 1 4 7 8 9 2 5 
5 4 8 2 1 9 6 3 7 
9 7 2 3 6 5 8 1 4

Complete code here.

Happy Hacking.

return top