Re: N-queens solution

Explanation of N-queens

I will assume the 4-queens problem for sake of simplicity. 4-queens has 2 solutions.

The Optimal Solution (without notDuplicate() and other functions)

The objective of the program is to generate the positions on a 4x4 chess board such that when queens are placed on those postions, they do not attack each other.

The mobility of the queen sets the rules by which the other queens can be placed on the board.

This is how my program goes. The main() enters a loop to go through the first row of the chess board. So in the first iteration of the loop list< Solution > holds a single point (0,0) and this is used to construct the first chessBoard object,through a pointer "chess". The constructor for ChessBoard takes "candidate Solution list" and size of the board (in this case 4x4, hence n=4). Next, in the loop chess->Search() is exceuted. Search() represents the main algorithm which does most of the work in the program. Search() takes an argument which is the row number where the child has to be searched. If you notice, in this version, I'm feeding forward, as in, since my first point is (0,0), I search for a child in row 1.

Now I'll break down Search() for initial point of (0,0). The first step in Search() is to check whether the list currSol's size equals the size of of n. This case is possible only when a solution is found and hence here an "if" statement checks for that and on being true, Search() prints the Solution, increments the no. of solutions found and then returns.

Now if the size is not equal to n, that means the list still has to grow to find a solution. Hence the next step is to Map the chess board, i.e. to setup the unsafe positions on the board. This is achieved by the function setAttForEach(). For (0,0), the resultant board layout is:

Print currSol
Position on board is: 0 , 0

Print Board
1 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0

Now once the board has been setup, the main loop of the Search() function starts. xpos sets which row has to be searched to find a new safe position. The loop starts iterating through through that row (namely row 1) and the "if" statement checks whether the board position is safe or not. This is the critical part, If a safe position is found, first the new Point is appended to the currSol list and after that a new object of ChessBoard is created giving currSol to the new object's constructor and then chess->Search(g+1) is called, i.e Search() is called on the new object - for the next row (namely row 2).

Now again Search() executes for the new object, first checking if solution is found (which fails) and then Mapping the board of the new object according to it's currSol, which has the Points (0,0) and (1,2), the board now has the following setup:

Print currSol
Position on board is: 0 , 0
Position on board is: 1 , 2

Print Board
1 0 0 0
0 0 1 0
0 0 0 0
0 1 0 0

As you can notice when Search() goes through row 2, it finds no 1's hence the search on this object returns. Returns to where? Returns to the first object's Search(). See Search(), there is a "delete chess", hence the first object (the one with (0,0))deletes the new object (the one with (0,0) & (1,2)), and then does a currSol.pop_back(), which means that (1,2) is removed from the first object's currSol (remember we had pushed it in before creating new object, hence we pop it back out, since there is not solution to be found from that). The next line (setAttForEach) is redundant and is not needed, hence you can delete it. Now the first object's currSol has only (0,0) and it continues with the loop, i.e. it continues to search through row 1. It now finds (1,3) to be a probable child and in this way the search continues for all possible safe positions in row 1. But 4-queens doesn't have any solutions with (0,0), so this object search finally returns back to main(), where again the object is deleted and the main's loop continues, so now a new ChessBoard is created for the initial point of (0,1). This does find a solution:

Print currSol
Position on board is: 0 , 1
Position on board is: 1 , 3
Position on board is: 2 , 0
Position on board is: 3 , 2
Solutions: 1

And the second solution found is

Print currSol
Position on board is: 0 , 2
Position on board is: 1 , 0
Position on board is: 2 , 3
Position on board is: 3 , 1
Solutions: 2

Actually these also are similar, these two are basically what you call reflections of each other (try swapping the x,y values in first and re-order, you get the second solution). So the First is the "Unique" solution.

So this was the explanation, hope it made sense to you'll. This may not be the most efficient way to solve this problem, but my aim was to brush up with c++, which I achieved. So all in all, I'm pretty happy with the product!

Dinesh.