import java.util.Arrays;
public class lily{
    private static int nextRow, nextCol;
    private static int height = 20;
    private static int width = 3;
    private static int numused = 0;
    private static int[][] board = new int[height][width];
    private static final int numOfPieces = 12;
    private static final boolean[] used = new boolean[numOfPieces+1];//we need 13 because we're not using the index 0 one. we will be using 1-12
    private  static final int[][] pieces = {
            { 1, 0,1,0,2,0,3,0,4 },  // Describes piece I in its horizontal orientation.
            { 1, 1,0,2,0,3,0,4,0 },  // Describes piece I in its vertical orientation.
            { 2, 1,-1,1,0,1,1,2,0 }, // Describes piece X in its only orientation.
            { 3, 0,1,1,0,2,-1,2,0 },
            { 3, 1,0,1,1,1,2,2,2 },
            { 3, 0,1,1,1,2,1,2,2 },
            { 3, 1,-2,1,-1,1,0,2,-2 },
            { 4, 1,0,2,0,2,1,2,2 },
            { 4, 0,1,0,2,1,0,2,0 },
            { 4, 1,0,2,-2,2,-1,2,0 },
            { 4, 0,1,0,2,1,2,2,2 },
            { 5, 0,1,0,2,1,1,2,1 },
            { 5, 1,-2,1,-1,1,0,2,0 },
            { 5, 1,0,2,-1,2,0,2,1 },
            { 5, 1,0,1,1,1,2,2,0 },
            { 6, 1,0,1,1,2,1,2,2 },
            { 6, 1,-1,1,0,2,-2,2,-1 },
            { 6, 0,1,1,1,1,2,2,2 },
            { 6, 0,1,1,-1,1,0,2,-1 },
            { 7, 0,1,0,2,1,0,1,2 },
            { 7, 0,1,1,1,2,0,2,1 },
            { 7, 0,2,1,0,1,1,1,2 },
            { 7, 0,1,1,0,2,0,2,1 },
            { 8, 1,0,1,1,1,2,1,3 },
            { 8, 1,0,2,0,3,-1,3,0 },
            { 8, 0,1,0,2,0,3,1,3 },
            { 8, 0,1,1,0,2,0,3,0 },
            { 8, 0,1,1,1,2,1,3,1 },
            { 8, 0,1,0,2,0,3,1,0 },
            { 8, 1,0,2,0,3,0,3,1 },
            { 8, 1,-3,1,-2,1,-1,1,0 },
            { 9, 0,1,1,-2,1,-1,1,0 },
            { 9, 1,0,1,1,2,1,3,1 },
            { 9, 0,1,0,2,1,-1,1,0 },
            { 9, 1,0,2,0,2,1,3,1 },
            { 9, 0,1,1,1,1,2,1,3 },
            { 9, 1,0,2,-1,2,0,3,-1 },
            { 9, 0,1,0,2,1,2,1,3 },
            { 9, 1,-1,1,0,2,-1,3,-1 },
            { 10, 1,-2,1,-1,1,0,1,1 },
            { 10, 1,-1,1,0,2,0,3,0 },
            { 10, 0,1,0,2,0,3,1,1 },
            { 10, 1,0,2,0,2,1,3,0 },
            { 10, 0,1,0,2,0,3,1,2 },
            { 10, 1,0,1,1,2,0,3,0 },
            { 10, 1,-1,1,0,1,1,1,2 },
            { 10, 1,0,2,-1,2,0,3,0 },
            { 11, 1,-1,1,0,1,1,2,1 },
            { 11, 0,1,1,-1,1,0,2,0 },
            { 11, 1,0,1,1,1,2,2,1 },
            { 11, 1,0,1,1,2,-1,2,0 },
            { 11, 1,-2,1,-1,1,0,2,-1 },
            { 11, 0,1,1,1,1,2,2,1 },
            { 11, 1,-1,1,0,1,1,2,-1 },
            { 11, 1,-1,1,0,2,0,2,1 },
            { 12, 0,1,1,0,1,1,2,1 },
            { 12, 0,1,0,2,1,0,1,1 },
            { 12, 1,0,1,1,2,0,2,1 },
            { 12, 0,1,1,-1,1,0,1,1 },
            { 12, 0,1,1,0,1,1,1,2 },
            { 12, 1,-1,1,0,2,-1,2,0 },
            { 12, 0,1,0,2,1,1,1,2 },
            { 12, 0,1,1,0,1,1,2,0 }
    };
    public static boolean putPiece(int p, int row, int col){

        for (int i = 1; i < 8; i += 2){//first check if all the coordinates are on the board to prevent ArraysOutOfBounds
            //if it's on board we can then check the values
            if((row + pieces[p][i])>=height || (col+pieces[p][i+1])>=width || col+pieces[p][i+1] < 0 || row+pieces[p][i] < 0)
                return false;
            if (board[row + pieces[p][i]][col+pieces[p][i+1]] != 0) {// one of the block needed is filled already
                return false;
            }
        }
        //now place the piece to the board
        board[row][col] = pieces[p][0];//change the value of the first block

        for (int i = 1; i < 8; i += 2){
            board[row + pieces[p][i]][col+pieces[p][i+1]] = pieces[p][0];  //we assign the piece value to the 4 other empty blocks
        }
        return true;

    }
    public static void removePiece(int p, int row, int col) {
        for (int i = 1; i < 8; i += 2){
            board[row][col] = 0;
            board[row + pieces[p][i]][col+pieces[p][i+1]] = 0;
        }
    }
    public static void printBoard(){
        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){//convert the numbers to letters
                if(board[i][j]==1)System.out.print("I");
                if(board[i][j]==2)System.out.print("X");
                if(board[i][j]==3)System.out.print("Z");
                if(board[i][j]==4)System.out.print("V");
                if(board[i][j]==5)System.out.print("T");
                if(board[i][j]==6)System.out.print("W");
                if(board[i][j]==7)System.out.print("U");
                if(board[i][j]==8)System.out.print("L");
                if(board[i][j]==9)System.out.print("N");
                if(board[i][j]==10)System.out.print("Y");
                if(board[i][j]==11)System.out.print("F");
                if(board[i][j]==12)System.out.print("P");
                if(board[i][j]==0)System.out.print(0);

                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public static void solve(int row, int col) {   // recursive procedure that tries to solve the puzzle

        for (int p=0; p<63; p++){

            if ((used[pieces[p][0]] == false) && putPiece(p, row, col)){  // try piece p
                // a piece has been placed on the board.

                used[pieces[p][0]] = true;
                numused++;

                if (numused == numOfPieces) {  // puzzle is solved if used = pieces
                    System.out.println("Solution found:");
                    printBoard();
                    System.out.println(Arrays.toString(used));
                    System.exit(0);
                }
                else {//find the next empty block to fill
                    for(int i=height-1; i>=0; i--){
                        for(int j=width-1; j>=0; j--){
                            if (board[i][j]==0){
                                nextRow = i;
                                nextCol = j;
                            }
                        }
                    }
                    solve(nextRow, nextCol);  // try to complete the solution
                }
                removePiece(p, row, col);  // backtrack
                numused--;
                used[pieces[p][0]] = false;
            }
        }
    }



    public static void main(String[] args){

        solve(0,0);
    }
}