import java.util.Arrays; public class Solution { public static void main(String[] args) { int[][] chessboard = new int[8][8]; int[][] answerSave = new int[92][8]; int[] oneAnswer = new int[8]; while(true) { putQueens(chessboard); if(judgeCorrect(chessboard) == true) { oneAnswer = convert(chessboard); if(!contain(answerSave, oneAnswer)) { drawChessboard(chessboard); putIn(answerSave, oneAnswer); if(isFull(answerSave)) break; } else clearChessboard(chessboard); } else clearChessboard(chessboard); } } //put 8 queens on the chessboard randomly public static void putQueens(int[][] array) { int position; for(int i = 0; i < 8; i++) { position = (int)(Math.random() * 8); array[i][position] = 1; } } //clear the chessboard public static void clearChessboard(int[][] array) { for(int i = 0; i < 8; i++) for(int j = 0; j < 8; j++) array[i][j] = 0; } //judge if there is only one chess in a row public static boolean judgeRow(int[][] array, int x, int y) { for(int i = y - 1; i >= 0; i--) if(array[x][i] == 1) return false; for(int i = y + 1; i < 8; i++) if(array[x][i] == 1) return false; return true; } //judge if there is only one chess in a column public static boolean judgeColumn(int[][] array, int x, int y) { for(int i = x - 1; i >= 0; i--) if(array[i][y] == 1) return false; for(int i = x + 1; i < 8; i++) if(array[i][y] == 1) return false; return true; } //judge if there is only one chess in the lean from left-top to right-bottom public static boolean judgeLeanTopToBottom(int[][] array, int x, int y) { for(int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) if(array[i][j] == 1) return false; for(int i = x + 1, j = y + 1; i < 8 && j < 8; i++, j++) if(array[i][j] == 1) return false; return true; } //judge if there is only one chess in the lean from left-bottom to right-top public static boolean judgeLeanBottomToTop(int[][] array, int x, int y) { for(int i = x + 1, j = y - 1; i < 8 && j >= 0; i++, j--) if(array[i][j] == 1) return false; for(int i = x - 1, j = y + 1; i >= 0 && j < 8; i--, j++) if(array[i][j] == 1) return false; return true; } //judge if all the queens are put correctly public static boolean judgeCorrect(int[][] array) { int[] putX = new int[8]; int[] putY = new int[8]; for(int i = 0; i < 8; i++) for(int j = 0; j < 8; j++) if(array[i][j] == 1) { putX[i] = i; putY[i] = j; break; } for(int i = 0; i < 8; i++) { if(!(judgeRow(array, putX[i], putY[i]) && judgeColumn(array, putX[i], putY[i]) && judgeLeanTopToBottom(array, putX[i], putY[i]) && judgeLeanBottomToTop(array, putX[i], putY[i]))) return false; } return true; } //convert the 2D chessboard in a 1D array public static int[] convert(int[][] array) { int[] oneDQueen = new int[8]; for(int i = 0; i < 8; i++) for(int j = 0; j < 8; j++) { if(array[i][j] == 1) oneDQueen[i] = j; } return oneDQueen; } //judge if the answer has been found public static boolean contain(int[][] largeArray, int[] littleArray) { for(int[] array: largeArray) if(Arrays.equals(array, littleArray)) return true; return false; } //put the answer in the answer-save array public static void putIn(int[][] largeArray, int[] littleArray) { int signI = 0; for(int i = 0; i < 92; i++) for(int j = 0; j < 7; j++) if(largeArray[i][j] == 0 && largeArray[i][j + 1] == 0) { signI = i; putIn(largeArray, littleArray, signI); return; } } public static void putIn(int[][] largeArray, int[] littleArray, int sign) { for(int i = 0; i < 8; i++) largeArray[sign][i] = littleArray[i]; } //judge if the array is full public static boolean isFull(int[][] largeArray) { for(int j = 0; j < 8; j++) if(largeArray[91][j] != 0) return true; return false; } public static void drawChessboard(int[][] array) { for(int i = 0; i < 8; i++) { for(int j = 0; j < 8; j++) { if(array[i][j] == 1) System.out.print("Q"); else System.out.print("-"); } System.out.println(); } } }