/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package queenscombinations;

/**
 *
 * @author Demid
 */
public class QueensCombinations {

    final static int N = 8;

    static int combinationsCount;

    /**
     * Sets value to the position only if it's current value equals currentValue
     */
    static void setIf(int[][] board, int x, int y, int value, int currentValue) {
        if (board[x][y] == currentValue) {
            board[x][y] = value;
        }
    }

    /**
     * Puts/removes the Queen on the position. Marks/unmarks all position on
     * rows below that are under attack by this Queen
     */
    static void toggleQueen(int[][] board, int x, int y) {
        int value, opposite;
        if (board[x][y] == 0) {
            value = x + 1;
            opposite = 0;
        } else {
            value = 0;
            opposite = x + 1;
        }

        for (int i = x; i < N; i++) {
            setIf(board, i, y, value, opposite);
        }

        //main diagonal
        int difference = Math.abs(x - y);
        int length = N - difference;
        if (x <= y) {
            for (int i = x + 1; i < length; i++) {
                setIf(board, i, difference + i, value, opposite);
            }
        } else {
            for (int j = y + 1; j < length; j++) {
                setIf(board, difference + j, j, value, opposite);
            }
        }
        //secondary diagonal
        int sum = x + y;
        if (sum < N) {
            for (int j = 0; j <= y - 1; j++) {
                setIf(board, sum - j, j, value, opposite);
            }
        } else {
            for (int i = N - 1; i >= x + 1; i--) {
                setIf(board, i, sum - i, value, opposite);
            }
        }
    }

    /**
     * Recursion with backtracking. Puts the Queen on each position in a row and
     * calls itself on below row.
     */
    static int processRow(int[][] board, int row) {
        for (int i = 0; i < N; i++) {
            if (board[row][i] == 0) {
                if (row == N - 1) {
                    //print(board);
                    combinationsCount++;
                } else {
                    toggleQueen(board, row, i);
                    processRow(board, row + 1);
                    toggleQueen(board, row, i);
                }
            }
        }
        return combinationsCount;
    }

    /**
     * main method
     *
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int[][] board = new int[N][N];
        System.out.println(processRow(board, 0));
    }

    public static void print(int[][] a) {
        System.out.println();
        for (int i = 0; i < N; i++) {
            System.out.println();
            for (int j = 0; j < N; j++) {
                System.out.print(Math.abs(a[i][j]) + " ");
            }
        }

    }
}