N Queens – Backtracking Problem 2

BackTracking:

Find a solution by trying one of several choices. If the choice proves incorrect, computation backtracks or restarts at the point of choice and tries another choice. It is often convenient to maintain choice points.

In an exhaustive search algorithm you search every possible choice to reach to the goal state, however, the backtracking algorithm is an extension, where you realize a bad choice by using some constraint and do not explore that choice any further. Hence, this is optimized by reducing the number of choices that you would explore in case of exhaustive search.

Example:

The example can help you understand the backtracking algorithm. Almost all the problems have similar structure where you have to explore various options available and the choices are in the form of tree above.

Starting at Root, your options are A and B. You choose A.
At A, your options are C and D. You choose C.
C is a bad choice and it is decided by some constraint in the real world problems. Go back to A.
At A, you have already tried option C, and it failed. Try option D.
D is bad. Go back to A.
At A, you have no options left to try. Go back to Root.
At Root, you have already tried A. Try B.
At B, your options are E and F. Try E.
E is good which is your goal. Congratulations, you have solved the backtracking problem !

Backtracking Solution Structure:

 ALGORITHM Backtrack(X[1..i])
//Gives a template of a generic backtracking algorithm
//Input: X[1..i] specifies first i promising components of a solution
//Output: All the tuples representing the problem’s solutions
if X[1..i] is a solution write X[1..i]
else //
   for each element x ∈ Si+1 consistent with X[1..i] and the constraints do
      X[i + 1]←x
      Backtrack(X[1..i + 1])

N Queens Problem:

The problem is to place n queens on an nxn chessboard so that no two
queens attack each other by being in the same row or in the same column or on
the same diagonal.

Solution:
We start with the empty board and then place queen 1 in the first possible
position of its row, which is in column 1 of row 1. Then we place queen 2, after
trying unsuccessfully columns 1 and 2, in the first acceptable position for it, which
is square (2, 3), the square in row 2 and column 3. This proves to be a dead end
because there is no acceptable position for queen 3. So, the algorithm backtracks
and puts queen 2 in the next possible position at (2, 4). Then queen 3 is placed
at (3, 2), which proves to be another dead end. The algorithm then backtracks all
the way to queen 1 and moves it to (1, 2). Queen 2 then goes to (2, 4), queen 3 to
(3, 1), and queen 4 to (4, 3), which is a solution to the problem.

N_Queens Problem

public class NQueens {

    List<String[]> res = new ArrayList<String[]>();
    /****number of possible solutions****/
    int count=0;
    public List<String[]> solveNQueens(int n) {
        
        int A[] = new int[n];
        for(int i=0; i<n; i++){
            A[i]=-1;
        }
        solve(A,0,n);
        return res;
    }
    
    public void printBoard(int[] A, int n){
        String str[] = new String[n];
        for(int i=0; i<n; i++){
            String temp="";
            for(int j=0; j<n; j++){
                if(A[i]==j){
                    temp +="Q";
                }else{
                    temp +=".";
                }
            }
            str[i]=temp;
        }
        res.add(str);
    }
    
    public boolean isValid(int[] A, int col){
        for(int i=0; i<col; i++){
            if(A[i]==A[col] || Math.abs(A[i]-A[col])== (col-i)){
                return false;
            }
        }
        return true;
    }
    
    public void solve(int[] A, int col, int n){
         if(col==n){
             printBoard(A,n);
             count++;
         }else{
             for(int i=0; i<n; i++){
                 A[col] =i;
                 if(isValid(A,col)){
                     System.out.print(col+" ");
                	 solve(A,col+1,n);
                 }
             }
         }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation