Solve The Eight Queens Puzzle - Step 2

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

Four Step Programming Model: Step 2
Obviously we need to represent the board somehow, and I’d use a wrapper structure to wrap a two-dimensional int array. You can use bool array or another data structure if you want to. I use 1 to represent an empty position and 0 to represent a position occupied by a queen.

I need an integer to indicate the size of the board so that by simply changing it the program can find solutions to other numbers of queens. I need a vector to store past solutions so that I do not output the same solution twice. I need several variables to do indexing in loops, but they are not that important.

While reviewing my previous skeleton I realize that in recur() when the board successfully places a queen it calls recur() recursively to place the next queen. However I do not want recur() to start from the beginning of the loop trying to place the queen because the previous positions are tried already and there is no point trying them again.

So I think I need to give recur() one more argument to tell it where to begin in the loop so as to increase efficiency.

Here is my updated skeleton:

const int MAX = 8;
struct array {
	Int arr[MAX], arr[MAX];
}
vector<array> va;
array board;  //board configuration

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, int ii){
- 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 starting from ii
		fill the position with a queen
		if no queens are in conflict with one another
			call recur(cur-1, cur_pos) 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(){
- same
}

/*
precondition: none
postcondition: return true if there is conflict among the queens on b; return false otherwise
*/
bool conflict(){
- same
}

Let's look at the next step!◀ Solve The Eight Queens Puzzle - Step 1▶ Solve The Eight Queens Puzzle - Step 3