Draught Puzzle Solver in C (Source Code Included)

Amazon This puzzle is also know as octogram puzzle. You have 13 or 15 pieces of pieces and you are asked to arrange them on a square chessboard in such a way that they form a perfect chessboard, or known as draught or checkers board.

This is actually a type of jigsaw puzzle as you are putting all the pieces together to complete the mission. You'd think there might only be one single solution that exists, but that is NOT true!

Here I actually walk you through solving the draught puzzle in C++. To save you trouble I also included the source code below. Scroll down to see it.

This is actually a class assignment which asks us to find at least one solution under two hours. I wrote this program in C.

The way the program works is it uses recursion to try and place each piece onto the chessboard in any way possible. It first tries the first piece in some orientation and position, then the 2nd piece in some orientation and position, and so on until it leads to a dead end.

Then it tries another orientation or position of the last placed piece, and if it fails again it'll keep trying until all possible orientations and positions run out. Then it removes that piece and try the previously placed piece in different orientation and position. So on and so forth until it finds a solution. I enhanced the program so that it continues finding unique solutions and can stop anytime and pick up from where it left off next time it runs because I was so determined to find the total number of unique solutions, which I believe nobody has yet to find.

I ran the program for many hours a day for several days and got more than 16,000 unique solutions! They are unique because no matter how you rotate or transpose them they are different. I discard duplicates.

Here are two of the solutions I've found:

Solution #16008
**********
*KKKLCCEE*
*KGKLCCED*
*GGGLLEED*
*GHHHLJDD*
*BIHMJJJD*
*BIHMMJFF*
*BIIIMMFF*
*BBAAAAAF*
**********
223887 seconds

Solution #16009
**********
*KKKLCCEE*
*KMKLCCEI*
*AMMLLEEI*
*AGMMLIII*
*AGGGBBBB*
*AHGJBFFF*
*AHJJJDFF*
*HHHJDDDD*
**********
223892 seconds 

Let me share the source code with you, but if you want to improve your programming skills you should work on it yourself.

#include <iostream>
#include <vector>
#include <fstream>
#include <time.h>
#include <string>
using namespace std;

const int numPieces = 13;
const int numTrans = 8;
const int numRows = 5;
const int numCols = 5;
const int boardWidth = 10;
const int boardHeight = 10;

clock_t start = clock();
char board[boardHeight][boardWidth];

struct array {
	char acc[numRows][numCols];
};

void outputBoard();
void init(char[numRows][numCols]);
bool allUnprintable(string s);
void setEqual(char[numRows][numCols], char[numRows][numCols]);
bool sameArray(array, char[numRows][numCols]);
bool repeated(vector<array>, char[numRows][numCols]);
void arrayInit(array&, char[numRows][numCols]);
bool impasse(char[boardHeight][boardWidth]);
void solve(int);

class Trans {
public:
	char pattern[numRows][numCols];
	char id;
	Trans();
	Trans(char[numRows][numCols]);
	bool place(int, int);
	void clear();
};
/*
precondition: none
postcondition: default constructor
*/
Trans::Trans() {
	init(pattern);
	id = \'@\';
}
/*
precondition: cc should contain the pattern
postcondition: assign proper values to pattern[][] and id
*/
Trans::Trans(char cc[numRows][numCols]) {
	int r, c;
	for(r=0; r<numRows; r++)
		for(c=0; c<numCols; c++) {
			if(cc[r][c]!=\' \')
				id = cc[r][c];
			pattern[r][c] = cc[r][c];
		}
}
/*
precondition: r and c must be >= 0
postcondition: do nothing and return false if the invoking pattern doesn\'t fit in the given position; place the invoking pattern in the given location and return true if the invoking pattern fits
*/
bool Trans::place(int r, int c) {
    int rr, cc;
    for(rr=0; rr<numRows; rr++)
		for(cc=0; cc<numCols; cc++)
	    	if(pattern[rr][cc] != \' \') 
				if(rr+r>8 || cc+c>8 || board[rr+r][cc+c]!=\' \')
					return false;
	for(rr=0; rr<numRows; rr++)
		for(cc=0; cc<numCols; cc++)
	    	if(pattern[rr][cc] != \' \') 
	   			board[rr+r][cc+c] = pattern[rr][cc];
    return true;
}
/*
precondition: none
postcondition: clear out the spots occupied by the invoking pattern 
*/
void Trans::clear() {
	int r, c, i = 0;
	for(r=boardHeight-1; r>=0; r--)
		for(c=boardWidth-1; c>=0; c--)
			if (board[r][c]==id) {
				board[r][c] = \' \';
				if(++i==numRows)
					return;
			}
}
 
class Piece {
public:
	Trans *patterns[numTrans];
	int count;
	Piece();
	Piece(char[numRows][numCols]);
	void transpose(char[numRows][numCols]);
	void rotate90(char[numRows][numCols]);
};

Piece *pieces[numPieces];

/*
precondition: none
postcondition: default constructor
*/
Piece::Piece() {
	int i;
	for(i=0; i<numTrans; i++)
		patterns[i] = NULL;
	count = -1;
}
/*
precondition: cc should contain the pattern
postcondition: find and store all orientations of the pattern in Trans
*/
Piece::Piece(char cc[numRows][numCols]) {
	int i, currIndex;
	vector<array> va;
	array ar;
	va.clear();
	arrayInit(ar, cc);
	va.push_back(ar);
	patterns[0] = new Trans(cc);
	currIndex = 1;
	for(i=0; i<3; i++) {
		rotate90(cc);
		if(!repeated(va, cc)) {
			arrayInit(ar, cc);
			va.push_back(ar);
			patterns[currIndex] = new Trans(cc);

			++currIndex;
		}
	}
	rotate90(cc);
	transpose(cc);
	if(!repeated(va, cc)) {
		arrayInit(ar, cc);
		va.push_back(ar);
		patterns[currIndex] = new Trans(cc);
		++currIndex;
	}
	for(i=0; i<3; i++) {
		rotate90(cc);
		if(!repeated(va, cc)) {
			arrayInit(ar, cc);
			va.push_back(ar);
			patterns[currIndex] = new Trans(cc);
			++currIndex;
		}
	}
	count = currIndex;
}
/*
precondition: cc may contain anything
postcondition: transpose the pattern in cc
*/
void Piece::transpose(char cc[numRows][numCols]) {
    char tempcc[numRows][numCols];
    int r, c;
    init(tempcc);    
    for(r=0; r<numRows; r++)
        for(c=0; c<numCols; c++)
            tempcc[r][c] = cc[c][r];
    setEqual(cc, tempcc);
}
/*
precondition: cc may contain anything
postcondition: rotate the pattern in cc by 90 degrees counterclockwise
*/
void Piece::rotate90(char cc[numRows][numCols]) {
	int r, c, offset;
	bool found = false;
	char tempcc[numRows][numCols];
	offset = -1;
	for(c=numCols-1; c>=0 && !found; c--)
		for(r=numRows-1; r>=0; r--)
			if(cc[r][c]!=\' \') {
				offset = numCols - c - 1;
				found = true;
				break;
			}
	if(offset==-1)
		return;
	init(tempcc);
	for(r=0; r<numRows; r++)
		for(c=0; c<numCols; c++)
			if(numCols-c-1-offset>=0 && cc[r][c]!=\' \')
				tempcc[numCols-c-1-offset][r] = cc[r][c];
	setEqual(cc, tempcc);
}
int main(int argc, char **argv) {
	if(argc!=2) {
		cout << 'usage: <exe> <file>
';
		cout << '<exe>: the executable of the program
';
		cout << '<file>: the file that contains all pieces
';
		exit(1);
	}

	int i, r, c;
	ifstream fin;
	char tempcc[numRows][numCols], letter;
	string temps;
	fin.open(argv[1]);
	if(!fin.is_open()) {
		cout << argv[1] << ' cannot be opened, forced exit
';
		exit(2);
	}
	init(tempcc);
	letter = \'A\';
	for(i=0; i<numPieces; i++) {
		r = 0;
		while(true) {
			getline(fin, temps, \'
\');
			if(!fin)
				break;
			if(allUnprintable(temps))
				break;
			for (c=0; c<numCols; c++) {
				if(temps[c]==\'\')
					break;
	    		else if(temps[c]==\'#\')
	    			tempcc[r][c] = letter;
			}
			r++;
		}
		pieces[i] = new Piece(tempcc);
		init(tempcc);
		letter++;
	}
fin.close();
	for(r=0; r<boardHeight; r++)
	    for (c=0; c<boardWidth; c++)
	        board[r][c] = \' \';

	for(c=0; c<boardWidth; c++) {
	    board[0][c] = \'*\';
	    board[boardHeight-1][c] = \'*\';
    }
	for(r=1; r<boardHeight-1; r++) {
		board[r][0] = \'*\';
		board[r][boardWidth-1] = \'*\';
	}
	solve(0);
	return 0;
}

/*
precondition: none
postcondition: displays the current board onscreen
*/
void outputBoard() {
	int r, c;
    for(r=0; r<boardHeight; r++) {
		for(c=0; c<boardWidth; c++)
	    	cout << board[r][c];
    	cout << endl;
    }
}
/*
precondition: none
postcondition: make every element in the array a space
*/
void init(char cc[numRows][numCols]) {
	int r, c;
	for(r=0; r<numRows; r++)
		for(c=0; c<numCols; c++)
			cc[r][c] = \' \';
}
/*
precondition: none
postcondition: return true if s doesn\'t contain \'#\'; return false otherwise
*/
bool allUnprintable(string s) {
	int i;
	for(i=0; i<s.length(); i++)
		if(s[i]==\'#\')
	    	return false;
    return true;
}
/*
precondition: none
postcondition: set the contents of cc equal to those of cc2
*/
void setEqual(char cc[numRows][numCols], char cc2[numRows][numCols]) {
	int r, c;
	for(r=0; r<numRows; r++)
		for(c=0; c<numCols; c++) 
			cc[r][c] = cc2[r][c];
}
/*
precondition: none
postcondition: return true if the contents of a are identical to cc; return false otherwise
*/
bool sameArray(array a, char cc[numRows][numCols]) {
	int r, c;
	for(r=0; r<numRows; r++)
		for(c=0; c<numCols; c++) 
			if(a.acc[r][c]!=cc[r][c])
				return false;
	return true;
}
/*
precondition: none
postcondition: return true if cc exists in va; return false otherwise
*/
bool repeated(vector<array> va, char cc[numRows][numCols]) {
	int i;
	for(i=0; i<va.size(); i++)
		if(sameArray(va[i], cc))
			return true;
	return false;
}
/*
precondition: none
postcondition: make the contents of ar equal to cc
*/
void arrayInit(array & ar, char cc[numRows][numCols]) {
	int r, c;
	for(r=0; r<numRows; r++)
		for(c=0; c<numCols; c++)
			ar.acc[r][c] = cc[r][c];
}
/*
precondition: boardHeight and boardWidth must both be 10
postcondition: return true if current board must lead to an impasse; return false otherwise
*/
bool impasse(char b[boardHeight][boardWidth]) {
  for (int i = 1; i < 9; i++) {
	for (int j = 1; j < 9; j++) {
//cases where there\'s one unfillable pocket
 	    if (b[i-1][j]!=\' \'&&b[i][j-1]!=\' \'&&b[i][j+1]!=\' \'&&b[i+1][j]!=\' \')
		if (b[i][j] == \' \')
		    return true;

//cases where there\'s two unfillable pockets, horizontally
	    if (j < 8)
		if (b[i-1][j]!=\' \'&&b[i-1][j+1]!=\' \'&&b[i][j+2]!=\' \'&&b[i+1][j+1]!=\' \'
		    	&&b[i+1][j]!=\' \'&&b[i][j-1]!=\' \')
		    	if (b[i][j]==\' \'&&b[i][j+1]==\' \')
					return true;

//cases where there\'s three unfillable pockets, horizontally
	    if (j < 7)
		if (b[i-1][j]!=\' \'&&b[i-1][j+1]!=\' \'&&b[i-1][j+2]!=\' \'&&b[i][j+3]!=\' \'
		    &&b[i+1][j+2]!=\' \'&&b[i+1][j+1]!=\' \'&&b[i+1][j]!=\' \'&&b[i][j-1]!=\' \')
		    	if (b[i][j]==\' \'&&b[i][j+1]==\' \'&&b[i][j+2]==\' \')
					return true;

//cases where there\'s four unfillable pockets, horizontally
	    if (j < 6)
		if (b[i-1][j]!=\' \'&&b[i-1][j+1]!=\' \'&&b[i-1][j+2]!=\' \'&&b[i-1][j+3]!=\' \'
		    &&b[i][j+4]!=\' \'&&b[i+1][j+3]!=\' \'&&b[i+1][j+2]!=\' \'&&b[i+1][j+1]!=\' \'
		    &&b[i+1][j]!=\' \'&&b[i][j-1]!=\' \')
		    	if (b[i][j]==\' \'&&b[i][j+1]==\' \'&&b[i][j+2]==\' \'&&b[i][j+3]==\' \')
					return true;

//cases where there\'s two unfillable pockets, vertically
	    if (i < 8)
		if (b[i-1][j]!=\' \'&&b[i][j+1]!=\' \'&&b[i+1][j+1]!=\' \'&&b[i+2][j]!=\' \'
		    	&&b[i][j-1]!=\' \'&&b[i+1][j-1]!=\' \')
		    	if (b[i][j]==\' \'&&b[i+1][j]==\' \')
					return true;

//cases where there\'s three unfillable pockets, vertically
	    if (i < 7)
		if (b[i-1][j]!=\' \'&&b[i][j+1]!=\' \'&&b[i+1][j+1]!=\' \'&&b[i+2][j+1]!=\' \'
		    &&b[i+3][j]!=\' \'&&b[i][j-1]!=\' \'&&b[i+1][j-1]!=\' \'&&b[i+2][j-1]!=\' \')
		    	if (b[i][j]==\' \'&&b[i+1][j]==\' \'&&b[i+2][j]==\' \')
					return true;

//cases where there\'s four unfillable pockets, vertically
	    if (i < 6)
		if (b[i-1][j]!=\' \'&&b[i][j+1]!=\' \'&&b[i+1][j+1]!=\' \'&&b[i+2][j+1]!=\' \'
		    &&b[i+3][j+1]!=\' \'&&b[i+4][j]!=\' \'&&b[i][j-1]!=\' \'&&b[i+1][j-1]!=\' \'
		    &&b[i+2][j-1]!=\' \'&&b[i+3][j-1]!=\' \')
		    	if (b[i][j]==\' \'&&b[i+1][j]==\' \'&&b[i+2][j]==\' \'&&b[i+3][j]==\' \')
					return true;
	}
  }
  return false;
}
/*
precondition: n must be initially 0
postcondition: searches and displays solutions until all solutions are found
*/
void solve(int n) {
if (n==numPieces) {
		outputBoard();
		cout << (float)(clock() - start) / CLOCKS_PER_SEC << ' seconds' 				<< endl;
		return;
}
    Piece* temp = pieces[n];
    int r, c, counter;
   	for (counter=0; counter<temp->count; ++counter)  
		for (r=1; r<boardHeight-1; r++)
	    	for (c=1; c<boardWidth-1; c++)
		    	if (temp->patterns[counter]->place(r, c)) {
		        	if (!impasse(board))
			    	solve(n+1);
		        	temp->patterns[counter]->clear();	
		    	}
}

I thought only a couple of solutions existed because it seems so difficult to find one.

Enjoy solving the draught or octogram puzzle!