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