Sudoku solver with Dancing links, by bbi5291

dlx.h

//The following code is based on the paper "Dancing Links" by D. E. Knuth.
//See http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
#ifndef DLX_H
#define DLX_H
#include <cstring>
#include <climits>
struct data_object //A module in the sparse matrix data structure.
{
	data_object* L;                //Link to next object left.
	data_object* R;                //         "          right.
	data_object* U;                //         "          up.
	data_object* D;                //         "          down.
	data_object* C;                //Link to column header.
	int x;                         //In a column header: number of ones 
                                       //in the column. Otherwise: row index.
	void cover()                   //Covers a column.
	{
		data_object *i, *j;
		R->L=L;
		L->R=R;
		for (i=D; i!=this; i=i->D)
		{
			for (j=i->R; j!=i; j=j->R)
			{
				j->D->U=j->U;
				j->U->D=j->D;
				j->C->x--;
			}
		}
	}
	void uncover()                 //Uncovers a column.
	{
		data_object *i, *j;
		for (i=U; i!=this; i=i->U)
		{
			for (j=i->L; j!=i; j=j->L)
			{
				j->C->x++;
				j->D->U=j;
				j->U->D=j;
			}
		}
		R->L=this;
		L->R=this;
	}
};
//Standard S-heuristic suggested in Knuth's paper: pick the column with the
//fewest ones. Takes the root of the sparse matrix structure as an argument; 
//returns a pointer to the column header with the fewest ones.
data_object* DLX_Knuth_S_heuristic(data_object* root)
{
	data_object *P, *res;
	int best=INT_MAX/2;
	for (P=root->R; P!=root; P=P->R)
	{
		if (P->x<best)
		{
			best=P->x;
			res=P;
		}
	}
	return res;
}
template <typename Func1,typename Func2>
/*
Actual recursive function implementing Knuth's Dancing Links method.
h is the root of the sparse matrix structure. 
O is the stack that will contain a list of rows used.
*/
void DLX_search(data_object* h,int k,int* O,Func1 send_row,
		Func2 choose_column)
{
	int i;
	data_object *r,*c,*j;
	if (h->R==h) //done - solution found
	{
		//send rows used in solution back...
		for (i=0; i<k; i++)
			send_row(O[i]);
		//-1 signifies end of solution
		send_row(-1);
		return;
	}
	//otherwise
	c=choose_column(h); //choose a column to cover
	c->cover();         //cover it
	for (r=c->D; r!=c; r=r->D)
	{
		O[k]=r->x;
		for (j=r->R; j!=r; j=j->R)
			j->C->cover();
		DLX_search(h,k+1,O,send_row,choose_column);
		//set r <- O[k], and c<- C[r], this is unnecessary
		for (j=r->L; j!=r; j=j->L)
			j->C->uncover();
	}
	c->uncover();
}
template <typename random_access_iterator,typename Func1,typename Func2>
/*
Meta-implementation of Knuth's Dancing Links method for finding solutions to
the exact cover problem.

PARAMETERS:
int rows: Number of rows in the matrix.
int cols: Number of columns in the matrix.
random_access_iterator buf: A random access iterator to ints (either 0 or
1), the entries of the matrix, in row major order.
Func1 send_row: A function object with return type void which takes as a
parameter the index of a row in a solution to the problem. (e.g. store it in 
a buffer or print it out) -1 signifies the end of a solution.
Func2 choose_column: A deterministic function object taking as a parameter a
data_object* (the root) and returning a data_object* (the header of the
column to choose.)
*/
void DLX_dancing_links(int rows,int cols,random_access_iterator buf,
			Func1 send_row,Func2 choose_column)
{
	//step 1: construct the linked-list structure.
	//We can do this by iterating through the rows and columns. Time is
	//linear in the number of entries (optimal).
	//Space used is linear in the number of columns + the number of rows
	// + the number of ones.
	int i,j;
	data_object* root=new data_object; //root
	data_object* P=root;               //left-right walker
	data_object* Q;                    //top-down walker
	//array of pointers to column headers
	data_object** walkers=new data_object*[cols];
	//auxiliary stack for recursion
	int* st=new int[rows];
	for (i=0; i<cols; i++)
	{
		//create a column header and L/R links
		(P->R=new data_object)->L=P;
		//store a pointer to the column header
		walkers[i]=Q=P=P->R;
		P->x=0; //reset popcount
		for (j=0; j<rows; j++)
			if (buf[i+cols*j]) //a 1 in the current location?
			{
				//create a data object and U/D links
				(Q->D=new data_object)->U=Q;
				Q=Q->D;  //advance pointer
				Q->C=P;  //link to the column header
				P->x++;  //increment popcount for this column
				Q->x=j;  //note the row number of this entry
			}
		Q->D=P; //complete the column
		P->U=Q;
	}
	P->R=root; //complete the column list
	root->L=P;
	//eliminate empty columns
	P=root;
	for (i=0; i<cols; i++)
	{
		P=P->R;
		if (!P->x)
		{
			P->L->R=P->R;
			P->R->L=P->L;
		}
	}
	//now construct the L/R links for the data objects.
	P=new data_object;
	for (i=0; i<rows; i++)
	{
		Q=P;
		for (j=0; j<cols; j++)
			if (buf[j+cols*i]) //a one
			{
				//in _this_ row...
				walkers[j]=walkers[j]->D;
				//create L/R links
				(Q->R=walkers[j])->L=Q;
				//advance pointer
				Q=Q->R;
			}
		if (Q==P) continue;
		Q->R=P->R;       //link it to the first one in this row.
		P->R->L=Q;       //link the first one to the last one.
	}
	delete P;                //P is no longer needed
	delete walkers;          //walkers are no longer needed
	//step 2: recursive algorithm
	DLX_search(root,0,st,send_row,choose_column);
	delete st;
	for (P=root->R; P!=root; )          //deallocate sparse matrix structure
	{
		for (Q=P->D; Q!=P; )
		{
			Q=Q->D;
			delete Q->U;
		}
		P=P->R;
		delete P->L;
	}
	delete root;
}

//If no heuristic is specified, Knuth's S heuristic is used - select the
//column with the fewest ones to minimize the breadth of the search tree.
template <typename random_access_iterator,typename Func1>
void DLX_dancing_links(int rows,int cols,random_access_iterator buf,Func1 send_row)
{
	DLX_dancing_links(rows,cols,buf,send_row,DLX_Knuth_S_heuristic);
}

#endif

input_example

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

sudoku.cpp

#include <iostream>
#include "dlx.h"
using namespace std;
#define block(r,c) (3*((r)/3)+((c)/3))
int cnt=0;
int grid[9][9];
void f(int x)
{
	int i;
	int c;
	int r;
	if (x+1) 
	{
		i=x%9; x/=9;
		c=x%9; r=x/9;
		grid[r][c]=i+1;
	}
	else
	{
		for (r=0; r<9; r++,putchar('\n'))
			for (c=0; c<9; c++)
				putchar(grid[r][c]+'0');
		printf("\n");
	}
}
int matrix[729][324];
void cover_col(int col)
{
	for (int row=0; row<729; row++)
		if (matrix[row][col])
		{
			matrix[row][col]=0;
			memset(matrix[row],0,sizeof(matrix[row]));
		}
}
void cover_row(int row)
{
	for (int col=0; col<324; col++)
		if (matrix[row][col])
		{
			matrix[row][col]=0;
			cover_col(col);
		}
}
int main()
{
	int row,r,c,i;
	char ch;
	for (row=0,r=0; r<9; r++)
		for (c=0; c<9; c++)
			for (i=0; i<9; i++,row++)
			{
				//uniqueness constraint
				matrix[row][r+9*c]=1;
				//row constraint
				matrix[row][81+i+9*r]=1;
				//column constraint
				matrix[row][162+i+9*c]=1;
				//block constraint
				matrix[row][243+i+9*block(r,c)]=1;
			}
	for (r=0; r<9; r++)
		for (c=0; c<9; c++)
		{
			scanf("%c",&ch);
			if (ch>='1'&&ch<='9') //known value
			{
				cover_row(81*r+9*c+ch-'1');
				grid[r][c]=ch-'0';
			}
			else if (ch!='.'&&ch!='0') //placeholder
			{
				c--;
				continue;
			}
		}
	putchar('\n');
	DLX_dancing_links(729,324,(int*)&matrix,f);
	return 0;
}

At first sight I see memory leak in your code.
`int* st=new int[rows];

...

delete st;`
And others...