NQueens

import java.util.Scanner;

/* Java program to solve N Queen Problem using
   backtracking */
public class NQueenProblem {
    final int N = 8;
    static int k = 1;
    int output[] = new int[N];

    /* A utility function to print solution */
    void printSolution(int board[][], int linha, int coluna) {
        if (board[linha - 1][coluna - 1] == 1) {
            System.out.print(" " + k++ + "      ");
            for (int j = 0; j < N; j++) {
                for (int i = 0; i < N; i++) {
                    if (board[i][j] == 1) {
                        System.out.print((i+1) + " ");
                        break;
                    }
                }
            }
            System.out.println();
        }
    }

    /*
     * A utility function to check if a queen can be placed on board[row][col]. Note
     * that this function is called when "col" queens are already placeed in columns
     * from 0 to col -1. So we need to check only left side for attacking queens
     */
    boolean isSafe(int board[][], int row, int col) {
        int i, j;

        /* Check this row on left side */
        for (i = 0; i < col; i++)
            if (board[row][i] == 1)
                return false;

        /* Check upper diagonal on left side */
        for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
            if (board[i][j] == 1)
                return false;

        /* Check lower diagonal on left side */
        for (i = row, j = col; j >= 0 && i < N; i++, j--)
            if (board[i][j] == 1)
                return false;

        return true;
    }

    /*
     * A recursive utility function to solve N Queen problem
     */
    boolean solveNQUtil(int board[][], int col, int linha, int coluna) {
        /*
         * base case: If all queens are placed then return true
         */
        if (col == N) {
            printSolution(board, linha, coluna);
            return true;
        }
        boolean res = false;
        /*
         * Consider this column and try placing this queen in all rows one by one
         */
        for (int i = 0; i < N; i++) {
            /*
             * Check if queen can be placed on board[i][col]
             */
            if (isSafe(board, i, col)) {
                /* Place this queen in board[i][col] */
                board[i][col] = 1;
                res = solveNQUtil(board, col + 1, linha, coluna) || res;

                /* recur to place rest of the queens */
                if (solveNQUtil(board, col + 1, linha, coluna) == true)
                    return true;

                /*
                 * If placing queen in board[i][col] doesn't lead to a solution then remove
                 * queen from board[i][col]
                 */
                board[i][col] = 0; // BACKTRACK
            }
        }

        /*
         * If queen can not be place in any row in this colum col, then return false
         */
        return res;
    }

    /*
     * This function solves the N Queen problem using Backtracking. It mainly uses
     * solveNQUtil() to solve the problem. It returns false if queens cannot be
     * placed, otherwise return true and prints placement of queens in the form of
     * 1s. Please note that there may be more than one solutions, this function
     * prints one of the feasible solutions.
     */
    void solveNQ(int linha, int coluna) {
        int board[][] = new int[N][N];

        if (solveNQUtil(board, 0, linha, coluna) == false) {
            System.out.print("Solution does not exist");
            return;
        }

        return;
    }

    // driver program to test above function
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int data_set = in.nextInt();
        int linha = in.nextInt();
        int coluna = in.nextInt();
        NQueenProblem Queen = new NQueenProblem();
        System.out.print("SOLN       COLUMN\n");
        System.out.print(" #      1 2 3 4 5 6 7 8\n\n");
        Queen.solveNQ(linha, coluna);
    }
}