In class, we considered the N Queens problem, where we had to place N queens on
ID: 3824101 • Letter: I
Question
In class, we considered the N Queens problem, where we had to place N queens on an N-by-N chessboard such that no two queens were
in the same row, column, or diagonal (i.e., no two queens are threatening each other). We designed a simple local search algorithm for this problem as
follows:
First, because we know that each column can contain only one queen, assign each queen to her own column. Place each queen at a random location
within her column. Calculate the number of pairs of queens that are threatening each other (e.g., if Q1 is threatened by both Q2 and Q3, this counts
as 2 threats). For each queen Qi, consider moving queen Qi to a different location in the same column, and calculate the new number of conflicts that
would exist if you performed that move. Once you have performed these calculations, perform the move that results in the greatest reduction in the
current number of conflicts (subject to the constraint that each queen must remain in her assigned column). If there is no move that reduces the current
number of conflicts, then terminate. Repeat until termination.
Give an example showing that this algorithm may fail to nd a correct solution. (Hint: try N = 4. Show that (a) there is a solution in which all queens
are safe, and (b) there is some starting position and some sequence of moves
following the above description that fails to find such a solution.)
Explanation / Answer
The Queens Problem
A)There are so many ways to keep the queens in different columns.
In 4x4 - can't put a queen in the corner because then you are reduced to a 3x3 problem which isn't possible. But can't generalize that "no queen in the corner rule" (5x5 solution)
X....
..X..
....X
.X...
...X.
4x4 solution
.X..
...X
X...
..X.
Start by putting queen in position 1,2. Now there's only one place left in row 2 to put a queen (2,4). Now there's only one place left in row 3 to put a queen (3,1). Now there's only one place to put a queen in row 4 (4,3).
Possible slow algorithm: Start at top left square. Put Q in square. Mark off all "impossible" squares (put x's there). Go to next row, in first available square put a queen. If you run into row all marked off, go back up a row and go to next block. Looks like a depth first search.
Other solution to 4x4:
..X.
X...
...X
.X..
This is symmetric to the other solution. This is more advanced in the problem so we're putting it aside for now.
Depth first search. This is backtracking - all of backtracking is essentially depth first search. At most, there are n^n possible branches (but a lot are eliminated). Fortunately, there are small inputs (13^13).
n^n comes from put one in each row and check. But the solution currently proposed goes in order. Every time you put a queen somewhere, you kill off squares. This is called pruning. This cuts down on number of depth first searches you have to do.
ANOTHER WAY TO DESIGN THIS
The solver starts by arbitrarily placing a queen in the upper left corner. That's a hypothesis of sorts; perhaps it will turn out that no solution exists with a queen in the upper left corner.
Given this hypothesis, what constraints can we propagate? One constraint is that there can be only one queen in a column (the gray Xs below), and another constraint prohibits two queens on the same diagonal (the red Xs below).
Our third constraint prohibits queens on the same row:
Our constraints propagated, we can test out another hypothesis, and place a second queen on one of the available remaining squares. Our solver might decide to place in it the first available square in the second column:
After propagating the diagonal constraint, we can see that it leaves no available squares in either the third column or last row:
With no solutions possible at this stage, we need to backtrack. One option is for the solver to choose the other available square in the second column. However, constraint propagation then forces a queen into the second row of the third column, leaving no valid spots for the fourth queen:
And so the solver must backtrack again, this time all the way back to the placement of the first queen. We have now shown that no solution to the our queens problem will occupy a corner square.
Since there can be no queen in the corner, the solver moves the first queen down by one, and propagates, leaving only one spot for the second queen:
Propagating again reveals only one spot left for the third queen:
And for the fourth and final queen:
We have our first solution! (There are clearly other symmetrical solutions: just rotate the board.) If we instructed our solver to stop after finding the first solution, it would end here. Otherwise, it would backtrack again and place the first queen in the third row of the first column.
I am writing a java program to develop this.
/* Java program to solve N Queen Problem using
backtracking */
public class NQueenProblem
{
final int N = 4;
void printSolution(int board[][])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
System.out.print(" " + board[i][j]
+ " ");
System.out.println();
}
}
boolean isSafe(int board[][], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
for (i=row, j=col; i>=0 && j>=0; i--, j--)
if (board[i][j] == 1)
return false;
for (i=row, j=col; j>=0 && i<N; i++, j--)
if (board[i][j] == 1)
return false;
return true;
}
boolean solveNQUtil(int board[][], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++)
{
if (isSafe(board, i, col))
{
board[i][col] = 1;
if (solveNQUtil(board, col + 1) == true)
return true;
board[i][col] = 0;
}
}
return false;
}
boolean solveNQ()
{
int board[][] = {{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if (solveNQUtil(board, 0) == false)
{
System.out.print("Solution does not exist");
return false;
}
printSolution(board);
return true;
}
public static void main(String args[])
{
NQueenProblem Queen = new NQueenProblem();
Queen.solveNQ();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.