N-Queen Problem

The eight queen’s puzzle is the problem of placing eight chess queens on an 8 x 8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

Backtracking eliminates or avoids the partial candidate solutions as soon as it finds that that path cannot lead to a solution. We are given 4 x 4 chessboard and we need to place 4 queens in non-attacking places on this board.

source Code

package com.dsacode.Algorithm.backtracking;
 
public class NQueens {
 
    int[] x;
 
    public NQueens(int N) {
        x = new int[N];
    }
 
    public boolean canPlaceQueen(int r, int c) {
        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) {
        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[]) {
        NQueens Q = new NQueens(4);
        System.out.println("Solution for 4 Queen Problem");
        Q.callplaceNqueens();
      
    }
}

Output

Solution for 4 Queen Problem
* Q * *
* * * Q
Q * * *
* * Q *
 
* * Q *
Q * * *
* * * Q
* Q * *

Algorithm Explanation

	Divide problem into sub problem of placing a single queen on the chess board.
	If this leads to a solution, check any of the already placed queens attacks this position.
	If yes, then go to next column. If no, then place this queen and move on to next queen.

Reference

1. https://en.wikipedia.org/wiki/Eight_queens_puzzle
2. http://mathworld.wolfram.com/QueensProblem.html
3. https://developers.google.com/optimization/puzzles/queens
4. https://www.cs.usfca.edu/~galles/visualization/RecQueens.html
5. https://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/introduction/4queens.html