akattack's blog

By akattack, history, 4 weeks ago, In English,

What is N Queen Problem?

We are given N chess’s queens and is asked to place them in the chessboard of size NxN so that no two queens attack/eliminate each other.

A queen can only attack if another queen is either on:

  • Same Row
  • Same Column
  • Same Diagonal (left or right)

Solution using Backtracking

import java.util.Scanner;
 
public class Board {
 
    int chessBoard[][];
    int queens;
 
    public Board(int queens) {
        chessBoard = new int[20][20];
        this.queens = queens;
    }
 
    void displayBoard(){
        int i, j;
        for(i=0; i<queens; i++){
            for(j=0; j<queens; j++){
                if(chessBoard[i][j] == 1)
                    System.out.print(" * ");
                else
                    System.out.print(" - ");
            }
            System.out.print("\n");
        }
        System.out.print("\n");
        System.out.print("\n");
    }
 
    void reset(){
        for(int i=0; i<queens; i++){
            for(int j=0; j<queens; j++){
                chessBoard[i][j] = 0;
            }
        }
    }
 
    boolean isValidPlace(int row, int col){
        int i,j;
 
        //Checking horizontally
        for(i=col; i>=0; i--){
            if(chessBoard[row][i] == 1)
                return false;
        }
 
        //checking left diagonal
        for(i=row, j=col; i>=0 && j>=0; i--,j--){
            if(chessBoard[i][j] == 1)
                return false;
        }
 
        //checking right diagonal
        for(i=row, j=col; i<queens && j>=0; i++,j--){
            if(chessBoard[i][j] == 1)
                return false;
        }
 
        return true;
    }
}
 
public class NQueen {
 
    int queens;
    boolean flag;
    Board board;
 
    public NQueen(int queens) {
        this.flag = false;
        this.board = new Board(queens);;
        this.queens = queens;
    }
 
    void solveNqueen(){
 
        int i;
        //starting from (0,0) of the board
        hasSolution(0,0);
 
        //After running hasSolution() still flag == false
        //It means no Solution
        if(!flag)
            System.out.println("No Solution");
 
    }
 
    boolean hasSolution(int ctr, int colQueen){
 
        //Reached beyond last column
        //Means solution (configuration) found
 
        if(colQueen == queens){
            flag = true;
            board.displayBoard();
            //intentionally returning false to find more possible solution
            return false;
        }
 
        int i,j;
        for(i=ctr; i<queens; i++){
 
            //checking if position is safe
            if(board.isValidPlace(i,colQueen)){
                //setting current value to 1 means placing a queen
                board.chessBoard[i][colQueen] = 1;
                //moving to next column's 1st row
                if(hasSolution(0,colQueen+1))
                    return true;
 
                //backtrack
                //reset to 0 means removing queen
                board.chessBoard[i][colQueen] = 0;
            }
 
        }
 
        //When no row is safe in current column
        return false;
    }
}
 
public class App {
 
    static Scanner in = new Scanner(System.in);
 
    public static void main(String args[]){
        System.out.println("Enter number of Queens");
        int queens = in.nextInt();
 
        NQueen nQueen = new NQueen(queens);
        nQueen.solveNqueen();
 
    }
}

Reference: My Programming Blog

 
 
 
 
  • Vote: I like it
  • +30
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Auto comment: topic has been updated by akattack (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Auto comment: topic has been updated by akattack (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

You can optimize your diagonal checking part to O(1). Think about how.

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

You can optimize your solution by not using Java.