Solve The Eight Queens Puzzle - Step 4

◀ Solve The Eight Queens Puzzle - Step 3▶ Exercise #4: Word Ladder Game
Amazon Let’s run the last step of the Four-Step Programming Model to solve the eight queen's puzzle!

Four Step Programming Model: Step 4
While implementing it I realize board is used very often, so I just rename it to b for brevity. To make sure no repeated solutions are reported, I need to write transpose(), to transpose a board so that every column is switched with every corresponding row, and rotate90(), to rotate a board 90 degrees counterclockwise, to find every possible equivalent board configuration of a given one.

For example, the following two boards are considered equivalent, assuming the board size is 4:
*0123*
0X   0
1X   1
2X   2
3    3
*0123*

*0123*
0    0
1    1
2    2
3XXX 3
*0123*
Since the second board is the first board after rotating 90 degrees counterclockwise. transpose() is a no-brainer but rotate90() takes some skills, so code rotate90() by yourself to prove you are made of something, will you?

Here is the complete program:
/*
Michael Wen
6/8/2003
This program solves the classic eight queens\' puzzle.
*/
#include <iostream>
#include <vector>
using namespace std;

const int MAX = 8;
struct array {
	int arr[MAX][MAX];
};
int counter;
array b;
vector<array> va;

bool repeated();
void makeEqual(array&, array&);
bool operator==(array&, array&);
void transpose(array&);
void rotate90(array&);
void outputBoard();
void initArray(array&);
bool conflict();
void recur(int, int);

int main() {
	int cur;
	bool found;

	initArray(b);
	cur = MAX;
	found = false;
	counter = 1;
/* run the recursive function given the size of the board */
	recur(cur, -1);
	return 0;
}

/*
precondition: none
postcondition: return true if b is an orientation contained in va; b is not changed
*/
bool repeated() {
	int i;
	array tempa;
	makeEqual(tempa, b);
/* rotate and transpose each element in va and test if b matches any of it */
	for(i=0; i<va.size(); i++) {
		if(tempa==va[i])
			return true;
	}
	makeEqual(tempa, b);
	rotate90(tempa);
	for(i=0; i<va.size(); i++) {
		if(tempa==va[i])
			return true;
	}
	makeEqual(tempa, b);
	rotate90(tempa);
	rotate90(tempa);
	for(i=0; i<va.size(); i++) {
		if(tempa==va[i])
			return true;
	}
	makeEqual(tempa, b);
	rotate90(tempa);
	rotate90(tempa);
	rotate90(tempa);
	for(i=0; i<va.size(); i++) {
		if(tempa==va[i])
			return true;
	}
	makeEqual(tempa, b);
	transpose(tempa);
	for(i=0; i<va.size(); i++) {
		if(tempa==va[i])
			return true;
	}
	makeEqual(tempa, b);
	transpose(tempa);
	rotate90(tempa);
	for(i=0; i<va.size(); i++) {
		if(tempa==va[i])
			return true;
	}
	makeEqual(tempa, b);
	transpose(tempa);
	rotate90(tempa);	
	rotate90(tempa);
	for(i=0; i<va.size(); i++) {
		if(tempa==va[i])
			return true;
	}
	makeEqual(tempa, b);
	transpose(tempa);
	rotate90(tempa);
	rotate90(tempa);
	rotate90(tempa);
	for(i=0; i<va.size(); i++) {
		if(tempa==va[i])
			return true;	
	}
	return false;
}

/*
precondition: none
postcondition: equate b with a
*/
void makeEqual(array & a, array & b) {
	int i, i2;
	for(i=0; i<MAX; ++i)
		for(i2=0; i2<MAX; ++i2)
			a.arr[i][i2] = b.arr[i][i2];
}

/*
precondition: none
postcondition: return true if a contains identical elements as b
*/
bool operator==(array & a, array & b) {
	int i, i2;
	for(i=0; i<MAX; ++i)
		for(i2=0; i2<MAX; ++i2)
			if(a.arr[i][i2]!=b.arr[i][i2])
				return false;
	return true;
}

/*
precondition: none
postcondition: transpose a 
*/
void transpose(array & a) {
	array tempa;
	int r, c;
	
	initArray(tempa);	
	for(r=0; r<MAX; r++)
		for(c=0; c<MAX; c++)
			tempa.arr[r][c] = a.arr[c][r];
	makeEqual(a, tempa);
}

/*
precondition: none
postcondition: rotate a by 90 degrees counterclockwise
*/
void rotate90(array & a) {
	int r, c;
	bool found = false;
	array tempa;

	initArray(tempa);
	for(r=0; r<MAX; r++)
		for(c=0; c<MAX; c++)
			if(MAX-c-1>=0)
				tempa.arr[MAX-c-1][r] = a.arr[r][c];
	makeEqual(a, tempa);
}

/*
precondition: none
postcondition: output the board configuration represented by b
*/
void outputBoard() {
	int i, i2;
	cout << "*";
	for(i=0; i<MAX; i++) 
		cout << i;
	cout << "*\n";
	for(i=0; i<MAX; i++) {
		cout << i;
		for(i2=0; i2<MAX; i2++)
			if(b.arr[i][i2]==0)
				cout << \'X\';
			else
				cout << \' \';
		cout << i << endl;
	}
	cout << "*";
	for(i=0; i<MAX; i++) 
		cout << i;
	cout << "*\n";
}

/*
precondition: none
postcondition: each element in a is initialized to 1, meaning empty
*/
void initArray(array & a) {
	int i, i2;
	for(i=0; i<MAX; i++)
		for(i2=0; i2<MAX; i2++)
			a.arr[i][i2] = 1;
}

/*
precondition: none
postcondition: return true if there is conflict among the queens on b; return false otherwise
*/
bool conflict() {
	int i, i2, j, j2;
	for(i=0; i<MAX; i++)
		for(i2=0; i2<MAX; i2++)
			if(b.arr[i][i2]==0) {
/* vertical and horizontal */
				for(j=0; j<MAX; j++) {
					if(b.arr[j][i2]==0&&j!=i)
						return true;
					if(b.arr[i][j]==0&&j!=i2)
						return true;
				}
/* upper left to lower right */
				j = i-1;
				j2 = i2-1;
				while(j>=0 && j2>=0) {
					if(b.arr[j][j2]==0)
						return true;
					j--;
					j2--;
				}
				j = i+1;
				j2 = i2+1;
				while(j<MAX && j2<MAX) {
					if(b.arr[j][j2]==0)
						return true;
					j++;	
					j2++;
				}
/* upper right to lower left */
				j = i-1;
				j2 = i2+1;
				while(j>=0 && j2<MAX) {
					if(b.arr[j][j2]==0)
						return true;
					j--;
					j2++;
				}
				j = i+1;
				j2 = i2-1;
				while(j<MAX && j2>=0) {
					if(b.arr[j][j2]==0)
						return true;
					j++;
					j2--;
				}
			}
	return false;
}

/*
precondition: cur and ii should both contain positive values
postcondition: recursively find a board configuration where no two queens can attack each other
*/
void recur(int cur, int ii) {
/* if cur is 0 it is the base case */
	if(cur==0) {
/* if current solution is not repeated */
		if(!repeated()) {
/* put it in a vector */
			va.push_back(b);
			cout << "\nSolution: " << counter << endl;
			++counter;
/* output it onto screen */
			outputBoard();
		}
		return;
	}
	int i, i2;
/* loop through each position on the board starting from ii */
	for(i=ii+1; i<MAX; i++) {
		for(i2=0; i2<MAX; i2++) {
			if(b.arr[i][i2]==1) {
/* fill the position with a queen */
				b.arr[i][i2]=0;
/* if no queens are in conflict with one another */
				if(!conflict())
/* call recur() to place the next queen */
					recur(cur-1, i);
/* un-fill the position */
				b.arr[i][i2]=1;
			}
		}
	}
}
Congratulations if you worked this out by yourself. You’ve certainly gained more experience with writing recursive functions. Care to move on?

Next let’s write a program to solve the word ladder game!
◀ Solve The Eight Queens Puzzle - Step 3▶ Exercise #4: Word Ladder Game

fShare
Questions? Let me know!