How do I make a N Queens program that does recursion around an input of the size
ID: 3781823 • Letter: H
Question
How do I make a N Queens program that does recursion around an input of the size of the board along with the position of ONE initalized queen.
I want it to print out the array of solutions at the end including the input position of the first queen.
I'm stumped on this part because I can't figure out how to do recursion to check for the initial queen position.
So if I were to run the program and input the values 5 3 5, (suppose the first # is the size of the board, second # is the column, and the third # is the row)
I would get back an array of solutions beginning with
3 5
1 1
2 3
4 2
5 4
And if there is no solution in a specific instance because of the placement of the queen or because of the board size then just print no solution.
Explanation / Answer
The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. (http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/)
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; // BACKTRACK
}
}
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();
}
}
Thank you.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.