import java.util.Arrays;
import java.util.ArrayList;
enum ChessPiece{
        K(new int[][]{{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}}),
        N(new int[][]{{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}}),
        R(new int[][]{{-1,0},{0,1},{1,0},{0,-1}}),
        Q(new int[][]{{-1,0},{0,1},{1,0},{0,-1},{-1,-1},{-1,1},{1,1},{1,-1}}),
        B(new int[][]{{-1,-1},{-1,1},{1,1},{1,-1}}),
        P(new int[][]{{-1,-1},{-1,+1}});
 
        private int[][] moves;
 
        ChessPiece(int[][] moves){
                this.moves=moves;
        }
        public int[][] getMoves(){
                int [][] a=new int[this.moves.length][2];
                for(int i=0;i<a.length;i++)
                        a[i]=Arrays.copyOf(this.moves[i],this.moves[i].length);
                return a;
        }
}
class ChessPuzzle{
        /*EMPTY=not occupied,INVALID=not safe for king to move in*/
        private final static char EMPTY='\u002D';       //   -
        private final static char INVALID='\u0023'; //   #
        char[][] board;
        char[][] elab;
        int[] blackKing;
        ChessPuzzle(String t){
                board=new char[8][8];
                elab=new char[8][8];
                blackKing=new int[2];
                Arrays.fill(blackKing,-1);
                readFromFen(t);
        }
        private ChessPuzzle(char[][] t){
                board=t;
                blackKing=new int[2];
                elab=new char[8][8];
                outer:
                for(int i=0;i<8;i++)
                        for(int j=0;j<8;j++)
                                if(board[i][j]=='k'){
                                        blackKing[0]=i;
                                        blackKing[1]=j;
                                        break outer;
                                }
        }
        /*Prints on screen the current puzzle*/
        public void printBoard(){
                for(char[] a:board)
                        System.out.println(Arrays.toString(a));
        }
        /*Reads from a string in FEN format them stores it in elab and board*/
        private void readFromFen(String t){
                String[] lines=t.split("/");
                for(int i=0;i<8;i++){
                        Arrays.fill(board[i],EMPTY);
                        Arrays.fill(elab[i],EMPTY);
                }
                for(int i=0;i<8;i++){
                        if(lines[i].equals("8"))
                                continue;
                        else if(lines[i].matches("[A-Za-z]{8}+")){
                                board[i]=lines[i].toCharArray();
                                elab[i]=lines[i].toCharArray();
                        }
                        else{
                                int a=0;
                                for(int j=0;j<lines[i].length();j++){
                                        if(lines[i].substring(j,j+1).matches("[1-7]"))
                                                a+=Integer.parseInt(lines[i].substring(j,j+1));
                                        else{
                                                board[i][a]=lines[i].charAt(j);
                                                elab[i][a]=lines[i].charAt(j);
                                                a++;
                                        }
                                }
                        }
                }
        outer:
        for(int i=0;i<8;i++)
                for(int j=0;j<8;j++)
                        if(board[i][j]=='k'){
                                blackKing[0]=i;
                                blackKing[1]=j;
                                break outer;
                        }
        }
        /*Methods used to figure out possible escape routes for Black King*/
        void solve(){
                ArrayList<Integer> enemiesInRange=new ArrayList<>();
                if(isBlackKingInCheck()){
                        int row=-1,col=-1;
                        int[][] a=ChessPiece.K.getMoves();
                        buidElab();
                        for(char[] c:elab)
                                System.out.println(Arrays.toString(c));
                       
                        for(int[] c:a){
                                row=blackKing[0]+c[0];
                                col=blackKing[1]+c[1];
                                if(row<0||row>7||col<0||col>7)
                                        continue;
                                else if(elab[row][col]==EMPTY){
                                        System.out.println("Solution found new king pos: "+((7-row)+1)+" "+(char)(65*(col+1)));
                                        return;
                                }
                                else if(elab[row][col]>64&&elab[row][col]<91){
                                        enemiesInRange.add(row);
                                        enemiesInRange.add(col);
                                }
                        }
                        if(enemiesInRange.size()==0){
                                System.out.println("Black king cannot move to get out of check");return;
                        }
                        while(enemiesInRange.size()>0){
                                char[][] b=new char[8][8];
                                ChessPuzzle n;
                                for(int i=0;i<board.length;i++)
                                        b[i]=Arrays.copyOf(board[i],board.length);
                                b[blackKing[0]][blackKing[1]]=EMPTY;
                                b[enemiesInRange.remove(0)][enemiesInRange.remove(0)]='k';
                                n=new ChessPuzzle(b);
                                if(!n.isBlackKingInCheck()){
                                        System.out.println(
                                        new StringBuilder("Solution found, new king pos: ")
                                        .append(7-n.blackKing[0]+1).append((char)(65+(n.blackKing[1]))));
                                        n.printBoard();
                                        return;
                                }
                        }
                }
                else{
                        System.out.println("Black King not in check");
                        for(char[] c:board)
                                System.out.println(Arrays.toString(c));
                }
        }
        /*Modify the array elab highlighting invalid moves for k*/
        private void buidElab(){
                for(int i=0;i<8;i++)
                        for(int j=0;j<8;j++)
                                switch(elab[i][j]){
                                        case 'K':
                                                CalcDangerZones(i,j,ChessPiece.K);
                                                break;
                                        case 'Q':
                                                recursiveCalcDangerZones(-1,i,j,ChessPiece.Q);
                                                break;
                                        case 'N':
                                                CalcDangerZones(i,j,ChessPiece.N);
                                                break;
                                        case 'B':
                                                recursiveCalcDangerZones(-1,i,j,ChessPiece.B);
                                                break;
                                        case 'P':
                                                CalcDangerZones(i,j,ChessPiece.P);
                                                break;
                                        case 'R':
                                                recursiveCalcDangerZones(-1,i,j,ChessPiece.R);
                                                break;
                                }
        }
        /*MArks invalid zones for black king,used for K P N*/
        private void CalcDangerZones(int pieceRow,int pieceCol,ChessPiece cP){
                int[][] a=cP.getMoves();
                int newRow=-1,newCol=-1;
                for(int i=0;i<a.length;i++){
                        newRow=pieceRow+a[i][0];
                        newCol=pieceCol+a[i][1];
                       
                        if(newRow<0||newRow>7||newCol>7||newCol<0)
                                continue;
                        else if(elab[newRow][newCol]==EMPTY)
                                elab[newRow][newCol]=INVALID;
                }
        }
        /*Recursive method called to mark invalid zones used for Q R B*/
        private void recursiveCalcDangerZones(int index,int pieceRow,int pieceCol,ChessPiece cP){
                /*first call*/
                if(index<0){
                        int[][] a=cP.getMoves();
                        for(int i=0;i<a.length;i++)
                                recursiveCalcDangerZones(i,pieceRow+a[i][0],pieceCol+a[i][1],cP);
                }
                /*return conditions*/
                else if(pieceRow<0||pieceRow>7||pieceCol<0||pieceCol>7)
                        return;
                else if(elab[pieceRow][pieceCol]>64&&elab[pieceRow][pieceCol]<123&&elab[pieceRow][pieceCol]!='k')
                        return;
                /*recursive steps*/
                else if(elab[pieceRow][pieceCol]==INVALID||elab[pieceRow][pieceCol]=='k'){
                        int[] b=cP.getMoves()[index];
                        recursiveCalcDangerZones(index,pieceRow+b[0],pieceCol+b[1],cP);
                }
               
                else if(elab[pieceRow][pieceCol]==EMPTY) {
                        int[] b=cP.getMoves()[index];
                        elab[pieceRow][pieceCol]=INVALID;
                        recursiveCalcDangerZones(index,pieceRow+b[0],pieceCol+b[1],cP);
                }
        }
        /*Boolean methods used to verify if black king is in check*/
        private boolean isBlackKingInCheck(){
                boolean p=isPawnCheckingBlackKing();
                boolean b=isBishopCheckingBlackKing(false);
                boolean r=isRookCheckingBlackKing(false);
                boolean n=isKnightCheckingBlackKing();
                boolean q=isBishopCheckingBlackKing(true)||isRookCheckingBlackKing(true);
 
                return p||b||r||n||q;
        }
        private boolean isPawnCheckingBlackKing(){
                if(blackKing[0]==7)return false;
                char case1=EMPTY,case2=EMPTY;
                if(blackKing[1]<7)
                        case2=board[blackKing[0]+1][blackKing[1]+1];
                if(blackKing[1]>0)
                        case1=board[blackKing[0]+1][blackKing[1]-1];
                return case1=='P'||case2=='P';
        }
        private boolean isKnightCheckingBlackKing(){
                int row,col;
                int[][] a=ChessPiece.N.getMoves();
                for(int[] c:a){
                        row=blackKing[0]+c[0];
                        col=blackKing[1]+c[1];
                        if(row<0||row>7||col>7||col<0)
                                continue;
                        else if(board[row][col]=='N')
                                return true;
                }
                return false;
        }
        private boolean isBishopCheckingBlackKing(boolean isQueen){
                int d1_row,d1_col,d2_row,d2_col;
                String diag1,diag2;
                String piece=(isQueen)?"Q":"B";
                String regex1=new StringBuilder(".*").append(piece).append("\\u002D*k.*").toString();
                String regex2=new StringBuilder(".*k\\u002D*").append(piece).append(".*").toString();
               
                StringBuilder d1=new StringBuilder(),d2=new StringBuilder();
                if(blackKing[0]>=blackKing[1]){
                        d1_row=Math.abs(blackKing[0]-blackKing[1]);
                        d1_col=0;
                        d2_row=Math.abs((7-blackKing[0])-(7-blackKing[1]));;
                        d2_col=7;
                }
                else{
                        d1_row=0;
                        d1_col=Math.abs(blackKing[0]-blackKing[1]);
                        d2_row=0;
                        d2_col=Math.abs((7-blackKing[0])-(7-blackKing[1]));
                }
 
                while(d1_row<8&&d1_col<8){
                        d1.append(board[d1_row][d1_col]);
                        d1_row++;d1_col++;
                }
                while(d2_row<8&&d2_col>-1){
                        d2.append(board[d2_row][d2_col]);
                        d2_row++;d2_col--;
                }
                diag1=d1.toString();
                diag2=d2.toString();
 
                return diag1.matches(regex1)||diag1.matches(regex2)||
                           diag2.matches(regex1)||diag2.matches(regex2);
        }
        private boolean isRookCheckingBlackKing(boolean isQueen){
                String row=new String(board[blackKing[0]]);
                String col;
                String piece=(isQueen)?"Q":"R";
                String regex1=new StringBuilder(".*").append(piece).append("\\u002D*k.*").toString();
                String regex2=new StringBuilder(".*k\\u002D*").append(piece).append(".*").toString();
                StringBuilder buff=new StringBuilder();
                for(int j=0;j<8;j++)
                        buff.append(board[blackKing[0]][j]);
                col=buff.toString();
                return row.matches(regex1)||row.matches(regex2)||
                           col.matches(regex1)||col.matches(regex2);
        }
        /*MAIN*/
        public static void main(String[] args){
                ChessPuzzle a=new ChessPuzzle("1r3kR1/4P3/6NB/8/8/Q7/8/4KR2");
                a.solve();
        }
}