C++ Sudoku Dancing Links Implementation Program By Naim Hashmi
//Naim Hashmi, 2014
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
class Sudoku{
private: // Dancing Links toroidal structures
class header;
class node{
public:
int row;
node * up, * down, * left, * right;
header * head;
};
class header : public node{
public:
int size;
bool visible;
header * left, * right;
};
int u, u2, u3, rowsNumber, columnsNumber, solutionsNumber, maxSolutionsNumber;
header * root;
vector<header> columns;
vector<vector<node> > rows;
vector<int> solutions;
public:
Sudoku(int dimension) :
u(dimension),
u2(u*u),
u3(u2*u2),
rowsNumber(u3*u2),
rows(rowsNumber, vector<node>(4, node())),
columnsNumber(u3*4+1),
columns(columnsNumber, header()),
solutions(u3, 0)
{ // create the 729x324 matrix
root = &(columns[u3*4]);
for (int i = 0; i < columnsNumber; i++) {
columns[i].up = &(columns[i]);
columns[i].down = &(columns[i]);
columns[i].left = &(columns[(i+columnsNumber-1)%columnsNumber]);
columns[i].right = &(columns[(i+1)%columnsNumber]);
columns[i].visible = true;
columns[i].size = 0;
}
for (int i = 0; i < rowsNumber; i++) {
int r = i/(u3), c = i%u3/u2, p = i%u2;
for (int j = 0; j < 4; j++) {
int columnIndex;
// http://www.stolaf.edu/people/hansonr/sudoku/exactcover.htm
switch (j){
case 0: // cell constraints
columnIndex = u3*j + r*u2+c;
break;
case 1: //row constraints
columnIndex = u3*j + r*u2+p;
break;
case 2: //column constraints
columnIndex = u3*j + c*u2+p;
break;
case 3: //block constraints
columnIndex = u3*j + (r/u*u+c/u)*u2+p;
break;
}
rows[i][j].row = i;
rows[i][j].left = &(rows[i][(j+3)%4]);
rows[i][j].right = &(rows[i][(j+1)%4]);
rows[i][j].down = rows[i][j].head = &(columns[columnIndex]);
rows[i][j].up = columns[columnIndex].up;
columns[columnIndex].up->down = columns[columnIndex].up = &(rows[i][j]);
columns[columnIndex].size++;
}
}
};
void print(int * s){
for (int i=0; i<u3; i++){
if (i!=0 && i%(u*u2)==0){
cout << "\n";
for (int j=0; j<u; j++){
for (int k=0; k<u*2+2*((j==0 || j==u-1) ? 1 : 2); k++) cout << "-";
if (j!=u-1) cout << "+";
}
}
if (i%u2==0) cout << "\n";
else if (i%u==0) cout << " \u007C ";
cout << s[i] << " ";
}
cout << "\n";
}
int solver(int * grid, int max=1, bool fill=true){
int i = 0;
solutionsNumber = 0;
maxSolutionsNumber = max;
for (int j = 0; j<u3; j++){
if (grid[j]) {
int rowIndex = j*u2+grid[j]-1;
if (rows[rowIndex][0].head->visible==false ||
rows[rowIndex][1].head->visible==false ||
rows[rowIndex][2].head->visible==false ||
rows[rowIndex][3].head->visible==false) {
return -1; // unvalid puzzle
break;
}
for (int k = 0; k<4; k++)
cover(rows[rowIndex][k].head);
solutions[i++] = rowIndex;
}
}
backtrack(i);
if (solutionsNumber==0) return 0;
if (fill)
for (int j=0; j<u3; j++)
grid[solutions[j]/u2] = solutions[j]%u2+1;
for (int j=i-1; j>=0; j--)
for (int k=3; k>=0; k--)
uncover(rows[solutions[j]][k].head);
return solutionsNumber;
}
int generator (int * grid, int numbers=-1, int limit=1000, int randomness = 100){
for (int i=0; i<u3; i++)
grid[i] = 0;
solver(grid);
srand((unsigned)time(0));
for (int i=0; i<randomness; i++){
int box = rand()%3, begin = rand()%3, end = rand()%3;
if (rand()%2==0){
for (int j=0; j<u2; j++){
int beginIndex = box*u2*u+begin*u2+j,
endIndex = box*u2*u+end*u2+j;
int t = grid[endIndex];
grid[endIndex] = grid[beginIndex];
grid[beginIndex] = t;
}
}else{
for (int j=0; j<u2; j++){
int beginIndex = box*u+j*u2+begin,
endIndex = box*u+j*u2+end;
int t = grid[endIndex];
grid[endIndex] = grid[beginIndex];
grid[beginIndex] = t;
}
}
}
if (numbers==-1) numbers = u3-u3/3;
for (int i=0; i<numbers; i++){
int t, r, c=0;
do{
if (c!=0) grid[r] = t;
r = rand()%u3;
t = grid[r];
grid[r] = 0;
if (++c>limit) break;
}while(solver(grid, 2, false)!=1);
}
}
private:
void cover(header *column){ // cover a column and its nodes' rows
column->visible = false;
column->right->left = column->left;
column->left->right = column->right;
for (node *i = column->down; i!=column; i=i->down){
for (node *j = i->right; j!=i; j=j->right) {
j->down->up = j->up;
j->up->down = j->down;
j->head->size--;
}
}
}
void uncover(header *column){ // uncover a column and its nodes' rows
column->visible = true;
for (node *i = column->up; i!=column; i=i->up){
for (node *j = i->left; j!=i; j=j->left) {
j->head->size++;
j->up->down = j;
j->down->up = j;
}
}
column->left->right = column;
column->right->left = column;
}
void backtrack(int i){
if (root->right == root) {
solutionsNumber++;
return;
}
header * column, * choosen = root->right;
for (column = root->right; column!=root; column=column->right) {
if (column->size < choosen->size)
choosen = column;
if (choosen->size==0) return;
}
cover(choosen);
for (node *row = choosen->down; row!=choosen && solutionsNumber<maxSolutionsNumber; row=row->down) {
if (solutionsNumber==0)
solutions[i] = row->row;
for (node *j = row->right; j!=row; j=j->right)
cover(j->head);
backtrack(i + 1);
for (node *j = row->left; j!=row; j=j->left)
uncover(j->head);
}
uncover(choosen);
}
};
int main(){
int empty[81] = {
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
};
int minusthree[81] = {
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 2, 3, 0, 0, 0, 7, 8, 0,
1, 0, 0, 4, 0, 6, 0, 0, 9,
9, 0, 0, 0, 5, 0, 0, 0, 4,
2, 0, 0, 0, 0, 0, 0, 0, 8,
0, 1, 0, 0, 0, 0, 0, 3, 0,
0, 0, 8, 0, 0, 0, 3, 0, 0,
0, 0, 0, 2, 0, 9, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0
};
int heart[81] = {
8, 7, 2, 0, 0, 9, 0, 0, 0,
0, 0, 0, 0, 3, 0, 4, 0, 0,
0, 0, 0, 0, 0, 1, 2, 0, 8,
0, 0, 9, 0, 0, 0, 0, 8, 0,
3, 0, 7, 0, 0, 0, 6, 0, 5,
0, 2, 0, 0, 0, 0, 1, 0, 0,
1, 0, 8, 2, 0, 0, 0, 0, 0,
0, 0, 5, 0, 9, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 9, 5, 3
};
clock_t begin, end;
begin = clock();
Sudoku sudoku(3);
cout << "Sudoku.solver\n";
sudoku.print(heart);
begin = clock();
cout << "Working.." << "\n";
int solutions = sudoku.solver(heart, 2);
end = clock();
sudoku.print(heart);
cout << solutions
<< " solutions. Solved in " << ((double)(end - begin)*1000)/CLOCKS_PER_SEC << "\n";
cout << "\n\nSudoku.generator\n";
int mysudoku[81];
begin = clock();
cout << "Working.." << "\n";
sudoku.generator(mysudoku);
end = clock();
sudoku.print(mysudoku);
cout << "Generated in " << ((double)(end - begin)*1000)/CLOCKS_PER_SEC << "\n";
begin = clock();
cout << "Working.." << "\n";
sudoku.solver(mysudoku);
end = clock();
sudoku.print(mysudoku);
cout << solutions
<< " solutions. Solved in " << ((double)(end - begin)*1000)/CLOCKS_PER_SEC << "\n";
}
