Solve The Eight Queens Puzzle - Step 1

◀ Exercise #3: Solve The Eight Queens Puzzle▶ Solve The Eight Queens Puzzle - Step 2 Amazon Let’s run the 1st step of the Four-Step Programming Model to solve the eight queen's puzzle!

Four Step Programming Model: Step 1
The idea is to use recursion to find a board configuration where no two queens can attack each other. We put one queen somewhere, check if the board is okay; if it is okay put the next queen; if it is not okay we put the queen somewhere else. We go on until we reach a solution, in which case we check whether it is repeated or not. We output it if it is not repeated. We try to find the next solution until we try every possible configuration of the board. Here is my pseudo-code of the program:

void recur(int cur);
bool repeated();
bool conflict();

int main(int argc, char **argv) {
- run the recursive function given the size of the board
}

/*
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){
- if cur is 0 it is the base case
	if current solution is not repeated
		put it in a vector
		output it onto screen
		return
- else
	loop through each position on the board 
		fill the position with a queen
		if no queens are in conflict with one another
			call recur(cur-1) to place the next queen
		else
			un-fill the position
}

/*
precondition: none
postcondition: return true if b is an orientation contained in va; b is not changed
*/
bool repeated(){
- return true if current board configuration is repeated, meaning that it has been outputted before already; note it needs to check every transposition and rotation to make sure it is not repeated; return false otherwise
}

/*
precondition: none
postcondition: return true if there is conflict among the queens on b; return false otherwise
*/
bool conflict(){
- return true if no queens are in conflict with one another; return false otherwise
}

The argument to recur() is the number of queens that are waiting to be placed on the board. So if it is zero, it means we successfully place every queen and can output the board configuration if it is not repeated.

As you can see everything is straightforward, but when it gets down to implementing it we may need to move things around or add something to avoid a problem or to achieve a task. We will see!

Let's look at the next step!◀ Exercise #3: Solve The Eight Queens Puzzle▶ Solve The Eight Queens Puzzle - Step 2