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!
Close