10

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]);
                }
           }
     }
}
Nath
  • 229
  • 2
  • 4
  • 11
  • Is this homework? If so, you should tag the question as such. It might prevent people from giving you complete solutions that wouldn't help you at all. – Bertrand Marron Jun 14 '11 at 00:07
  • 4
    +1 for explicitly requesting that we don't write the code for you. :-) – Aasmund Eldhuset Jun 14 '11 at 00:10
  • @Bertrand: I wouldn't say it's homework since I am studying on my own. – Nath Jun 14 '11 at 00:10
  • 3
    @Aasmund: Yes, exaclty. No code. I want to understand it and do it myself. – Nath Jun 14 '11 at 00:12
  • Couple of points: 1) look up what recursion means (not meant to be snotty.) You're not doing it in your pseudo code because, in short, you haven't invoked the method Queen from within the method Queen. 2) To solve this problem, your program is going to have to try many different solutions until it finds one that works. To do so, it won't print anything out until it has a solution. So you're going to need some sort of data structure to hold the problem in memory while your program works on it. – Marvo Jun 14 '11 at 00:17
  • @Marvo: I've done different problems involving recursion but this is the first one involving backtracking recursion. – Nath Jun 14 '11 at 00:27
  • Thank you kindly to everyone who replied to my question. I will review all of your replies and for sure will be back with more questions later. – Nath Jun 14 '11 at 01:08

5 Answers5

8

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

Aasmund Eldhuset
  • 37,289
  • 4
  • 68
  • 81
  • 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. – Nath Jun 14 '11 at 01:03
  • 1
    >> _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) – Op De Cirkel Jun 14 '11 at 01:49
  • @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). – Aasmund Eldhuset Jun 14 '11 at 10:12
  • @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? – Nath Jun 14 '11 at 19:01
  • @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). – Aasmund Eldhuset Jun 14 '11 at 19:22
  • @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. – Nath Jun 14 '11 at 19:53
  • @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...) – Aasmund Eldhuset Jun 14 '11 at 19:57
  • @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 Jun 14 '11 at 20:27
  • @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 Jun 16 '11 at 11:17
  • @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 Jun 16 '11 at 11:19
  • @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. – Aasmund Eldhuset Jun 16 '11 at 11:20
  • I apologize for the late reply, too :) I'll see what I can do myself and will be back with more questions... – Nath Jun 16 '11 at 21:30
4

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.

Nemo
  • 70,042
  • 10
  • 116
  • 153
  • @Nemo: Can you, please give me some simpler example where I can try the above pseudocode? – Nath Jun 14 '11 at 21:46
  • @Nemo: I am having hard time understanding the backtracking recursion. – Nath Jun 14 '11 at 21:54
  • 1
    @Nath: I have added an update with an attempt at a different explanation. Let me know what you think. – Nemo Jun 14 '11 at 23:56
  • @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? – Nath Jun 15 '11 at 18:31
  • 1
    @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 Jun 15 '11 at 18:42
  • 1
    @Nath: I have edited your second update to look more like what I mean... Hope that is OK – Nemo Jun 15 '11 at 21:42
  • @Nemo: Absolutely. I think I understand now what you meant. Let me try to do the recursive version now. – Nath Jun 15 '11 at 22:25
  • @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... – Nath Jun 16 '11 at 01:52
  • 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... – Nemo Jun 16 '11 at 05:19
  • @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? – Nath Jun 16 '11 at 20:07
  • 1
    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 – Nemo Jun 16 '11 at 20:23
  • 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 Jun 16 '11 at 20:46
  • @Nemo: If I assume the pseudocode in update 3 is correct how could I incorporate the backtracking process? – Nath Jun 17 '11 at 18:26
  • @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. – Divick Jan 04 '15 at 04:24
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.

Community
  • 1
  • 1
Saurabh Gokhale
  • 53,625
  • 36
  • 139
  • 164
0

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:

 *  -  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 

 *  -  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 

 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 

 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 

 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 

 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 

 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 

 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 

 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 

 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 

 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 

 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 

 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  *  -  -  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 

 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 

 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 

 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 

 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 

 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 *  -  -  -  -  -  -  - 

 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 

 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 

 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 

 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 

 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 

 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 

 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  -  * 

 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 

 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 

 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 

 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  -  -  *  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 

 -  -  -  -  *  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  -  -  *  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 

 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 

 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 *  -  -  -  -  -  -  - 

 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  *  -  -  -  -  - 

 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 

 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 

 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 

 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 

 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 

 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  -  * 

 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  *  -  -  -  - 

 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 

 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 

 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 

 -  -  -  -  -  *  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 

 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  *  -  -  -  - 

 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 

 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 

 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 

 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 

 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 

 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 

 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 

 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 

 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 

 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 

 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 

 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 

 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 

 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 

 -  -  -  -  -  -  *  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 

 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  -  -  -  -  *  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 

 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  *  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 

 -  -  -  -  -  -  *  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  *  -  -  -  - 

 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  -  * 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  -  * 
 -  -  -  -  -  *  -  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  *  -  -  - 

 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 

 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  -  -  -  -  -  * 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 
 -  -  -  -  -  *  -  - 

 -  -  -  -  -  -  -  * 
 -  -  *  -  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  *  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  *  -  -  -  - 

 -  -  -  -  -  -  -  * 
 -  -  -  *  -  -  -  - 
 *  -  -  -  -  -  -  - 
 -  -  *  -  -  -  -  - 
 -  -  -  -  -  *  -  - 
 -  *  -  -  -  -  -  - 
 -  -  -  -  -  -  *  - 
 -  -  -  -  *  -  -  -
jatin Goyal
  • 85
  • 6
  • 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. – JAL Dec 06 '15 at 18:25
0

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