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

fShare
Questions? Let me know!
Close