package com.company;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Random;

public class Board1 {

    private int numOfQueens;
    private ArrayList<Integer> configuration;
    private int[][] conflicts;
    private Random random = new Random();
    private int queensConflicts = 0;

    Board1(int numOfQueens) {
        this.numOfQueens = numOfQueens;
        setConfiguration();
    }

    private void setConfiguration() {
        configuration = new ArrayList<>(numOfQueens);
        conflicts = new int[numOfQueens][numOfQueens];
        queensConflicts = 0;
        int randIndexInFirstRow = random.nextInt(numOfQueens);
        Coordinates coordinatesOfFirstQueen = new Coordinates(0, randIndexInFirstRow);
        configuration.add(randIndexInFirstRow);
        updateConflictsForQueen(coordinatesOfFirstQueen, Update.INCREMENT);
        int i = 1;
        while(i < numOfQueens) {
            int indexOfQueen = minConflictsIndexesPerRow(i);
            configuration.add(indexOfQueen);
            Coordinates coordinatesOfQueen = new Coordinates(i, indexOfQueen);
            updateConflictsForQueen(coordinatesOfQueen, Update.INCREMENT);
            i++;
        }
    }

    private  void updateConflictsForQueen(Coordinates queenCoordinates, Update update) {
        if(update == Update.INCREMENT) {
                int row = queenCoordinates.getX() - 1;
                int left = queenCoordinates.getY() - 1;
                int above = queenCoordinates.getY();
                int right = queenCoordinates.getY() + 1;

                while (row >= 0) {
                    if(left >= 0) conflicts[row][left]++;
                    conflicts[row][above]++;
                    if(right < numOfQueens) conflicts[row][right]++;

                    left--;
                    row--;
                    right++;
                }

                row = queenCoordinates.getX() + 1;
                left = queenCoordinates.getY() - 1;
                int down = queenCoordinates.getY();
                right = queenCoordinates.getY() + 1;

                while (row < numOfQueens) {
                    if(left >= 0) conflicts[row][left]++;
                    conflicts[row][down]++;
                    if(right < numOfQueens) conflicts[row][right]++;

                left--;
                row++;
                right++;
            }
        }
        else {
            int row = queenCoordinates.getX() - 1;
            int left = queenCoordinates.getY() - 1;
            int above = queenCoordinates.getY();
            int right = queenCoordinates.getY() + 1;

            while (row >= 0) {
                if(left >= 0) conflicts[row][left]--;
                conflicts[row][above]--;
                if(right < numOfQueens) conflicts[row][right]--;

                left--;
                row--;
                right++;
            }

            row = queenCoordinates.getX() + 1;
            left = queenCoordinates.getY() - 1;
            int down = queenCoordinates.getY();
            right = queenCoordinates.getY() + 1;

            while (row < numOfQueens) {
                if(left >= 0) conflicts[row][left]--;
                conflicts[row][down]--;
                if(right < numOfQueens) conflicts[row][right]--;

                left--;
                row++;
                right++;
            }
        }
    }

    void solve() {
        int moves = 0;
        int restart = 0;

        while(true) {
            int worstQueenIndex = findMostConflicted();
            if(queensConflicts == 0) {
                System.out.println("Move: " + moves + " Restarts: " + restart);
                return;
            }
            int minConflictIndex = minConflictsIndexesPerRow(worstQueenIndex);
            moveQueen(worstQueenIndex, minConflictIndex);
            if(moves == 100 || minConflictIndex == -1) {
                setConfiguration();
                moves = 0;
                restart++;
            }
            moves++;
        }
    }

    public void print(PrintStream stream) {
        for(int i = 0; i < configuration.size(); i++) {
            for(int j = 0; j < configuration.size(); j++) {
                stream.print(configuration.get(i) == j ? "* " : "_ ");
            }
            stream.println();
        }
    }

    private void moveQueen(int rowOfQueen, int indexOfMin) {
        Coordinates oldPlaceQueen = new Coordinates(rowOfQueen, configuration.get(rowOfQueen));
        Coordinates newPlaceQueen = new Coordinates(rowOfQueen, indexOfMin);
        //Not to move queen and the same place
        if(!oldPlaceQueen.equalCoordinates(newPlaceQueen) && indexOfMin != -1) {
            configuration.set(rowOfQueen, indexOfMin);
            updateConflictsForQueen(newPlaceQueen, Update.INCREMENT);
            updateConflictsForQueen(oldPlaceQueen, Update.DECREMENT);
        }
    }

    private int minConflictsIndexesPerRow(int row) {
        ArrayList<Integer> minConflicted = new ArrayList<>();
        int minConflicts = numOfQueens;
        for (int col = 0; col < numOfQueens; col++) {
            int numberOfConflicts = conflicts[row][col];
            if (numberOfConflicts == minConflicts) {
                minConflicted.add(col);
            }
            else if (numberOfConflicts < minConflicts) {
                minConflicts = numberOfConflicts;
                minConflicted.clear();
                minConflicted.add(col);
            }
        }
        //if the row has no min conflicts, we have no option to move the queen
        if(minConflicted.size() == numOfQueens - 1) {
            return -1;
        }
        int index = random.nextInt(minConflicted.size());
        return minConflicted.get(index);
    }

    private int findMostConflicted() {
        ArrayList<Integer> maxConflicted = new ArrayList<>();
        int maxConflicts = 0;
        queensConflicts = 0;
        for (int row = 0; row < numOfQueens; row++) {
            int numberOfConflicts = conflicts[row][configuration.get(row)];
            if (numberOfConflicts == maxConflicts) {
                maxConflicted.add(row);
            }
            else if (numberOfConflicts > maxConflicts) {
                maxConflicts = numberOfConflicts;
                queensConflicts = maxConflicts;
                maxConflicted.clear();
                maxConflicted.add(row);
            }
        }
        int index = random.nextInt(maxConflicted.size());
        return maxConflicted.get(index);
    }
}