solving the eight queens to produce a solution

222 views Asked by At

Below is my attempt at solving the 8 queens problem to print one solution. (place 8 queens on a chessboard such that none of them are attacking each other). However, this solution only places 6 queens. I need another opinion of where I am making a mistake. I'm doing this in more of a BFS style instead of backtracking.

1

There are 1 answers

1
Compass On BEST ANSWER

It seems your algorithm is malfunctioning at some point. Upon running it, I found the following issues:

  1. You are constantly setting visited[i][j] to 0 in your for loop in main. This always resets visited to 0 even if a recursion call is made. In fact, when you declare both visited and board they are initiated to arrays full of 0s. So you can get rid of both set statements in there. In addition, because you reset the arrays, your recursive function ends up setting both values to 0 and then finds them again."

  2. For debugging, in the !hasQueen statement, you should output the board[row][col] coordinates, which show you the coordinates that have been found. The final list before it prints out the grid shows that 2,4 and 1,6 are found and set twice.

  3. The actual chessboard that is output ends up with an impossible solution:

1 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 0 0 1 0 0 0

0 0 1 0 0 0 0 0

0 0 0 X 0 Y 0 0

0 0 0 Y 0 X 0 0

0 0 0 0 0 0 0 1

0 1 0 0 0 0 0 0

(sorry I can't get the numbers to format)

Both layout X and layout Y fail the 8 queens rules.

If you run your program with the setting to 0 commented out, you will see that it grinds to a halt after finding 6 locations.