import java.util.Arrays;

public class NQueens {

    static final int UKURAN = 4;
    static int[] posisi = new int[UKURAN];   // posisi[baris] = kolom ratu
    static int jumlahSolusi = 0;
    static long percobaan;

    public static void main(String[] args) {
        System.out.println("=== N-Queens " + UKURAN + "x" + UKURAN
                + ": semua solusi ===");
        tempatkan(0);
        System.out.println("Total solusi: " + jumlahSolusi);
        System.out.println("Total percobaan penempatan ratu: " + percobaan);
    }

    // Coba semua kolom pada satu baris; naik satu baris setelah penempatan aman.
    static void tempatkan(int baris) {
        if (baris == UKURAN) {
            jumlahSolusi++;
            cetakPapan();
            return;
        }
        for (int kolom = 0; kolom < UKURAN; kolom++) {
            percobaan++;
            if (aman(baris, kolom)) {
                posisi[baris] = kolom;    // pilih: taruh ratu
                tempatkan(baris + 1);     // telusuri baris berikutnya
                // mundur: posisi[baris] akan tertimpa pada iterasi berikutnya
            }
        }
    }

    static boolean aman(int baris, int kolom) {
        for (int b = 0; b < baris; b++) {
            if (posisi[b] == kolom) {
                return false;    // ada ratu pada kolom yang sama
            }
            if (Math.abs(posisi[b] - kolom) == baris - b) {
                return false;    // ada ratu pada diagonal yang sama
            }
        }
        return true;
    }

    static void cetakPapan() {
        System.out.println("Solusi " + jumlahSolusi + ": kolom per baris = "
                + Arrays.toString(posisi));
        for (int baris = 0; baris < UKURAN; baris++) {
            StringBuilder sb = new StringBuilder("  ");
            for (int kolom = 0; kolom < UKURAN; kolom++) {
                sb.append(kolom == posisi[baris] ? "Q " : ". ");
            }
            System.out.println(sb);
        }
        System.out.println();
    }
}