Solving Draught Puzzle - Step 4

◀ Solving Draught Puzzle - Step 3▶ Solving Draught Puzzle - FAQ Amazon Let’s apply the last step of the Four-Step Programming Model to solve the Draught puzzle!

Four Step Programming Model: Step 4
Let me show you my program before I explain any part of it. You'll find many answers in the next section!

#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>\n";
		cout << "<exe>: the executable of the program\n";
		cout << "<file>: the file that contains all pieces\n";
		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\n";
		exit(2);
	}
	init(tempcc);
	letter = 'A';
	for(i=0; i<numPieces; i++) {
		r = 0;
		while(true) {
			getline(fin, temps, '\n');
			if(!fin)
				break;
			if(allUnprintable(temps))
				break;
			for (c=0; c<numCols; c++) {
				if(temps[c]=='\0')
					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();	
		    	}
}

This is a rather large program, and there are several parts that need more clarifications. Some of you may understand the program completely, while some of you might understand most of it but need help with a part of it.

I know some of you may have questions. So I've compiled a list of questions and answers next!◀ Solving Draught Puzzle - Step 3▶ Solving Draught Puzzle - FAQ