//Urheber: Jonathan Püttmann 2020
//Quelle: www.mengenwertskala.de/informatik/quickRecChess.java
//Dieses Programm ist freigegeben zur Weiterverwendung und -entwicklung im Sinne der Freie-Software-Bewegung
//Bugs und Verbesserungsvorschläge an kontakt@mengenwertskala.de

import java.util.ArrayList;

public class Play {

    public static void main(String[] args) {
        final double timeStart = System.currentTimeMillis();
        Board board = new Board(13, 13);
        board.quickRecSearch(0, new ArrayList<>());
        final double timeEnd = System.currentTimeMillis();
        System.out.println();
        System.out.println("Vergleiche: " + board.getCounter());
        System.out.println("Zeit: " + (timeEnd - timeStart)/1000 + " Sekunden");
    }

}

public class Board {

    public Board(int spalten, int reihen) {
        this.spalten = spalten;
        this.reihen = reihen;
    }
    
    int spalten;
    int reihen;
    public static double counter = 0;
    public static int solNumber = 0;
    public double getCounter() {return this.counter;}
    
    public void quickRecSearch (int tiefe, ArrayList<Queen> queens) {
        if (tiefe==this.spalten){
            solNumber++;                                //Nummer der Lösung
            System.out.print(solNumber + "-> ");
            for (Queen queen : queens) System.out.print(queen.yPos + " | ");
            System.out.println();
        } else {
            tiefe ++;                                   //Tiefe im Suchbaum
            for (int i = 1; i<=this.reihen; i++) {
                counter++;                              //Anzahl der Stellungsvergleiche
                Queen newQ = new Queen(tiefe, i);
                boolean valid = true;
                for (Queen q : queens) if (!newQ.valid2(q)) valid = false;
                if (valid) {
                    ArrayList<Queen> newQueens = new ArrayList<>();
                    newQueens.addAll(queens);
                    newQueens.add(newQ);
                    quickRecSearch(tiefe, newQueens);   //Rekursiver Aufruf für nächste Spalte
                }
            }
        }
    }
}

public class Queen {

    public Queen(int xPos, int yPos){
        this.xPos = xPos;
        this.yPos = yPos;
    }

    public int xPos;
    public int yPos;
    
    public boolean valid2(Queen q) {
        int x1 = this.xPos;
        int y1 = this.yPos;
        int x2 = q.xPos;
        int y2 = q.yPos;
        int dx = Math.abs(x2-x1);
        int dy = Math.abs(y2-y1);
        return (!(y1==y2 || dx==dy));
    }
}