Advertisement
kuathadianto

Eight Queens Puzzle

Nov 16th, 2016
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.78 KB | None | 0 0
  1. package eightQueensPuzzle;
  2.  
  3. public class EightQueensPuzzle {
  4.  
  5.     private boolean isTrue = true;
  6.    
  7.     public boolean result() {
  8.         return isTrue;
  9.     }
  10.    
  11.     public EightQueensPuzzle(int board[][]) {
  12.         for(int row = 0; row < board.length; row++) {
  13.             if(!isTrue) { // don't continue, if it's known invalid
  14.                 break;
  15.             }
  16.             for(int col = 0; col < board.length; col++) {
  17.                 if(board[row][col] == 1) {
  18.                     if(!checkValidity(board, row, col)) {
  19.                         isTrue = false;
  20.                         break; // don't continue, if it's known invalid
  21.                     }
  22.                 }
  23.             }
  24.         }
  25.     }
  26.    
  27.     private boolean checkValidity(int board[][], int row, int col) {
  28.         // horizontal left
  29.         for(int colTemp = col-1; colTemp >= 0; colTemp--) {
  30.             if(board[row][colTemp] == 1) {
  31.                 return false;
  32.             }
  33.         }
  34.        
  35.         // horizontal right
  36.         for(int colTemp = col+1; colTemp < board.length; colTemp++) {
  37.             if(board[row][colTemp] == 1) {
  38.                 return false;
  39.             }
  40.         }
  41.        
  42.         // vertical top
  43.         for(int rowTemp = row-1; rowTemp >= 0; rowTemp--) {
  44.             if(board[rowTemp][col] == 1) {
  45.                 return false;
  46.             }
  47.         }
  48.        
  49.         // vertical bottom
  50.         for(int rowTemp = row+1; rowTemp < board.length; rowTemp++) {
  51.             if(board[rowTemp][col] == 1) {
  52.                 return false;
  53.             }
  54.         }
  55.        
  56.         // diagonal left top
  57.         for(int rowTemp = row-1, colTemp = col-1;
  58.                 rowTemp >= 0 && colTemp >= 0;
  59.                 rowTemp--, colTemp--) {
  60.             if(board[rowTemp][colTemp] == 1) {
  61.                 return false;
  62.             }
  63.         }
  64.        
  65.         // diagonal right top
  66.         for(int rowTemp = row-1, colTemp = col+1;
  67.                 rowTemp >= 0 && colTemp < board.length;
  68.                 rowTemp--, colTemp++) {
  69.             if(board[rowTemp][colTemp] == 1) {
  70.                 return false;
  71.             }
  72.         }
  73.        
  74.         // diagonal left bottom
  75.         for(int rowTemp = row+1, colTemp = col-1;
  76.                 rowTemp < board.length && colTemp >= 0;
  77.                 rowTemp++, colTemp--) {
  78.             if(board[rowTemp][colTemp] == 1) {
  79.                 return false;
  80.             }
  81.         }
  82.        
  83.         // diagonal right bottom
  84.         for(int rowTemp = row+1, colTemp = col+1;
  85.                 rowTemp < board.length && colTemp < board.length;
  86.                 rowTemp++, colTemp++) {
  87.             if(board[rowTemp][colTemp] == 1) {
  88.                 return false;
  89.             }
  90.         }
  91.        
  92.         return true;
  93.     }
  94.    
  95.     public static void main(String[] args) {
  96.         int b1[][] = {{0,0,1,0,0,0,0,0},
  97.                       {0,0,0,0,1,0,0,0},
  98.                       {0,1,0,0,0,0,0,0},
  99.                       {0,0,0,0,0,0,0,1},
  100.                       {1,0,0,0,0,0,0,0},
  101.                       {0,0,0,0,0,0,1,0},
  102.                       {0,0,0,1,0,0,0,0},
  103.                       {0,0,0,0,0,1,0,0}
  104.         };
  105.        
  106.         int b2[][] = {{0,1,0,0},
  107.                       {0,0,0,1},
  108.                       {1,0,0,0},
  109.                       {0,1,0,0}
  110.         };
  111.        
  112.         int b3[][] = {{0,1,0,0},
  113.                       {0,0,0,1},
  114.                       {1,0,0,0},
  115.                       {0,0,1,0}
  116.         };
  117.        
  118.         System.out.println(new EightQueensPuzzle(b1).result()); // should be true
  119.         System.out.println(new EightQueensPuzzle(b2).result()); // should be false
  120.         System.out.println(new EightQueensPuzzle(b3).result()); // should be true
  121.     }
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement