Sudoku Solver using Knuth's algorithmx

sudoku.cpp

//////////////////////////////////////////////////////////////////////////////
// Sudoku Solving using Knuth's algorithmX
// Author: Suthee, 2008
///////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <vector>

using namespace std;

///////////////////////////////////////////////////////////////////////////////

#define BORAD_BLOCK_SIZE	( 4 )
#define BOARD_SIZE			( BORAD_BLOCK_SIZE * BORAD_BLOCK_SIZE )
#define SUDOKU_CONTRAINTS	( 4 ) // This is a fixed value
#define MATRIX_SIZE			( BOARD_SIZE * BOARD_SIZE * SUDOKU_CONTRAINTS )
#define MAX_COLUMN_NODES	( BOARD_SIZE * BOARD_SIZE * BOARD_SIZE )

///////////////////////////////////////////////////////////////////////////////

class DancingList;
class DancingListNode;
class DancingMatrix;

///////////////////////////////////////////////////////////////////////////////

void ExactCoverSolver_RemoveColumnConstraints( DancingMatrix& matrix, DancingListNode* chooseRowNode, DancingList* constraints[], DancingListNode* removeNodes[], int* removeSize );
void DanceList_DecSize( DancingList* danceList );
void Matrix_DecSize( DancingMatrix* matrix );

///////////////////////////////////////////////////////////////////////////////
// Node Pools 
///////////////////////////////////////////////////////////////////////////////

enum CONSTRAINT_TYPE { ROW, COL, BLOCK, SQUARE };
static DancingListNode* NodePool;

static void InitDancingListNodePool( void );
static void DestroyDancingListNodePool( void );
static DancingListNode* GetDancingListNodeByType( CONSTRAINT_TYPE type, int row, int col, int val );

///////////////////////////////////////////////////////////////////////////////
// Dancing List Node
///////////////////////////////////////////////////////////////////////////////

class DancingListNode {
public:
	
	DancingListNode();
	DancingListNode( DancingList* h );
	DancingListNode( DancingList* h, int value );
	DancingListNode( int value  );
	
	// Add operations
	void AddLeft	( DancingListNode* newNode );
	void AddRight	( DancingListNode* newNode );
	void AddUp		( DancingListNode* newNode );
	void AddDown	( DancingListNode* newNode );

	// Remove operations
	void RemoveFromLeftRight();
	void RemoveFromUpDown();
	
	DancingListNode* 	right;
	DancingListNode* 	left;
	DancingListNode* 	up;
	DancingListNode* 	down;
	DancingList*		header;
	
	// For Debugging
	int item;
};

DancingListNode::DancingListNode(): header( NULL ) {
	right 	= this;
	left 	= this;
	up 		= this;
	down 	= this;
}

DancingListNode::DancingListNode( DancingList* h ): header( h ) {
	right 	= this;
	left 	= this;
	up 		= this;
	down 	= this;
}

DancingListNode::DancingListNode( DancingList* h, int value ): header( h ), item( value ) {
	right 	= this;
	left 	= this;
	up 		= this;
	down 	= this;
}

DancingListNode::DancingListNode( int value ): header( NULL ), item( value ) {
	right 	= this;
	left 	= this;
	up 		= this;
	down 	= this;
}

void DancingListNode::AddLeft( DancingListNode* newNode ) {
	left->right		= newNode;
	newNode->left	= left;
	left			= newNode;
	newNode->right	= this;
}
	
void DancingListNode::AddRight( DancingListNode* newNode ) {
	right->left		= newNode;
	newNode->right	= right;
	right			= newNode;
	newNode->left	= this;
}
	
void DancingListNode::AddUp( DancingListNode* newNode ) {
	up->down		= newNode;
	newNode->up		= up;
	up				= newNode;
	newNode->down	= this;
}
	
void DancingListNode::AddDown( DancingListNode* newNode ) {
	down->up		= newNode;
	newNode->down	= down;
	down			= newNode;
	newNode->up		= this;
}
	
void DancingListNode::RemoveFromLeftRight() {
	right->left		= left;
	left->right		= right;
	right			= this;
	left			= this;
}
	
void DancingListNode::RemoveFromUpDown() {
	up->down	= down;
	down->up	= up;
	up			= this;
	down		= this;
	//header->size--;
	DanceList_DecSize( header );
}

///////////////////////////////////////////////////////////////////////////////
// Dancing List
///////////////////////////////////////////////////////////////////////////////

class DancingList {
public:

	DancingList( DancingMatrix* matrix );
	DancingList( DancingMatrix* matrix, int id );
	virtual ~DancingList();

	void Remove();
	void AddNode( DancingListNode* newNode );
	
	inline bool IsEmpty() { return ( size <= 0 ); }
		
	DancingList*		next;
	DancingList*		prev;
	DancingListNode		sentinel;
	DancingMatrix*		header;
	
	int size;
	int index;
};

void DanceList_DecSize( DancingList* danceList )
{
	danceList->size--;
}

DancingList::DancingList( DancingMatrix* matrix ):size(0), header( matrix ) {
	next = this;
	prev = this;
	index = -1;
}

DancingList::DancingList( DancingMatrix* matrix, int id ):size(0), header( matrix ),index( id ) {
	next = this;
	prev = this;
}

DancingList::~DancingList() {
	DancingListNode* node;
	while ( size > 0 ) {
		node = sentinel.down;
		node->RemoveFromUpDown();
		//delete node;
	}
}

void DancingList::Remove() {
	prev->next = next;
	next->prev = prev;
	next = this;
	prev = this;

	Matrix_DecSize( header );
	//header->size--;
}

void DancingList::AddNode( DancingListNode* newNode ) {
	sentinel.AddUp( newNode );
	newNode->header = this;
	size++;
}

///////////////////////////////////////////////////////////////////////////////
// Dancing Matrix
///////////////////////////////////////////////////////////////////////////////

class DancingMatrix {
public:
	DancingMatrix();
	DancingMatrix( int numColumns );
	virtual ~DancingMatrix();

	inline bool IsEmpty() { return ( size <= 0 ); }
	
	void AddNewList( DancingList* newList );

	DancingList* GetSmallestList();
	DancingList* GetConstraintByIndex( int index );

	DancingList* GetRowConstraint	( int row, int val );
	DancingList* GetColConstraint	( int col, int val );
	DancingList* GetBlockConstraint	( int row, int col, int val );
	DancingList* GetSquareConstraint( int row, int col );
	
	// We organize constraint sets in this order: Row, Col, Block, Square
	DancingList* sentinel;
	int size;
};

void Matrix_DecSize( DancingMatrix* matrix )
{
	matrix->size--;
}

DancingMatrix::DancingMatrix(): size(0) {
	sentinel = new DancingList( this );
}
	
DancingMatrix::DancingMatrix( int numColumns ): size(0) {
	sentinel = new DancingList( this );
	size = 0;
	
	for ( int i = 0; i < numColumns; i++ ) {
		AddNewList( new DancingList( this, i ) );
	}
}

DancingMatrix::~DancingMatrix() {
	DancingList* list;
	if ( sentinel ) {
		while ( size > 0 ) {
			list = sentinel->next;
			list->Remove();
			delete list;
		}
	}
	free( sentinel );
}

void DancingMatrix::AddNewList( DancingList* newList ) {
	sentinel->prev->next = newList;
	newList->prev = sentinel->prev;
	sentinel->prev = newList;
	newList->next = sentinel;
	size++;
}

DancingList* DancingMatrix::GetSmallestList() {
	int minSize = MAX_COLUMN_NODES;
	DancingList* smallestList = NULL;
	
	if ( ! IsEmpty() ) {
		for ( DancingList* list = sentinel->next; list != sentinel; list = list->next ) {
			if ( minSize > list->size ) {
				minSize = list->size;
				smallestList = list;
			}
		}
	}
	
	return smallestList;
}
	
DancingList* DancingMatrix::GetConstraintByIndex( int index ) {
	int count = 0;
	DancingList* list = NULL;
	
	if ( ! IsEmpty() ) {
		list = sentinel->next;
		
		while ( count < index ) {
			list = list->next;
			count++;

			if ( count >= size ) {
				return NULL; // this is an index out of bound
			}
		}
	}
	return list;
}

DancingList* DancingMatrix::GetRowConstraint( int row, int val ) { 
	return GetConstraintByIndex( ( row * BOARD_SIZE ) + ( val - 1 ) );
}

DancingList* DancingMatrix::GetColConstraint( int col, int val ) {
	int offset = BOARD_SIZE * BOARD_SIZE;
	return GetConstraintByIndex( ( col * BOARD_SIZE ) + ( val - 1 ) + offset );
}

DancingList* DancingMatrix::GetBlockConstraint( int row, int col, int val ) {
	int offset = BOARD_SIZE * BOARD_SIZE * 2;
	int blockRow = row / BORAD_BLOCK_SIZE;
	int blockCol = col / BORAD_BLOCK_SIZE;
	return GetConstraintByIndex( ( ( blockRow * BORAD_BLOCK_SIZE + blockCol ) * BOARD_SIZE ) + ( val - 1 ) + offset );
}

DancingList* DancingMatrix::GetSquareConstraint( int row, int col ) {
	int offset = BOARD_SIZE * BOARD_SIZE * 3;
	return GetConstraintByIndex( ( row * BOARD_SIZE ) + col + offset );
}

///////////////////////////////////////////////////////////////////////////////
// Node allocator
///////////////////////////////////////////////////////////////////////////////

static void InitDancingListNodePool( void )
{
	NodePool = new DancingListNode[ MAX_COLUMN_NODES * SUDOKU_CONTRAINTS ];
}

static void DestroyDancingListNodePool( void )
{
	delete [] NodePool;
}

static DancingListNode* GetDancingListNodeByType( CONSTRAINT_TYPE type, int row, int col, int val )
{
	int index = ( MAX_COLUMN_NODES * type ) + ( ( ( row * BOARD_SIZE ) + col ) * BOARD_SIZE ) + ( val - 1 );
	return NodePool + index;
}

///////////////////////////////////////////////////////////////////////////////
// Convert Sudoku to ExactCover problem
///////////////////////////////////////////////////////////////////////////////

void Sudoku_ConvertBoardCharToInt( char charboard[BOARD_SIZE][BOARD_SIZE+1], int board[BOARD_SIZE][BOARD_SIZE] )
{
	char c;
	for ( int row = 0; row < BOARD_SIZE; ++row ) {
		for ( int col = 0; col < BOARD_SIZE; ++col ) {
			c = charboard[row][col];
			if ( c >= 'A' && c <= 'P' ) {
				board[row][col] = (int) ( c - 'A' ) + 1;
			} else {
				board[row][col] = 0;
			}
		}
	}
}

void Sudoku_PrintSolution( vector<int>& solution, int board[BOARD_SIZE][BOARD_SIZE] ) 
{
	// fill up a board yet
	int row;
	int col;

	for ( unsigned int i = 0; i < solution.size(); i++ ) {
		row = ( solution[ i ] & 0x0000FF00 ) >> 8;
		col = solution[ i ] & 0x000000FF;
		board[ row ][ col ] = ( solution[ i ] & 0x00FF0000 ) >> 16;
	}

	for ( row = 0; row < BOARD_SIZE; row++ ) {
		for ( col = 0; col < BOARD_SIZE; col++ ) {
			if ( board[ row ][ col ] == 0 ) {
				cout << "-";
			} else {
				cout << ( char ) ( board[ row ][ col ] + 64 );
			}
		}
		cout << endl;
	}
	cout << endl;
}

void Sudoku_CreateDancingMatrixFromSudoku( DancingMatrix& matrix, int board[BOARD_SIZE][BOARD_SIZE] ) 
{
	vector< DancingListNode* > partialSolution;

	for ( int row = 0; row < BOARD_SIZE; row++ ) {
		for ( int col = 0; col < BOARD_SIZE; col++ ) {
			for ( int val = 1; val <= BOARD_SIZE; val++ ) {
				
				int index = ( ( val & 0x000000FF ) << 16 ) | ( ( row & 0x000000FF ) << 8 ) | ( col & 0x000000FF );

				// Row constraints 
				//DancingListNode* node1 = new DancingListNode( index );
				DancingListNode* node1 = GetDancingListNodeByType( ROW, row, col, val );
				new ( node1 ) DancingListNode( index );
				matrix.GetRowConstraint( row, val )->AddNode( node1 );
				
				// Column constraints 
				//DancingListNode* node2 = new DancingListNode( index );
				DancingListNode* node2 = GetDancingListNodeByType( COL, row, col, val );
				new ( node2 ) DancingListNode( index );
				matrix.GetColConstraint( col, val )->AddNode( node2 );					
				
				// Block constraints 
				//DancingListNode* node3 = new DancingListNode( index );
				DancingListNode* node3 = GetDancingListNodeByType( BLOCK, row, col, val );
				new ( node3 ) DancingListNode( index );
				matrix.GetBlockConstraint( row, col, val )->AddNode( node3 );
				
				// Square constraints 
				//DancingListNode* node4 = new DancingListNode( index );
				DancingListNode* node4 = GetDancingListNodeByType( SQUARE, row, col, val );
				new ( node4 ) DancingListNode( index );
				matrix.GetSquareConstraint( row, col )->AddNode( node4 );
				
				// append all new nodes together
				node1->AddLeft( node2 );
				node1->AddLeft( node3 );
				node1->AddLeft( node4 );
				
				// save partial solution, we will remove them from matrix later
				if ( board[row][col] == val ) {
					partialSolution.push_back( node1 );
				}
			}
		}
	}

	// Now we remove column constraints
	DancingList* constraints[ SUDOKU_CONTRAINTS ];
	for ( unsigned int i = 0; i < partialSolution.size(); i++ ) {
		ExactCoverSolver_RemoveColumnConstraints( matrix, partialSolution.at( i ), constraints, NULL, NULL );
		memset( constraints, 0, sizeof( DancingList* ) );
	}
}

///////////////////////////////////////////////////////////////////////////////
// Algorithm X 
///////////////////////////////////////////////////////////////////////////////

// Remove each row node from its parents 
void ExactCoverSolver_RemoveRow( DancingListNode* rowNode ) 
{
	DancingListNode* curNode = rowNode;
	do {
		curNode->RemoveFromUpDown();
		curNode = curNode->right;
	} while ( curNode != rowNode );
}

// Remove a row from matrix ( Cover operation )
void ExactCoverSolver_RemoveColumnConstraints( DancingMatrix& matrix, DancingListNode* chooseRowNode, DancingList* constraints[], DancingListNode* removeNodes[], int* removeSize ) 
{
	// For each column in a choosing row
	int count = 0;
	DancingListNode* colNode = chooseRowNode;
	do {
		constraints[ count++ ] = colNode->header;
		colNode = colNode->right;
	} while ( colNode != chooseRowNode );

	// remove all rows from constraints columns
	count = 0;
	DancingList* colList;
	for ( int i = 0; i < SUDOKU_CONTRAINTS; ++i ) {
		colList = constraints[ i ];

		if ( colList->IsEmpty() ) {
			continue;
		}

		DancingListNode* rowNode = colList->sentinel.down;
		do {	
			DancingListNode* nextRowNode = rowNode->down;
			DancingListNode* curNode = rowNode;
			do {

				if ( count >= 201 )
				{
					int x = 1;
				}

				if ( removeNodes )
				{
					removeNodes[ count++ ] = curNode; // save remove node
				}

				curNode->RemoveFromUpDown();
				curNode = curNode->right;
			} while ( curNode != rowNode );

			rowNode = nextRowNode;
		} while ( rowNode != &( colList->sentinel ) );
	}

	if ( removeSize )
	{
		*removeSize = count;
	}

	// remove constraint columns
	for ( int i = 0; i < SUDOKU_CONTRAINTS; ++i ) {
		constraints[ i ]->Remove();
	}
}

void ExactCoverSolver_UndoRemoveColumnConstraints( DancingMatrix& matrix, DancingList* constraints[], DancingListNode* removeNodes[], int removeSize )
{
	// put constraints back
	for ( int i = 0; i < SUDOKU_CONTRAINTS; ++i ) {
		matrix.AddNewList( constraints[ i ] );
	}
				
	// put remove nodes back
	int i = 0;
	for ( int i = 0; i < removeSize; i++ ) {
		removeNodes[ i ]->header->AddNode( removeNodes[ i ] );
	}
}

void ExactCoverSolver_Solve( DancingMatrix& matrix, vector<int>& solution ) 
{
	if ( matrix.IsEmpty() ) {
		// Solution is found, Terminate
		return;
	} else {
		DancingList* chooseColList = matrix.GetSmallestList();
		
		DancingList*		constraints[ SUDOKU_CONTRAINTS ];
		DancingListNode*	removeNodes[ 250 ]; // Max num remove nodes is 220
		int					removeSize = 0;

		// choose a row
		for ( DancingListNode* chooseRowNode = chooseColList->sentinel.down; chooseRowNode != &( chooseColList->sentinel ); chooseRowNode = chooseRowNode->down ) {
			
			// Add to our solution
			solution.push_back( chooseRowNode->item );

			// Remove the choosen row ( Cover )
			ExactCoverSolver_RemoveColumnConstraints( matrix, chooseRowNode, constraints, removeNodes, &removeSize );

			// Solve a smaller matrix
			ExactCoverSolver_Solve( matrix, solution );

			if ( matrix.IsEmpty() ) {
				break; // there is a solution
			}
			
			// roll back
			solution.pop_back(); // remove partial solution
			ExactCoverSolver_UndoRemoveColumnConstraints( matrix, constraints, removeNodes, removeSize );

			memset( constraints, 0, sizeof( DancingList* ) );
			removeNodes[ 0 ] = NULL;
		}
	}
}

///////////////////////////////////////////////////////////////////////////////
// Main 
///////////////////////////////////////////////////////////////////////////////

int main( int argc, char** argv ) 
{
	//int board[4][4] = { { 0, 2, 3, 0 }, { 0, 0, 0, 2 }, { 1, 0, 0, 0 }, { 0, 3, 1, 0 } };
	//int board[9][9] = {	{ 0,2,6,5,0,0,0,9,0 }, { 5,0,0,0,7,9,0,0,4 }, { 3,0,0,0,1,0,0,0,0 },
	//					{ 6,0,0,0,0,0,8,0,7 }, { 0,7,5,0,2,0,0,1,0 }, { 0,1,0,0,0,0,4,0,0 },
	//					{ 0,0,0,3,0,8,9,0,2 }, { 7,0,0,0,6,0,0,4,0 }, { 0,3,0,2,0,0,1,0,0 } };
	
	//int board[9][9] = {	{ 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 } };

	// Read input
	char board44[16][17] = {	{ "--A----C-----O-I" }, 
								{ "-J--A-B-P-CGF-H-" },
								{ "--D--F-I-E----P-" },
								{ "-G-EL-H----M-J--" },
								{ "----E----C--G---" },
								{ "-I--K-GA-B---E-J" }, 
								{ "D-GP--J-F----A--" },
								{ "-E---C-B--DP--O-" },
								{ "E--F-M--D--L-K-A" },
								{ "-C--------O-I-L-" },
								{ "H-P-C--F-A--B---" },
								{ "---G-OD---J----H" }, 
								{ "K---J----H-A-P-L" }, 
								{ "--B--P--E--K--A-" },
								{ "-H--B--K--FI-C--" },
								{ "--F---C--D--H-N-" } };

	int			board[16][16];
	vector<int> solution;
	int			numInput;
	char		rowInput[ BOARD_SIZE + 1 ];

	solution.reserve( BOARD_SIZE * BOARD_SIZE );

	InitDancingListNodePool();

	scanf( "%d\n", &numInput );
	for ( int i = 0; i < numInput; i++ ) {
		
		// Read a board from input stream
		for ( int row = 0; row < BOARD_SIZE; row++ ) {
			scanf( "%s\n", rowInput );
			for ( int col = 0; col < BOARD_SIZE; col++ ) {
				if ( rowInput[ col ] >= 'A' && rowInput[ col ] <= 'P' ) {
					board[ row ][ col ] = (int) ( rowInput[ col ] - 'A' ) + 1;
				} else {
					board[ row ][ col ] = 0;
				}
			}
		}

		solution.clear();
		DancingMatrix matrix( MATRIX_SIZE );

		//Sudoku_ConvertBoardCharToInt( board44_2, board );
		Sudoku_CreateDancingMatrixFromSudoku( matrix, board );
		ExactCoverSolver_Solve( matrix, solution );

		Sudoku_PrintSolution( solution, board );
	}

	DestroyDancingListNodePool();

	return 0;
}