// http://en.literateprograms.org/Special:Downloadcode/Eight_queens_puzzle_%28C%29

import std.stdio: writef, writefln;
import std.conv: toInt;

int queens_solutions(int n) {
    int queen_num_1, current_queen, num_solutions;
    int is_valid, went_off_right_side; // int instead of bool for speed

    auto queen_rows = new int[n];
    auto queen_cols = new int[n];
    auto col_in_use = new int[n + 1];

    for (int queen_num; queen_num < n; queen_num++)
        queen_rows[queen_num] = queen_num;
    queen_cols[] = -1;

    while (current_queen >= 0) {
        if (queen_cols[current_queen] != -1)
            col_in_use[queen_cols[current_queen]] = 0;

        do {
            // Find next open column
            do {
                queen_cols[current_queen]++;
            } while (col_in_use[queen_cols[current_queen]]);

            went_off_right_side = (queen_cols[current_queen] >= n) ||
                                  (current_queen == 0 && queen_cols[0] > (n-1)/2);
            if (went_off_right_side)
                break;

            // Check for diagonals
            is_valid = true;
            queen_num_1 = current_queen;
            for (int queen_num_2; queen_num_2 < queen_num_1; queen_num_2++) {
                if (queen_rows[queen_num_1] - queen_rows[queen_num_2] ==
                    queen_cols[queen_num_1] - queen_cols[queen_num_2] ||
                    queen_rows[queen_num_1] - queen_rows[queen_num_2] ==
                    -(queen_cols[queen_num_1] - queen_cols[queen_num_2])) {
                    is_valid = false;
                    break;
                }
            }
        } while (!is_valid);

        if (!went_off_right_side) {
            col_in_use[queen_cols[current_queen]] = 1;
            if (current_queen + 1 < n) {
                current_queen++;
                queen_cols[current_queen] = -1;
            } else {
                if (num_solutions == 0) {
                    for (int queen_num; queen_num < n; queen_num++)
                        writef("(%d,%d) ", queen_rows[queen_num], queen_cols[queen_num]);
                    writefln;
                }
                num_solutions++;
                if (queen_cols[0] < n/2)
                    num_solutions++; // add mirrored solution
            }
        } else {
            // backtrack
            queen_cols[current_queen] = -1;
            current_queen--;
        }
    }

    return num_solutions;
}


void main(string[] args) {
    int n = args.length == 2 ? toInt(args[1]) : 14;
    writefln("Board side = ", n);
    writefln("Number of solutions: ", queens_solutions(n));
}

Timeout