public class Dronninger {
    private Felt[][] brett;
    private int storrelse;

    public Dronninger(int storrelse) {
        this.storrelse = storrelse;
        brett = new Felt[storrelse][storrelse];

        for (int rad = 0; rad < storrelse; rad++) {
            for (int kol = 0; kol < storrelse; kol++) {
                brett[rad][kol] = new Felt();
            }
        }
    }

    public boolean loes(int kolonne) {
        if (kolonne == storrelse) {
            return true;
        }
        for (int rad = 0; rad < storrelse; rad++) {
            if (lovligPlassering(rad, kolonne)) {
                brett[rad][kolonne].tatt = true;

                if (loes(kolonne + 1)) {
                    return true;
                }

                brett[rad][kolonne].tatt = false;
            }
        }
        return false;
    }

    public void printBrett() {
        for (int rad = 0; rad < storrelse; rad++) {
            for (int kol = 0; kol < storrelse; kol++) {
                System.out.print(brett[rad][kol].tatt ? "Q " : "- ");
            }
            System.out.println();
        }
    }

    /**
     * Returnerer hvorvidt det er lovlig aa plassere en dronning paa en
     * gitt rad og kolonne. Plasseringen er lovlig bare hvis dronningen ikke er under
     * angrep av en allerede plassert dronning.
     *
     * @return true hvis plasseringen er lovlig, ellers false.
     */
    private boolean lovligPlassering(int rad, int kol) {
        for (int y = 0; y < storrelse; y++) {
            if (brett[rad][y].tatt) {
                return false;
            }
        }

        for (int y = Math.max(rad-kol, 0), x = Math.max(kol-rad, 0); y < storrelse && x < storrelse; y++, x++) {
            if (brett[y][x].tatt) {
                return false;
            }
        }

        int speilrad = (storrelse-1)-rad;
        for (int y = Math.max(speilrad-kol, 0), x = Math.max(kol-speilrad, 0); y < storrelse && x < storrelse; y++, x++) {
            if (brett[(storrelse-1)-y][x].tatt) {
                return false;
            }
        }

        return true;
    }

    private static class Felt {
        public boolean tatt = false;
    }
}