package JEG_SKAL_BLI_PRO;
import java.util.Scanner;
public class Queens {
public static void main(String[] a) {
Scanner in = new Scanner(System.in);
int[][] grid = new int[8][8];
boolean success;
for(int i=0;i < 8;i++) {
success = false; // initially no queen is placed
for(int j=0;j < 8;j++) {
/* THIS IS FOR DEBUGGING */
/* place(i,j,grid,4);
p(grid);
String s = in.nextLine();
place(i,j,grid,0); */
if(isLegal(i,j,grid)) {
place(i,j,grid);
success = true; // A queen is placed
break;
}
}
// check if a queen was placed. Do backtracking here!
if(! success) {
// System.out.println("failure");
}
}
p(grid);
}
public static boolean isLegal(int y, int x, int[][] grid) {
if (isThreatenedVertically(y, x, grid)) return false;
if (isThreatenedHorizontally(y, x, grid)) return false;
if (isThreatenedDiagonally(y, x, grid)) return false;
return true;
}
public static boolean isThreatenedVertically(int y, int x, int[][] grid) {
// check above
for(int i=0;i < y;i++) {
if(grid[i][x] == 1) return true;
}
// check below
for(int i=y+1;i < grid.length;i++) {
// if(grid[i][x] == 1) return true;
}
return false;
}
public static boolean isThreatenedHorizontally(int y, int x, int[][] grid) {
// check left
for(int i=0;i < x;i++) {
if(grid[y][i] == 1) return true;
}
// check right
for(int i=x+1;i < grid.length;i++) {
if(grid[y][i] == 1) return true;
}
return false;
}
public static boolean isThreatenedDiagonally(int y, int x, int[][] grid) {
// check above and left
int dx = x - 1;
int dy = y - 1;
while(dx >= 0 && dy >= 0) {
if(grid[dy--][dx--] == 1) return true;
}
// check below and right
dx = x + 1;
dy = y + 1;
while(dx < grid.length && dy < grid.length) {
if(grid[dy++][dx++] == 1) return true;
}
// check above and right
dx = x + 1;
dy = y - 1;
while(dx < grid.length && dy >= 0) {
if(grid[dy--][dx++] == 1) return true;
}
// check below and left
dx = x - 1;
dy = y + 1;
while(dx >= 0 && dy < grid.length) {
if(grid[dy++][dx--] == 1) return true;
}
return false;
}
public static void p(int[][] grid) {
for(int i=0;i < grid.length;i++) {
for(int j=0;j < grid[0].length;j++) {
System.out.print(grid[i][j]);
}
System.out.println();
}
}
public static void place(int y, int x, int[][] grid) {
grid[y][x] = 1;
}
// for debugging
public static void place(int y, int x, int[][] grid, int i) {
grid[y][x] = i;
}
}