Saturday, October 28, 2006

Just Another Sudoku Solver (C++)

Closing this topic, here is the sourcecode of the C++ Sudoku Solver (originally in Java). Remember that this a template class, so all this code has to go to a header file. All allocation actions should be the same as under Java - which is important for runtime behavior comparison.

I coded this last night between 1am and 2am in the morning, so please don't shoot me in case of any mistakes ;-).

#pragma once
#include <vector>
#include <math.h>

template<int D> class Sudoku
{

public:

Sudoku(int _startGrid[D][D])
{
solutions = new std::vector<int(*)[D]>();
dimSqrt = (int)sqrt((double)D);
for (int x = 0; x < D; x++) {
for (int y = 0; y < D; y++) {
squareIdx[x][y] =
(x / dimSqrt) * dimSqrt + (y / dimSqrt);
}
}

copyGrid(_startGrid, startGrid);
}

virtual ~Sudoku() {
for (std::vector<int(*)[D]>::iterator it =
solutions->begin(); it != solutions->end(); it++) {
delete[] *it;
}
delete solutions;
}

std::vector<int(*)[D]>* solve() {
for (std::vector<int(*)[D]>::iterator it =
solutions->begin(); it != solutions->end(); it++) {
delete[] *it;
}
solutions->clear();
copyGrid(startGrid, grid);
for (int i = 0; i < D; i++) {
for (int j = 0; j < D; j++) {
usedInRow[i][j] = false;
usedInColumn[i][j] = false;
usedInSquare[i][j] = false;
}
}
for (int x = 0; x < D; x++) {
for (int y = 0; y < D; y++) {
int val = grid[x][y];
if (val != 0) {
usedInRow[x][val - 1] = true;
usedInColumn[y][val - 1] = true;
usedInSquare[squareIdx[x][y]][val - 1] = true;
}
}
}

digInto(0, 0);
return solutions;
}

private:

void copyGrid(int src[D][D], int tgt[D][D]) {
for (int x = 0; x < D; x++) {
// for compatibility reasons with java we
// copy one-dimensional arrays only
memcpy(tgt[x], src[x], D * sizeof(int));
}
};

void digInto(int x, int y) {
if (startGrid[x][y] == 0) {
int square = squareIdx[x][y];

for (int val = 1; val <= D; val++) {
int valIdx = val - 1;
if (usedInRow[x][valIdx] || usedInColumn[y][valIdx] ||
usedInSquare[square][valIdx]) {
continue;
}
grid[x][y] = val;
usedInRow[x][valIdx] = true;
usedInColumn[y][valIdx] = true;
usedInSquare[square][valIdx] = true;
if (x < D - 1) {
digInto(x + 1, y);
}
else if (y < D - 1) {
digInto(0, y + 1);
}
else {
addSolution();
}
grid[x][y] = 0;
usedInRow[x][valIdx] = false;
usedInColumn[y][valIdx] = false;
usedInSquare[square][valIdx] = false;
}

}
else {
if (x < D - 1) {
digInto(x + 1, y);
}
else if (y < D - 1) {
digInto(0, y + 1);
}
else {
addSolution();
}
}
};

void addSolution() {
int (*solution)[D] = new int[D][D];
copyGrid(grid, solution);
solutions->push_back(solution);
};

int startGrid[D][D];
int grid[D][D];
int dimSqrt;
std::vector<int(*)[D]>* solutions;
bool usedInColumn[D][D];
bool usedInRow[D][D];
bool usedInSquare[D][D];
int squareIdx[D][D];

};

Previos Posts:

Follow-Ups: