Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement