This code snippet is from a program we had to create during our AI class, that solved a Sudoku puzzle
void set(uint l, uint c, uint val)
{
// Sets the cell at line l and row c to hold the value val
if (isValidPos(l, c) && ((0 < val) && (val <= MAXVAL)))
{
if (table[l * C + c] == 0) ++filledIn;
table[l * C + c] = val;
for (uint i = 0; i < C; ++i) // Update lines
usedDigits[lineElements[l][i]] |= 1< 0)
++d;
set(i / C, i % C, d); // Fill it in
changed = true; // The board has been changed so this step must be rerun
}
else if (bitcount(usedDigits[i]) == MAXVAL)
throw 666; // Speed boost
}
}
void goBruteForce()
{
int max(-1); // Find the cell with the _minimum_ number of posibilities (i.e. the one with the largest number of /used/ digits)
for (uint i(0); i < S; ++i)
if (table[i] == 0) // Is there a digit already written?
if ((max == -1) || (bitcount(usedDigits[i]) > bitcount(usedDigits[max])))
max = i;
if (max != -1)
{
for (uint i(1); i <= MAXVAL; ++i) // Go through each possible digit
if ((usedDigits[max] & 1<
{
// If it can be placed in this cell, do
SudokuBoard temp(*this); // Create a new board
temp.set(max / C, max % C, i); // Complete the attempt
temp.solve(); // Solve it
if (temp.getFilledIn() == S)
{
// If the board was completely solved (i.e. the number of filled in cells is S)
for (uint j(0); j < S; ++j) // Copy the board into this one
set(j / C, j % C, temp.at(j / C, j % C));
return; // Break the recursive cascade
}
}
}
}