SHARE
TWEET

Untitled

a guest Jan 27th, 2015 235 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package testcode;
  2.  
  3. import java.util.ArrayList;
  4.  
  5. class Grid {
  6.     int[][] grid = new int[8][8];
  7.     ArrayList<int[]> queens = new ArrayList<int[]>();
  8.  
  9.     public void addQueen(int[] b) {
  10.         addQueen(b[0], b[1]);
  11.     }
  12.  
  13.     public void addQueen(int x, int y) {
  14.         grid[x][y] = 2;
  15.         queens.add(new int[]{x, y});
  16.     }
  17.  
  18.     public void reduceGrid() {
  19.         for(int x = 0; x < 8; x++) {
  20.             for(int y = 0; y < 8; y++) {
  21.                 if(grid[x][y] == 2) continue;
  22.                
  23.                 for(int[] b : queens) {
  24.                     if(b[0] == x || b[1] == y) {grid[x][y] = 1; continue;}
  25.                     if(Math.abs(b[0] - x) == Math.abs(b[1] - y)) {grid[x][y] = 1; continue;}
  26.                 }
  27.             }
  28.         }
  29.     }
  30.  
  31.     public ArrayList<int[]> getUncoveredCoords() {
  32.         ArrayList<int[]> p = new ArrayList<>();
  33.         for(int x = 0; x < 8; x++)
  34.             for(int y = 0; y < 8; y++)
  35.                 if(grid[x][y] == 0)
  36.                     p.add(new int[]{x, y});
  37.         return p;
  38.     }
  39.  
  40.     public int countUncovered() {
  41.         int c = 0;
  42.         for(int x = 0; x < 8; x++)
  43.             for(int y = 0; y < 8; y++)
  44.                 if(grid[x][y] == 0)
  45.                     c++;
  46.         return c;
  47.     }
  48.  
  49.     @Override
  50.     public String toString() {
  51.         String s = "";
  52.         for(int x = 0; x < 8; x++) {
  53.             for(int y = 0; y < 8; y++)
  54.                 s += grid[x][y] + " ";
  55.             s += "\n";
  56.         }
  57.         return s;
  58.     }
  59. }
  60.  
  61. public class TestCode18 {
  62.     public static void main(String[] args) {
  63.         int minUncovered = 64;
  64.         ArrayList<Grid> minCases = new ArrayList<>();
  65.  
  66.         for(int x = 0; x < 8; x++) {
  67.             for(int y = 0; y < 8; y++) {
  68.                 System.out.println("Iter " + (x * 8 + y + 1));
  69.  
  70.                 int[] Q1 = new int[]{x, y};
  71.                 Grid g = new Grid();
  72.                 g.addQueen(Q1);
  73.                 g.reduceGrid();
  74.                 ArrayList<int[]> coordQ1 = g.getUncoveredCoords();
  75.  
  76.                 for(int[] Q2 : coordQ1) { //then iterate over them.
  77.                     Grid g2 = new Grid(); //Make and reduce a new grid
  78.                     g2.addQueen(Q1); g2.addQueen(Q2);
  79.                     g2.reduceGrid();
  80.                     ArrayList<int[]> coordQ2 = g.getUncoveredCoords();
  81.  
  82.                     for(int[] Q3 : coordQ2) { //then iterate over them.
  83.                         Grid g3 = new Grid(); //Make and reduce a new grid
  84.                         g3.addQueen(Q1); g3.addQueen(Q2); g3.addQueen(Q3);
  85.                         g3.reduceGrid();
  86.                         ArrayList<int[]> coordQ3 = g.getUncoveredCoords(); //ad infinitum
  87.  
  88.                         for(int[] Q4 : coordQ3) {
  89.                             Grid g4 = new Grid(); //Make and reduce a new grid
  90.                             g4.addQueen(Q1); g4.addQueen(Q2); g4.addQueen(Q3); g4.addQueen(Q4);
  91.                             g4.reduceGrid();
  92.  
  93.                             //If the current case is less than the minimal case, print it and update the list.
  94.                             if(g4.countUncovered() < minUncovered) {
  95.         minCases = new ArrayList<>();
  96.         minCases.add(g4);
  97.         minUncovered = g4.countUncovered();
  98.  
  99.         System.out.println(g4 + "" + g4.countUncovered() + "\n");
  100.                             }
  101.  
  102.                             if(g4.countUncovered() == minUncovered)
  103.         minCases.add(g4);
  104.                         }
  105.                     }
  106.                 }
  107.             }
  108.         }
  109.  
  110.         for(Grid gr : minCases)
  111.             System.out.println(gr + "\n");
  112.         System.out.println(minCases.get(0).countUncovered() + " is the maximum squares covered.");
  113.        
  114.         for(Grid gr : minCases) {
  115.             for(int[] b : gr.getUncoveredCoords()) {
  116.                 System.out.print(b[0] + "," + b[1] + " | ");
  117.             }
  118.             int x1 = gr.getUncoveredCoords().get(0)[0];
  119.             int y1 = gr.getUncoveredCoords().get(0)[1];
  120.             int x2 = gr.getUncoveredCoords().get(1)[0];
  121.             int y2 = gr.getUncoveredCoords().get(1)[1];
  122.             System.out.println(Math.abs(x2-x1) + "," + Math.abs(y2-y1));
  123.            
  124.             //if(Math.abs(x2-x1) != Math.abs(y2-y1)) System.out.println(gr);
  125.            
  126.             //System.out.println(gr.getUncoveredCoords());
  127.         }
  128.     }
  129. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top