$ mkdir ~/cs170/labs/lab30 $ cd ~/cs170/labs/lab30
In Computer Science, we like elegant things. However, sometimes there isn't a real elegant solution. Sometimes, the only real solution is to just However, sometimes there's a lot of possible solutions to try. Backtracking is a mechanism which is essentially a more directed brute force search. Instead of computing a full solution, you stop trying a solution once you found something that won't work.
In a file called NQueens.cc, create a program that solves the 8-Queens problem. You should create an \(8 \times 8\) 2-dimensional array, initially filled with 0's. You will use the number \(1\) to represent a location with a queen in it.
To solve this problem, you will need AT LEAST 2 helper functions:
bool queenBacktracking(int ** board, int currRow).
This function takes the current board, and an integer specifying
the current row. This function should attempt to place a queen
somewhere in the specified row. If it was successful, it should
recursively call itself on the next row to attempt to place a
queen there. This function should return \(true\) only if it
was able to place a queen in all of the rows in the range
\([currRow, N)\).
bool checkQueenConflict(int ** board, int row, int col).
This function takes the current board, and a \((row, col)\)
coordinate. It should return \(true\) if placing a queen in the
specified location would cause a conflict. This means checking
the specified row, column, and diagonals to see if there are any
queens in them already.
You may need helper functions! Don't be afraid to add more!
Once you finished the code for the 8 Queens problem, modify your code so that it can solve the N-Queens problem. If written properly, this should mean only needing to change one constant value defined at the top of your program.
Attempt to solve the N-Queens problem for board sizes in the range \([1, 25]\). Which ones are solvable? Which ones aren't? At what point do the solutions take an obvious amount of time?
