The n-queens problem in Java

Posted By: Java Examples - 10:38 PM

Share

& Comment

A classic combinatorial problem is to place n queens on an n × n chess board so that no queen threatens any other queen, that is, so that no two queens are on the same row, column, or diagonal. In order to reduce this solution space, it can now be assumed without loss of generality, that the ith queen is placed in the ith row, thereby avoiding those two queens can be in the same row. 

All solutions to the n-queens problem can therefore be represented as ntuples (c1, c2, . . . cn), where ci is column on which queen i is placed, and no two ciscan be the same. Each queen is assigned a different column, so the only thing left to check is whether two queens are in the same diagonal. The rows are now numbered from bottom to top and the columns are numbered from left to right Hence the bottom left corner has the coordinates (0,0) and the top left corner (n-1,0). With this numeration, two queens with the coordinates (i, ci) and (j, cj) are in the same ascending diagonal if j −i == cjci. They are in the same descending diagonal if j −i == ci − cj. Thus, in order to check whether two queens are in the same diagonal, no matter in which direction, it is sufficient to check whether |j − i| == |cj − ci| or not.




Java version of the  n-queens problem  is given below: 

/**
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package queens;

/**
 *
 * @author ACHCHUTHAN
 */
public class Queens {

    int[] x;

    public Queens(int N) {
        x = new int[N];
    }

    public boolean canPlaceQueen(int r, int c) {
        /**
         * Returns TRUE if a queen can be placed in row r and column c.
         * Otherwise it returns FALSE. x[] is a global array whose first (r-1)
         * values have been set.
         */
        for (int i = 0; i < r; i++) {
            if (x[i] == c || (i - r) == (x[i] - c) ||(i - r) == (c - x[i])) 
            {
                return false;
            }
        }
        return true;
    }

    public void printQueens(int[] x) {
        int N = x.length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (x[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    public void placeNqueens(int r, int n) {
        /**
         * Using backtracking this method prints all possible placements of n
         * queens on an n x n chessboard so that they are non-attacking.
         */
        for (int c = 0; c < n; c++) {
            if (canPlaceQueen(r, c)) {
                x[r] = c;
                if (r == n - 1) {
                    printQueens(x);
                } else {
                    placeNqueens(r + 1, n);
                }
            }
        }
    }

    public void callplaceNqueens() {
        placeNqueens(0, x.length);
    }

    public static void main(String args[]) {
        Queens Q = new Queens(8);
        Q.callplaceNqueens();
     
    }
}


Output of this program is given bellow :
run:
* Q * * 
* * * Q 
Q * * * 
* * Q * 
* * Q * 
Q * * * 
* * * Q 
* Q * * 

BUILD SUCCESSFUL (total time: 1 second)

About Java Examples

I’m passionate about Web Development and Programming and I go to extreme efforts to meet my passion. I’m a believer of learning the fundamentals first. I try to understand everything little bit more than the average.

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .