Sunday, September 7, 2014

NQueens Problem - Solver Program [N x M board][Java]

This program solves the NQueens problem. The problem is to place N queens on N rows (N is the number of rows in the board) on the board so that no two queens can attack each other. Note that the board must be 4 x 4 (if square) at least, otherwise no solution is possible.

Source :

/**
 *
 * @author Jatin Thakur coderbots.blogspot.com
 */

import java.util.*;

class Board {

    char[][] board;
    int x, y;

    void setDimensions(int x, int y) {
        this.x = x;
        this.y = y;

        board = new char[x][y];
        for (int i = 0; i < x; ++i) {
            Arrays.fill(board[i], '_');
        }
    }

    int getX() {return x;}
    int getY() {return y;}

    public void place(Point p) {
        board[p.x][p.y] = 'Q';
    }
}

class Point {

    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class NQueens {

    static Board boardInstance = new Board();

    boolean diagonals(Point p) {    //placeable (considering diagonals only)
        int i = p.x - 1;
        int j = p.y + 1;
        for (; i >= 0 && j < boardInstance.getY(); i--, j++) {
            if (boardInstance.board[i][j] == 'Q') {
                return false;
            }
        }
        i = p.x - 1;
        j = p.y - 1;
        for (; i >= 0 && j >= 0; --j, --i) {
            if (boardInstance.board[i][j] == 'Q') {
                return false;
            }
        }
        return true; //Diagonals are free - placeable
    }

    boolean rowColumn(Point p) {    //Placeable on rowColumns?
        for (int i = p.x; i >= 0; --i) {
            if (boardInstance.board[i][p.y] == 'Q') {
                return false;
            }
        }
        for (int i = 0; i < boardInstance.getY(); ++i) {
            if (boardInstance.board[p.x][i] == 'Q') {
                return false;
            }
        }
        return true;
    }

    boolean placeable(Point p) {
        return diagonals(p) && rowColumn(p);
    }

    public boolean solveBoard(int row) {

        Boolean placed = false;
        for (int i = 0; i < boardInstance.getY(); ++i) {
            Point p = new Point(row, i);
            if (placeable(p)) {
                boardInstance.place(p);
//                printBoard();
                if (row < boardInstance.getX() - 1) {
                    placed = solveBoard(row + 1);
                }

                if (row == boardInstance.getX()-1) {
                    printBoard(); 
                }
                if (!placed) {
                    boardInstance.board[row][i] = '_';
                }
            }
        }
        return false;
    }

    public void printBoard() {
        System.out.println();
        for (int i = 0; i < boardInstance.getX(); ++i) {
            for (int j = 0; j < boardInstance.getY(); ++j) {
                System.out.print(boardInstance.board[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter board size: ");
        int x = scan.nextInt(), y = scan.nextInt();

        boardInstance.setDimensions(x, y);

        NQueens fq = new NQueens(); 
        fq.solveBoard(0);  
    } 
}

Output #1:

Enter board size:
4 4

_ Q _ _
_ _ _ Q
Q _ _ _
_ _ Q _


_ _ Q _
Q _ _ _
_ _ _ Q
_ Q _ _



Output #2:

Enter board size  //(although chess boards aren't non-square):
2 6

Q _ _ _ _ _
_ _ Q _ _ _


Q _ _ _ _ _
_ _ _ Q _ _


Q _ _ _ _ _
_ _ _ _ Q _


Q _ _ _ _ _
_ _ _ _ _ Q


_ Q _ _ _ _
_ _ _ Q _ _


_ Q _ _ _ _
_ _ _ _ Q _


_ Q _ _ _ _
_ _ _ _ _ Q


_ _ Q _ _ _
Q _ _ _ _ _


_ _ Q _ _ _
_ _ _ _ Q _


_ _ Q _ _ _
_ _ _ _ _ Q


_ _ _ Q _ _
Q _ _ _ _ _


_ _ _ Q _ _
_ Q _ _ _ _


_ _ _ Q _ _
_ _ _ _ _ Q


_ _ _ _ Q _
Q _ _ _ _ _


_ _ _ _ Q _
_ Q _ _ _ _


_ _ _ _ Q _
_ _ Q _ _ _


_ _ _ _ _ Q
Q _ _ _ _ _


_ _ _ _ _ Q
_ Q _ _ _ _


_ _ _ _ _ Q
_ _ Q _ _ _


_ _ _ _ _ Q
_ _ _ Q _ _



Output #3:

Enter board size:
6 6

_ Q _ _ _ _
_ _ _ Q _ _
_ _ _ _ _ Q
Q _ _ _ _ _
_ _ Q _ _ _
_ _ _ _ Q _


_ _ Q _ _ _
_ _ _ _ _ Q
_ Q _ _ _ _
_ _ _ _ Q _
Q _ _ _ _ _
_ _ _ Q _ _


_ _ _ Q _ _
Q _ _ _ _ _
_ _ _ _ Q _
_ Q _ _ _ _
_ _ _ _ _ Q
_ _ Q _ _ _


_ _ _ _ Q _
_ _ Q _ _ _
Q _ _ _ _ _
_ _ _ _ _ Q
_ _ _ Q _ _
_ Q _ _ _ _ 

No comments:

Post a Comment