8Queens

import java.util.Scanner;

public class Main {

    static class QueenProblem {
        final int N = 8;
        int k = 1;
        int counter = 1;

        void printSolution(int board[][], int linha, int coluna) {
            if (board[linha - 1][coluna - 1] == 1) {
                if (k <= 9) {
                    System.out.print(" " + k++ + "      ");
                } else {
                    System.out.print(k++ + "      ");
                }
                for (int j = 0; j < N; j++) {
                    for (int i = 0; i < N; i++) {
                        if (board[i][j] == 1) {
                            if (counter <= 7) {
                                System.out.print((i + 1) + " ");
                                counter++;
                                break;
                            } else {
                                System.out.print(i + 1);
                                counter++;
                                break;
                            }
                        }
                    }
                }
                System.out.println();
            }
            counter = 0;
        }

        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;
        }

        boolean solveNQUtil(int board[][], int col, int linha, int coluna) {

            if (col >= N) {
                printSolution(board, linha, coluna);
                return true;
            }

            boolean res = false;
            for (int i = 0; i < N; i++) {

                if (isSafe(board, i, col)) {
                    /* Place this queen in board[i][col] */
                    board[i][col] = 1;

                    res = solveNQUtil(board, col + 1, linha, coluna) || res;

                    board[i][col] = 0; // BACKTRACK
                }
            }
            return res;
        }

        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();
            for (int a = 0; a < data_set; a++) {
                int linha = in.nextInt();
                int coluna = in.nextInt();
                QueenProblem Queen = new QueenProblem();
                System.out.print("SOLN       COLUMN\n");
                System.out.print(" #      1 2 3 4 5 6 7 8\n\n");
                Queen.solveNQ(linha, coluna);
                if (a != data_set - 1) {
                    System.out.println();
                }
            }
        }
    }
}