package testcode;

import java.util.ArrayList;

class Grid {
    int[][] grid = new int[8][8];
    ArrayList<int[]> queens = new ArrayList<int[]>();

    public void addQueen(int[] b) {
        addQueen(b[0], b[1]);
    }

    public void addQueen(int x, int y) {
        grid[x][y] = 2;
        queens.add(new int[]{x, y});
    }

    public void reduceGrid() {
        for(int x = 0; x < 8; x++) {
            for(int y = 0; y < 8; y++) {
                if(grid[x][y] == 2) continue;

                for(int[] b : queens) {
                    if(b[0] == x || b[1] == y) {grid[x][y] = 1; continue;}
                    if(Math.abs(b[0] - x) == Math.abs(b[1] - y)) {grid[x][y] = 1; continue;}
                }
            }
        }
    }

    public ArrayList<int[]> getUncoveredCoords() {
        ArrayList<int[]> p = new ArrayList<>();
        for(int x = 0; x < 8; x++)
            for(int y = 0; y < 8; y++)
                if(grid[x][y] == 0)
                    p.add(new int[]{x, y});
        return p;
    }

    public int countUncovered() {
        int c = 0;
        for(int x = 0; x < 8; x++)
            for(int y = 0; y < 8; y++)
                if(grid[x][y] == 0)
                    c++;
        return c;
    }

    @Override
    public String toString() {
        String s = "";
        for(int x = 0; x < 8; x++) {
            for(int y = 0; y < 8; y++)
                s += grid[x][y] + " ";
            s += "\n";
        }
        return s;
    }
}

public class TestCode18 {
    public static void main(String[] args) {
        int minUncovered = 64;
        ArrayList<Grid> minCases = new ArrayList<>();

        for(int x = 0; x < 8; x++) {
            for(int y = 0; y < 8; y++) {
                System.out.println("Iter " + (x * 8 + y + 1));

                int[] Q1 = new int[]{x, y};
                Grid g = new Grid();
                g.addQueen(Q1);
                g.reduceGrid();
                ArrayList<int[]> coordQ1 = g.getUncoveredCoords();

                for(int[] Q2 : coordQ1) { //then iterate over them.
                    Grid g2 = new Grid(); //Make and reduce a new grid
                    g2.addQueen(Q1); g2.addQueen(Q2);
                    g2.reduceGrid();
                    ArrayList<int[]> coordQ2 = g.getUncoveredCoords();

                    for(int[] Q3 : coordQ2) { //then iterate over them.
                        Grid g3 = new Grid(); //Make and reduce a new grid
                        g3.addQueen(Q1); g3.addQueen(Q2); g3.addQueen(Q3);
                        g3.reduceGrid();
                        ArrayList<int[]> coordQ3 = g.getUncoveredCoords(); //ad infinitum

                        for(int[] Q4 : coordQ3) {
                            Grid g4 = new Grid(); //Make and reduce a new grid
                            g4.addQueen(Q1); g4.addQueen(Q2); g4.addQueen(Q3); g4.addQueen(Q4);
                            g4.reduceGrid();

                            //If the current case is less than the minimal case, print it and update the list.
                            if(g4.countUncovered() < minUncovered) {
    minCases = new ArrayList<>();
    minCases.add(g4);
    minUncovered = g4.countUncovered();

    System.out.println(g4 + "" + g4.countUncovered() + "\n");
                            }

                            if(g4.countUncovered() == minUncovered)
    minCases.add(g4);
                        }
                    }
                }
            }
        }

        for(Grid gr : minCases)
            System.out.println(gr + "\n");
        System.out.println(minCases.get(0).countUncovered() + " is the maximum squares covered.");

        for(Grid gr : minCases) {
            for(int[] b : gr.getUncoveredCoords()) {
                System.out.print(b[0] + "," + b[1] + " | ");
            }
            int x1 = gr.getUncoveredCoords().get(0)[0];
            int y1 = gr.getUncoveredCoords().get(0)[1];
            int x2 = gr.getUncoveredCoords().get(1)[0];
            int y2 = gr.getUncoveredCoords().get(1)[1];
            System.out.println(Math.abs(x2-x1) + "," + Math.abs(y2-y1));

            //if(Math.abs(x2-x1) != Math.abs(y2-y1)) System.out.println(gr);

            //System.out.println(gr.getUncoveredCoords());
        }
    }
}