Advertisement
Guest User

Untitled

a guest
Mar 26th, 2010
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.19 KB | None | 0 0
  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.         for(int i=0;i < 8;i++) {
  13.  
  14.                 success = false; // initially no queen is placed
  15.                
  16.                 for(int j=0;j < 8;j++) {
  17.  
  18.                     /* THIS IS FOR DEBUGGING */
  19.                     /*   place(i,j,grid,4);
  20.                     p(grid);
  21.                     String s = in.nextLine();
  22.                     place(i,j,grid,0);   */
  23.  
  24.                     if(isLegal(i,j,grid)) {
  25.                         place(i,j,grid);
  26.                         success = true; // A queen is placed                    
  27.                         break;
  28.                     }
  29.                 }
  30.                 // check if a queen was placed. Do backtracking here!
  31.                 if(! success) {
  32.                     // System.out.println("failure");
  33.                 }
  34.         }
  35.         p(grid);
  36.     }
  37.  
  38.     public static boolean isLegal(int y, int x, int[][] grid) {
  39.         if (isThreatenedVertically(y, x, grid)) return false;
  40.         if (isThreatenedHorizontally(y, x, grid)) return false;
  41.         if (isThreatenedDiagonally(y, x, grid)) return false;
  42.         return true;
  43.     }
  44.    
  45.     public static boolean isThreatenedVertically(int y, int x, int[][] grid) {
  46.         // check above
  47.         for(int i=0;i < y;i++) {
  48.             if(grid[i][x] == 1) return true;
  49.         }
  50.         // check below
  51.         for(int i=y+1;i < grid.length;i++) {
  52.             // if(grid[i][x] == 1) return true;
  53.         }
  54.         return false;
  55.     }
  56.    
  57.     public static boolean isThreatenedHorizontally(int y, int x, int[][] grid) {
  58.         // check left
  59.         for(int i=0;i < x;i++) {
  60.             if(grid[y][i] == 1) return true;
  61.         }
  62.         // check right
  63.         for(int i=x+1;i < grid.length;i++) {
  64.             if(grid[y][i] == 1) return true;
  65.         }
  66.         return false;
  67.     }
  68.    
  69.     public static boolean isThreatenedDiagonally(int y, int x, int[][] grid) {
  70.         // check above and left
  71.         int dx = x - 1;
  72.         int dy = y - 1;
  73.         while(dx >= 0 && dy >= 0) {
  74.             if(grid[dy--][dx--] == 1) return true;
  75.         }
  76.         // check below and right
  77.         dx = x + 1;
  78.         dy = y + 1;
  79.         while(dx < grid.length && dy < grid.length) {
  80.             if(grid[dy++][dx++] == 1) return true;
  81.         }
  82.         // check above and right
  83.         dx = x + 1;
  84.         dy = y - 1;
  85.         while(dx < grid.length && dy >= 0) {
  86.             if(grid[dy--][dx++] == 1) return true;
  87.         }
  88.         // check below and left
  89.         dx = x - 1;
  90.         dy = y + 1;
  91.         while(dx >= 0 && dy < grid.length) {
  92.             if(grid[dy++][dx--] == 1) return true;
  93.         }
  94.         return false;
  95.     }
  96.        
  97.     public static void p(int[][] grid) {
  98.         for(int i=0;i < grid.length;i++) {
  99.             for(int j=0;j < grid[0].length;j++) {
  100.                 System.out.print(grid[i][j]);
  101.             }
  102.             System.out.println();
  103.         }
  104.     }
  105.  
  106.     public static void place(int y, int x, int[][] grid) {
  107.         grid[y][x] = 1;
  108.     }
  109.  
  110.     // for debugging
  111.     public static void place(int y, int x, int[][] grid, int i) {
  112.             grid[y][x] = i;
  113.     }
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement