首页 > 代码库 > HW6.22

HW6.22

技术分享

 

  1 import java.util.Arrays;  2   3 public class Solution  4 {  5     public static void main(String[] args)  6     {  7         int[][] chessboard = new int[8][8];  8         int[][] answerSave = new int[92][8];  9         int[] oneAnswer = new int[8]; 10  11         while(true) 12         { 13             putQueens(chessboard); 14  15             if(judgeCorrect(chessboard) == true) 16             { 17                 oneAnswer = convert(chessboard); 18                 if(!contain(answerSave, oneAnswer)) 19                 { 20                     drawChessboard(chessboard); 21                     putIn(answerSave, oneAnswer); 22                     if(isFull(answerSave)) 23                         break; 24                 } 25                 else 26                     clearChessboard(chessboard); 27             } 28             else 29                 clearChessboard(chessboard); 30         }     31     } 32  33  34     //put 8 queens on the chessboard randomly 35     public static void putQueens(int[][] array) 36     { 37         int position; 38      39         for(int i = 0; i < 8; i++) 40         { 41             position = (int)(Math.random() * 8); 42             array[i][position] = 1; 43         } 44     } 45  46     //clear the chessboard 47     public static void clearChessboard(int[][] array) 48     { 49         for(int i = 0; i < 8; i++) 50             for(int j = 0; j < 8; j++) 51                 array[i][j] = 0; 52     } 53  54     //judge if there is only one chess in a row 55     public static boolean judgeRow(int[][] array, int x, int y) 56     { 57         for(int i = y - 1; i >= 0; i--) 58             if(array[x][i] == 1) 59                 return false; 60         for(int i = y + 1; i < 8; i++) 61             if(array[x][i] == 1) 62                 return false; 63         return true; 64     } 65  66     //judge if there is only one chess in a column 67     public static boolean judgeColumn(int[][] array, int x, int y) 68     { 69         for(int i = x - 1; i >= 0; i--) 70             if(array[i][y] == 1) 71                 return false; 72         for(int i = x + 1; i < 8; i++) 73             if(array[i][y] == 1) 74                 return false; 75         return true; 76     } 77  78     //judge if there is only one chess in the lean from left-top to right-bottom 79     public static boolean judgeLeanTopToBottom(int[][] array, int x, int y) 80     { 81         for(int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) 82             if(array[i][j] == 1) 83                 return false; 84         for(int i = x + 1, j = y + 1; i < 8 && j < 8; i++, j++) 85             if(array[i][j] == 1) 86                 return false; 87         return true; 88     } 89  90     //judge if there is only one chess in the lean from left-bottom to right-top 91     public static boolean judgeLeanBottomToTop(int[][] array, int x, int y) 92     { 93         for(int i = x + 1, j = y - 1; i < 8 && j >= 0; i++, j--) 94             if(array[i][j] == 1) 95                 return false; 96         for(int i = x - 1, j = y + 1; i >= 0 && j < 8; i--, j++) 97             if(array[i][j] == 1) 98                 return false; 99         return true;100     }101 102     //judge if all the queens are put correctly103     public static boolean judgeCorrect(int[][] array)104     {105         int[] putX = new int[8];106         int[] putY = new int[8];107 108         for(int i = 0; i < 8; i++)109             for(int j = 0; j < 8; j++)110                 if(array[i][j] == 1)111                 {112                     putX[i] = i;113                     putY[i] = j;114                     break;115                 }116 117         for(int i = 0; i < 8; i++)118         {119             if(!(judgeRow(array, putX[i], putY[i]) && judgeColumn(array, putX[i], putY[i]) 120                 && judgeLeanTopToBottom(array, putX[i], putY[i]) && judgeLeanBottomToTop(array, putX[i], putY[i])))121                 return false;122         }123         return true;124     }125 126     //convert the 2D chessboard in a 1D array127     public static int[] convert(int[][] array)128     {129         int[] oneDQueen = new int[8];130         for(int i = 0; i < 8; i++)131             for(int j = 0; j < 8; j++)132             {133                 if(array[i][j] == 1)134                     oneDQueen[i] = j;135             }136         return oneDQueen;137     }138 139     //judge if the answer has been found140     public static boolean contain(int[][] largeArray, int[] littleArray)141     {142         for(int[] array: largeArray)143             if(Arrays.equals(array, littleArray))144                 return true;145         return false;146     }147 148     //put the answer in the answer-save array149     public static void putIn(int[][] largeArray, int[] littleArray)150     {151         int signI = 0;152         for(int i = 0; i < 92; i++)153             for(int j = 0; j < 7; j++)154                 if(largeArray[i][j] == 0 && largeArray[i][j + 1] == 0)155                 {156                     signI = i;157                     putIn(largeArray, littleArray, signI);158                     return;159                 }160     } 161 162     public static void putIn(int[][] largeArray, int[] littleArray, int sign)163     {164         for(int i = 0; i < 8; i++)165             largeArray[sign][i] = littleArray[i];166     }167 168     //judge if the array is full169     public static boolean isFull(int[][] largeArray)170     {171         for(int j = 0; j < 8; j++)172             if(largeArray[91][j] != 0)173                 return true;174         return false;175     }176 177     public static void drawChessboard(int[][] array)178     {179         for(int i = 0; i < 8; i++)180         {181             for(int j = 0; j < 8; j++)182             {183                 if(array[i][j] == 1)184                     System.out.print("Q");185                 else186                     System.out.print("-");187             }188             System.out.println();189         }190     }191 }

 

HW6.22