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();
}
}
}
