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;

       Moves moves = new Moves();

       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
                        Integer[] move = {i ,j};  // autoboxing
                        moves.push(move); // push the move onto the stack
                        break;
                    }

	                // check if a queen was placed. Or if not enough queens have been placed
	                if( (! success && j == 7) || (i == 7 && j == 7 && moves.length() < 8)) {
	                	// System.out.println("failure");
	                	Integer[] lastMove = moves.pop();
	                	int lastY = lastMove[0];
	                	int lastX = lastMove[1];
	                	grid[lastY][lastX] = 0; // remove the last placed queen
	                	j = lastX + 1;
	                	i = lastY;
	                	// System.out.println("backtracking!");
	                }
                }
        }
        p(grid);

        // moves.printMoves();
    }

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