8 queens problem using backtracking recurison
I've been working on the 8 queens problem but I got stuck. I don't want code. I would love guidance and directions in order to understand how to solve this problem myself using backtracking recursion.
The program should enumerate all solutions to the N-queens problem by drawing the location of the queens in ASCII like the two solutions here.
My pseudocode so far is:
void queen(int n){
for( int i = 0; i < n; i++){
place queen[ i ] on row i;
for(int j = 0 ; j < n ; j++){
if( queen[ i ] is not in the same column as queen[0] through queen[ i - 1 ] &&
queen[ i ] is not on the same major diagonal with queen[0] through queen[ i -1 ] &&
queen[ i ] is not on the same minor diagonal with queen[0] through queen[ i -1 ] ) {
print 'Q ';
}
else{
print '* ';
}
System.out.println();
}
System.out.println();
}
}
There is no any backtracking recursion in my pseudocode because I don't know how to do it.
Any help is greatly appreciated.No code, please.
(Update in response to Nemo):
solver(int n, Board b){
for(int i = 0; i < b.length; i++){
place queen in column i;
for(int j = 0; j < b.length; j++){
change b;
solver(n+1,changed b);
}
}
}
Is it correct?
(Update 2):
solver8(board /* with queens presented in first 7 columns */){
// place a queen in the 8th column;
for(each possible placement of the queen in column 8
or in other words int i = 0; i < board.length; i++ ){
开发者_如何学C place the queen and print the board
}
}
solver7(board /* with queens presented in first 6 columns */){
// place a queen in the 7th column;
for(each possible placement of the queen in column 7
or in other words int i = 0; i < board.length; i++ ){
solver8(board with queens placed in first 7 columns);
}
}
solver6(board /* with queens presented in first 5 columns */ ){
// place a queen in the 6th column;
for(each possible placement of the queen in column 6
or in other words int i = 0; i < board.length; i++ ){
solver7(board with queens presented in first 6 columns);
}
}
and so on until
solver1(1, empty board){
for(int i = 0; i < board.length; i++){
place queen in row[i] of column 1;
solver2(board with queen in row[i] of column 1);
}
}
Update 3 (Edited):
private int numberOfQueens = 8;
solver(int n, Board b){
for(int r = 0; r < b.length; r++){
place queen in row[r] of column[n];
if(n == numberOfQueens){
print the board;
return;
}
else{
solver(n+1, board with queen in row[r] of column[n]);
}
}
}
}
The purpose of using recursion for these kinds of problems is that they allow you to think in terms of "I have now placed k queens; how can I place the remaining ones if the total number of queens is n?" So the recursive function should take two parameters: the target number of queens, and the number of queens placed so far. When writing the function, your goal is first and foremost to try out different ways of placing the k th queen. But when you have selected a possible placement and found it to be valid, you need to place the remaining n - k - 1 queens. How can we do this? The answer: recursion! Call the function (from within itself) with the parameter k - 1 to indicate that you want to place the remaining k - 1 queens. Whenever you exhaust all possibilities (or find that none are possible), simply return from the function - you will then get back to the previous function call (e.g. the one that tries to place the k th queen).
Edit: You will also need to create a two-dimensional array to represent the current state of your board; this array must either be sent as an additional parameter to the recursive function, or be kept as a field of the class that contains the method.
As for the backtracking, that is accomplished simply by making sure that the function that gets called with k + 1 removes the k + 1 th queen from the board before returning; this essentially says "We've now (unsuccessfully) tried all ways of placing the remainder of the queens - based on the positions of the k queens that have already been placed. None of them succeeded, so please adjust the positions of the first k queens (which will be done by the function that was called with k, and the function which called that function, and so on) and try again."
Generally speaking, a recursive backtracking search looks something like this:
// On input, s represents a valid State up to depth d-1
sub do_it(int d, State s)
if (d == MAX_DEPTH+1)
// State s represents an answer! Print it and return.
else
(augment s to make it valid for depth d)
for each augmented_s
do_it(d+1, augmented_s)
end for
end if
end sub
// top level
do_it(0, empty_state)
Note that for a given s valid up to depth d-1, there could be multiple ways to augment it into a state valid up to depth d. The idea is to call yourself with each of them.
For this problem, the "state" is the board. The depth "d-1" might mean the first d-1 columns are populated. The legal augmented states would be those with a queen in column d such that she cannot be captured.
[update]
Here is another way to look at it. Work the problem backwards.
Suppose I ask you to write a simple function called solver8(). This function takes as input a board with queens already present in the first 7 columns. All it has to do is take that board, find all ways to add a queen to the 8th column, and print out those boards. Do you think you could write this function? Good; write it.
Now suppose I ask you to write an almost-as-simple function called solver7(). This function takes as input a board with queens already present in the first 6 columns. All it has to do is take that board, find all ways to add a queen to the 7th column, and pass each of those boards as an argument to solver8(). Could you write this function?
Now suppose I ask you to write another function called solver6(). As input, it takes a board with queens present in the first 5 columns. All it has to do is take that board, find all ways to add a queen to the 6th column, and then pass each of those boards to solver7().
And so on, until we get to solver1(). This one takes an empty board, finds all ways to place a queen in the first column, and passes each of those boards to solver2().
You have just written 8 functions that together solve the 8 queens problem. If this does not make sense, write it out as 8 functions and stare at it until you do.
Now, if you look at all of these functions, you will find they are pretty similar. So instead of writing solver8, solver7, solver6, ..., solver1, you write a single function:
solver(int n, Board b)
...such that solver(1, b) is the same as solver1(b), solver(2, b) is the same as solver2(b), ..., and solver(8, b) is the same as solver8(b). And instead of solver2(...) calling solver3(...), for instance, you will just have solver(2, ...) calling solver(3, ...). One function instead of 8, but doing the same thing.
You will pretty quickly discover that the final code is cleaner if you start with a solver9() that just takes a fully populated board and prints it out, and have solver8() call that.
See this nice animation here on 8 queen's problem using recursion.
Also, check out : 8 queens problem - Java/C++.
Check out the logic explained here.
Put the first queen in [0][0], then find a spot for the second. lets say you found one go to the next, so on and so forth. Assumingly your 5th queen cant be placed anywhere in the 5th column or row (whichever you follow). Go back to the 4th and find another spot to that. Than go to the 5th again.Lets say you are in the 8th one and there are no spots available. Go to 7th and still nothing back there. You will kep on going back until the 2nd and find a spot to the 2nd again, and go to the 3rd. Does it make sense...
Hope this Solution helps
Main Points are
1.Recursion simple to under
2.IsValid position 2.1 cross Queen found in same column like
*
*
2.2 cross Queen found diagonally like
*--
---
--*
or
--*
---
*--
Code :
package queenproblem;
public class QueenProblem
{
int numQueens[];// hold columns postion
int numQueen;
QueenProblem(int noOfQueens) {
this.numQueen = noOfQueens;
numQueens = new int[noOfQueens];
}
public static void main(String[] args) {
new QueenProblem(8).solveProblem();
}
public void solveProblem() {
arrange(0);
}
// recursive Function
void arrange(int rowIndex) {
// 1.to check valid Postion of not.
// 2. to check all Queens postion is found or not.
for (int i = 0; i < numQueen; i++)
{
if (isValid(rowIndex, i))
{
numQueens[rowIndex] = i;// save col index
if (rowIndex == numQueen - 1)
{
printsBoard();
} else
{
arrange(rowIndex + 1);
}
}
}
}
private void printsBoard() {
for (int i = 0; i < numQueen; i++)
{
for (int j = 0; j < numQueen; j++)
{
if (numQueens[i] == j)
{
System.out.print(" * ");
} else System.out.print(" - ");
}
System.out.println();
}
System.out.println();
}
boolean isValid(int rowIndex, int colIndex) {
for (int i = 0; i < rowIndex; i++)
{
// on the save columns
if (numQueens[i] == colIndex) return false;
if ((i - rowIndex) == (numQueens[i] - colIndex)) return false;
if ((i - rowIndex) == (colIndex - numQueens[i])) return false;
}
return true;
}
}
92 Possible Solutions to 8 Queens Problem:
* - - - - - - -
- - - - * - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
* - - - - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
- - - - - - * -
- - - * - - - -
- * - - - - - -
- - - - * - - -
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- * - - - - - -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
- - - * - - - -
* - - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- * - - - - - -
- - - - - * - -
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - - - - - - *
- - * - - - - -
- - - - * - - -
- * - - - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
* - - - - - - -
- - - * - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - - - - - *
- - - - * - - -
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - - - *
* - - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
- - - * - - - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - * - - -
- - - - - - - *
- - - * - - - -
* - - - - - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - * - - -
- - - - - - - *
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
* - - - - - - -
- - - * - - - -
- - - - - - - *
- - - - * - - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
* - - - - - - -
- - - - - - - *
- - - * - - - -
- - * - - - - -
- - - - - * - -
- - - * - - - -
* - - - - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - * - - - - -
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - * - -
- - - - - - - *
* - - - - - - -
- - - * - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - * - - - - -
- - - - - * - -
- - - - - - - *
* - - - - - - -
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
- - * - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - - - - - *
- - - - * - - -
* - - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
* - - - - - - -
- - - - * - - -
- - * - - - - -
- - - - - - - *
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - - - - * - -
- * - - - - - -
- - - - * - - -
- - - * - - - -
* - - - - - - -
- - - - * - - -
- - - - - - - *
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - * - - - -
* - - - - - - -
- - - - * - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
- * - - - - - -
- - - - * - - -
- - - - - - - *
- - - - - * - -
* - - - - - - -
- - * - - - - -
- - - - - - * -
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - - - - - *
* - - - - - - -
- - - - * - - -
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - - - - - *
- - - - * - - -
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
* - - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
* - - - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
- - * - - - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - - - - - - *
- - - - * - - -
- * - - - - - -
- - - - - * - -
- - * - - - - -
- - - * - - - -
- - - - - - * -
- - * - - - - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
* - - - - - - -
- - - - - * - -
- - - * - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - - - - * - -
* - - - - - - -
- - * - - - - -
- - - - - - - *
- - - * - - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - - - *
* - - - - - - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
- - - * - - - -
- - - - - - - *
* - - - - - - -
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
- - - * - - - -
- - - - - - - *
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - - - * - - -
* - - - - - - -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - * - - -
* - - - - - - -
- - - - - - - *
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - - * - - -
* - - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
- - - - * - - -
- * - - - - - -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- * - - - - - -
- - - * - - - -
- - - - - - * -
- - * - - - - -
- - - - - - - *
- - - - - * - -
* - - - - - - -
- - - - * - - -
- * - - - - - -
- - - - - * - -
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - - - - - - *
- - * - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
* - - - - - - -
- - - * - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- - - - * - - -
- - * - - - - -
- - - - - - - *
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - - - - * - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
- - - - - - - *
* - - - - - - -
- - * - - - - -
- - - - - * - -
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - * - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - - - - - *
- - - * - - - -
- - - - * - - -
- - - - - - * -
- - - * - - - -
* - - - - - - -
- - * - - - - -
- - - - - - - *
- - - - - * - -
- * - - - - - -
- - - - * - - -
- - - - - - - *
- - - * - - - -
* - - - - - - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - - - *
- - - * - - - -
* - - - - - - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
- - - - - * - -
* - - - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
- - * - - - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - - - - - *
- - - * - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
* - - - - - - -
- - - * - - - -
- - - - - - - *
- - - - * - - -
- - * - - - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - - - - - *
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - - - - - *
- - - - * - - -
- * - - - - - -
- - - * - - - -
- - - - - - * -
- - - - - * - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - * - - - - -
- - - - * - - -
- - - - - - - *
* - - - - - - -
- - - * - - - -
- * - - - - - -
- - - - - - * -
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
- - - - - - - *
* - - - - - - -
- - - - * - - -
- - - - - * - -
- - * - - - - -
- - - - - - * -
- * - - - - - -
- - - - - - - *
- - - - * - - -
* - - - - - - -
- - - * - - - -
- - - - - * - -
- - * - - - - -
- - - - - - * -
- - - * - - - -
* - - - - - - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
- - - - - * - -
- - - * - - - -
* - - - - - - -
- - - - * - - -
- - - - - - - *
- * - - - - - -
- - - - - - * -
- - * - - - - -
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - * - -
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- - - - - - * -
* - - - - - - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
- - * - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
- - - - - - * -
* - - - - - - -
- - * - - - - -
- - - - - - - *
- - - - - * - -
- - - * - - - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
- * - - - - - -
- - - * - - - -
* - - - - - - -
- - - - - - - *
- - - - * - - -
- - * - - - - -
- - - - - * - -
- - - - - - * -
- * - - - - - -
- - - - - * - -
- - * - - - - -
* - - - - - - -
- - - * - - - -
- - - - - - - *
- - - - * - - -
- - - - - - * -
- - * - - - - -
* - - - - - - -
- - - - - * - -
- - - - - - - *
- - - - * - - -
- * - - - - - -
- - - * - - - -
- - - - - - * -
- - * - - - - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
* - - - - - - -
- - - - - * - -
- - - * - - - -
- - - - - - * -
- - - * - - - -
- * - - - - - -
- - - - * - - -
- - - - - - - *
* - - - - - - -
- - * - - - - -
- - - - - * - -
- - - - - - * -
- - - * - - - -
- * - - - - - -
- - - - - - - *
- - - - - * - -
* - - - - - - -
- - * - - - - -
- - - - * - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
- - - - - - - *
- * - - - - - -
- - - * - - - -
* - - - - - - -
- - - - - - * -
- - - - * - - -
- - * - - - - -
- - - - - * - -
- - - - - - - *
- * - - - - - -
- - - - * - - -
- - * - - - - -
* - - - - - - -
- - - - - - * -
- - - * - - - -
- - - - - * - -
- - - - - - - *
- - * - - - - -
* - - - - - - -
- - - - - * - -
- * - - - - - -
- - - - * - - -
- - - - - - * -
- - - * - - - -
- - - - - - - *
- - - * - - - -
* - - - - - - -
- - * - - - - -
- - - - - * - -
- * - - - - - -
- - - - - - * -
- - - - * - - -
加载中,请稍侯......
精彩评论