8 queens problem using backtracking recurison

Question

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++ ){
             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]);
                }
           }
     }
}

Solution 1

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."

Solution 2

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.

Solution 3

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.

Comments

[Nath]

I will need to carefully review all the responses. Since I haven't done any problems involving backtracking recursion yet I thought backtracking itself is kind of something hard to understand and implement.

[Op De Cirkel]

>> You will also need to create a *two-dimensional* array That is not necessary. you can keep one dimensional array (each field index is row and the number at the index is column where the queen is)

[Aasmund Eldhuset]

@Nath: Very understandable. I suggest that you try a simpler problem first to get comfortable with the technique. For instance: given a one-dimensional array of int (with, say, 10 elements), what are the possible ways you can fill it with zeroes and ones such that there is at most three ones? (e.g. 0011000001 is valid, but 0011000011 is not).

[Nath]

@Aasmund Eldhuset: I was trying to find a simpler problem in order to understand the backtracking recursion as you said but I couldn't. Thanks for your example. So, you mean how I would fill all the elements of the array with zeroes and ones such that every given element of the array doesn't have more than three ones?

[Aasmund Eldhuset]

@Nath: Yes (supposing that by "all elements of the array", you mean "all possible ways of populating the array" - the elements of the array are, after all, the individual items inside one array). So the output should be {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 1}, and so on. If you prefer, you can do it with strings instead of arrays (just beware that, from a performance standpoint, appending to a string is expensive).

[Nath]

@Aasmund Eldhuset: Actually by "all the elements" I meant elements array[0] through array[9]. For example, array[0] = 0000000000, array[1] = 0000000001, array[2] = 0000000010 and so on.

[Aasmund Eldhuset]

@Nath: Ah, you were thinking of the result being an array of strings or an array of arrays - then, yes. (However, there are more than 10 results; actually, there should be 176 possible ways of placing at most three ones, if I got the combinatorics right...)

[Nath]

@Aasmund Eldhuset: I was thinking of using one-dimensional array of int. I apologize for my misunderstanding but I got little confused now. You want me to fill the elements of one-dimensional array with different combinations of zeros and ones given that there can't be more than three ones in each combination? Right? And I have to do this by using backtracking recursion?

[Nath]

@Nemo: Can you, please give me some simpler example where I can try the above pseudocode?

[Nath]

@Nemo: I am having hard time understanding the backtracking recursion.

[Nemo]

@Nath: I have added an update with an attempt at a different explanation. Let me know what you think.

[Nath]

@Nemo: Thank you very much for your response. It is getting little cleaner in my head. I've written another pseudocode. Can you, please look at it in my updated post and let me know if it reflects correctly your explanation?

[Nemo]

@Nath: Sorry, but that is not it... Each "solver()" should only have one loop. I really think you should start by forgetting the recursive version and write it down as 8 separate functions like I describe. solver6 (just for example) does not need to loop through any columns; it should assume the first 5 columns are already populated, and its sole job is to place a queen in the 6th column and call solver7(). It calls solver7() once for each possible placement of the queen in the 6th column. That's it.

[Nemo]

@Nath: I have edited your second update to look more like what I mean... Hope that is OK

[Nath]

@Nemo: Absolutely. I think I understand now what you meant. Let me try to do the recursive version now.

[Nath]

@Nemo: I've tried to make the recursion version ( please, see Update 3 ) of what you explained to me earlier but I have the feeling that it's not what it has to be...

[Nemo]

You are still using nested "for" loops. There are no nested loops in the correct version... See if you can figure out how to write a two-argument solver(N, b) such that solver(1,b) is the same as solver1(b), solver(2,b) is the same as solver2(b), and so forth...

[Aasmund Eldhuset]

@Nath: Sorry for the late answer. Yes; use a one-dimensional int array with ten elements. Every element should contain 0 or 1 (so array[0] == 0 or array[0] == 1, array[1] == 0 or array[1] == 1, and so on to array[9] == 0 or array[9] == 1). The goal is, as you say, to produce all possible ways of filling the array so that there are at most three elements that contain 1.

[Aasmund Eldhuset]

@Nath: The backtracking approach will then be to have a recursive function that takes the array as a parameter along with an int i that tells which element we're trying to populate right now. If i == 10, this means that all array elements have been populated, and the current contents of the array is a valid solution and can be printed (and then, the function returns). Otherwise, let array[i] = 0 and call the function recursively with i + 1. When the recursive call returns, you know that all possible ways to fill the remainder of the array have been explored.

[Aasmund Eldhuset]

@Nath: Afterward, check whether the array elements to the left of i contain less than three ones; if so, we can place a one in position i and call the function recursively again to try all possibilities for the remaining part of the array.

[Nath]

@Nemo: I apologize for the late response. I removed the outer loop ( please, see the edited Update 3 ). I am having hard time figuring out how to write the two-argument solver(N, b) recursively because as far as I understood we place a queen in solver1() and solver8(), while no queen is placed in solver2(), solver3(), solver4(), solver5(), solver6() and solver7(). Is my understanding correct?

[Nemo]

All 8 solvers have to place a queen. solver1() places a queen in column1. solver2() places a queen in column 2. solver3() places a queen in column 3. etc

[Nath]

In that case the last update should be correct (I've edited it little) except that there is no backtracking and check for right position of the queen... Or no?

[Nath]

I apologize for the late reply, too :) I'll see what I can do myself and will be back with more questions...

[Nath]

@Nemo: If I assume the pseudocode in update 3 is correct how could I incorporate the backtracking process?

[Divick]

@Nemo: IMHO your pseudocode, does only recursion but not backtracking. You need to reset the state after return from do_it function in for loop.

[JAL]

While this code may answer the question, providing additional context regarding why and/or how this code answers the question improves its long-term value.