## 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 _ _ _ _