Pastebin launched a little side project called HostCabi.net, check it out ;-)Don't like ads? PRO users don't see any ads ;-)
Guest

Untitled

By: a guest on Mar 26th, 2010  |  syntax: None  |  size: 3.81 KB  |  hits: 95  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. package JEG_SKAL_BLI_PRO;
  2.  
  3. import java.util.Scanner;
  4.  
  5. public class Queens {
  6.     public static void main(String[] a) {
  7.         Scanner in = new Scanner(System.in);
  8.  
  9.         int[][] grid = new int[8][8];
  10.         boolean success;
  11.        
  12.        Moves moves = new Moves();
  13.  
  14.        for(int i=0;i < 8;i++) {
  15.  
  16.                         success = false; // initially no queen is placed
  17.                        
  18.                 for(int j=0;j < 8;j++) {
  19.  
  20.                     /* THIS IS FOR DEBUGGING */
  21.                      /*  place(i,j,grid,4);
  22.                     p(grid);
  23.                     String s = in.nextLine();
  24.                     place(i,j,grid,0);   */
  25.  
  26.                     if(isLegal(i,j,grid)) {
  27.                         place(i,j,grid);
  28.                         success = true; // A queen is placed  
  29.                         Integer[] move = {i ,j};  // autoboxing
  30.                         moves.push(move); // push the move onto the stack
  31.                         break;
  32.                     }
  33.                
  34.                         // check if a queen was placed. Or if not enough queens have been placed
  35.                         if( (! success && j == 7) || (i == 7 && j == 7 && moves.length() < 8)) {
  36.                                 // System.out.println("failure");
  37.                                 Integer[] lastMove = moves.pop();
  38.                                 int lastY = lastMove[0];
  39.                                 int lastX = lastMove[1];
  40.                                 grid[lastY][lastX] = 0; // remove the last placed queen
  41.                                 j = lastX + 1;
  42.                                 i = lastY;
  43.                                 // System.out.println("backtracking!");
  44.                         }
  45.                 }
  46.         }
  47.         p(grid);
  48.      
  49.         // moves.printMoves();
  50.     }
  51.  
  52.     public static boolean isLegal(int y, int x, int[][] grid) {
  53.         if (isThreatenedVertically(y, x, grid)) return false;
  54.         if (isThreatenedHorizontally(y, x, grid)) return false;
  55.         if (isThreatenedDiagonally(y, x, grid)) return false;
  56.         return true;
  57.     }
  58.    
  59.     public static boolean isThreatenedVertically(int y, int x, int[][] grid) {
  60.         // check above
  61.         for(int i=0;i < y;i++) {
  62.                 if(grid[i][x] == 1) return true;
  63.         }
  64.         // check below
  65.         for(int i=y+1;i < grid.length;i++) {
  66.                 // if(grid[i][x] == 1) return true;
  67.         }
  68.         return false;
  69.     }
  70.    
  71.     public static boolean isThreatenedHorizontally(int y, int x, int[][] grid) {
  72.         // check left
  73.         for(int i=0;i < x;i++) {
  74.                 if(grid[y][i] == 1) return true;
  75.         }
  76.         // check right
  77.         for(int i=x+1;i < grid.length;i++) {
  78.                 if(grid[y][i] == 1) return true;
  79.         }
  80.         return false;
  81.     }
  82.    
  83.     public static boolean isThreatenedDiagonally(int y, int x, int[][] grid) {
  84.         // check above and left
  85.         int dx = x - 1;
  86.         int dy = y - 1;
  87.         while(dx >= 0 && dy >= 0) {
  88.                 if(grid[dy--][dx--] == 1) return true;
  89.         }
  90.         // check below and right
  91.         dx = x + 1;
  92.         dy = y + 1;
  93.         while(dx < grid.length && dy < grid.length) {
  94.                 if(grid[dy++][dx++] == 1) return true;
  95.         }
  96.         // check above and right
  97.         dx = x + 1;
  98.         dy = y - 1;
  99.         while(dx < grid.length && dy >= 0) {
  100.                 if(grid[dy--][dx++] == 1) return true;
  101.         }
  102.         // check below and left
  103.         dx = x - 1;
  104.         dy = y + 1;
  105.         while(dx >= 0 && dy < grid.length) {
  106.                 if(grid[dy++][dx--] == 1) return true;
  107.         }
  108.         return false;
  109.     }
  110.        
  111.     public static void p(int[][] grid) {
  112.         for(int i=0;i < grid.length;i++) {
  113.             for(int j=0;j < grid[0].length;j++) {
  114.                 System.out.print(grid[i][j]);
  115.             }
  116.             System.out.println();
  117.         }
  118.     }
  119.  
  120.     public static void place(int y, int x, int[][] grid) {
  121.         grid[y][x] = 1;
  122.     }
  123.  
  124.     // for debugging
  125.     public static void place(int y, int x, int[][] grid, int i) {
  126.             grid[y][x] = i;
  127.     }
  128. }