Advertisement
Guest User

Chess Puzzle: can black king get out of check?

a guest
Nov 21st, 2015
293
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 8.49 KB | None | 0 0
  1. import java.util.Arrays;
  2. import java.util.ArrayList;
  3. enum ChessPiece{
  4.     K(new int[][]{{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}}),
  5.     N(new int[][]{{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}}),
  6.     R(new int[][]{{-1,0},{0,1},{1,0},{0,-1}}),
  7.     Q(new int[][]{{-1,0},{0,1},{1,0},{0,-1},{-1,-1},{-1,1},{1,1},{1,-1}}),
  8.     B(new int[][]{{-1,-1},{-1,1},{1,1},{1,-1}}),
  9.     P(new int[][]{{-1,-1},{-1,+1}});
  10.  
  11.     private int[][] moves;
  12.  
  13.     ChessPiece(int[][] moves){
  14.         this.moves=moves;
  15.     }
  16.     public int[][] getMoves(){
  17.         int [][] a=new int[this.moves.length][2];
  18.         for(int i=0;i<a.length;i++)
  19.             a[i]=Arrays.copyOf(this.moves[i],this.moves[i].length);
  20.         return a;
  21.     }
  22. }
  23. class ChessPuzzle{
  24.     /*EMPTY=not occupied,INVALID=not safe for king to move in*/
  25.     private final static char EMPTY='\u002D';   //   -
  26.     private final static char INVALID='\u0023'; //   #
  27.     char[][] board;
  28.     char[][] elab;
  29.     int[] blackKing;
  30.     ChessPuzzle(String t){
  31.         board=new char[8][8];
  32.         elab=new char[8][8];
  33.         blackKing=new int[2];
  34.         Arrays.fill(blackKing,-1);
  35.         readFromFen(t);
  36.     }
  37.     private ChessPuzzle(char[][] t){
  38.         board=t;
  39.         blackKing=new int[2];
  40.         elab=new char[8][8];
  41.         outer:
  42.         for(int i=0;i<8;i++)
  43.             for(int j=0;j<8;j++)
  44.                 if(board[i][j]=='k'){
  45.                     blackKing[0]=i;
  46.                     blackKing[1]=j;
  47.                     break outer;
  48.                 }
  49.     }
  50.     /*Prints on screen the current puzzle*/
  51.     public void printBoard(){
  52.         for(char[] a:board)
  53.             System.out.println(Arrays.toString(a));
  54.     }
  55.     /*Reads from a string in FEN format them stores it in elab and board*/
  56.     private void readFromFen(String t){
  57.         String[] lines=t.split("/");
  58.         for(int i=0;i<8;i++){
  59.             Arrays.fill(board[i],EMPTY);
  60.             Arrays.fill(elab[i],EMPTY);
  61.         }
  62.         for(int i=0;i<8;i++){
  63.             if(lines[i].equals("8"))
  64.                 continue;
  65.             else if(lines[i].matches("[A-Za-z]{8}+")){
  66.                 board[i]=lines[i].toCharArray();
  67.                 elab[i]=lines[i].toCharArray();
  68.             }
  69.             else{
  70.                 int a=0;
  71.                 for(int j=0;j<lines[i].length();j++){
  72.                     if(lines[i].substring(j,j+1).matches("[1-7]"))
  73.                         a+=Integer.parseInt(lines[i].substring(j,j+1));
  74.                     else{
  75.                         board[i][a]=lines[i].charAt(j);
  76.                         elab[i][a]=lines[i].charAt(j);
  77.                         a++;
  78.                     }
  79.                 }
  80.             }
  81.         }
  82.     outer:
  83.     for(int i=0;i<8;i++)
  84.         for(int j=0;j<8;j++)
  85.             if(board[i][j]=='k'){
  86.                 blackKing[0]=i;
  87.                 blackKing[1]=j;
  88.                 break outer;
  89.             }
  90.     }
  91.     /*Methods used to figure out possible escape routes for Black King*/
  92.     void solve(){
  93.         ArrayList<Integer> enemiesInRange=new ArrayList<>();
  94.         if(isBlackKingInCheck()){
  95.             int row=-1,col=-1;
  96.             int[][] a=ChessPiece.K.getMoves();
  97.             buidElab();
  98.             for(char[] c:elab)
  99.                 System.out.println(Arrays.toString(c));
  100.            
  101.             for(int[] c:a){
  102.                 row=blackKing[0]+c[0];
  103.                 col=blackKing[1]+c[1];
  104.                 if(row<0||row>7||col<0||col>7)
  105.                     continue;
  106.                 else if(elab[row][col]==EMPTY){
  107.                     System.out.println("Solution found new king pos: "+((7-row)+1)+" "+(char)(65*(col+1)));
  108.                     return;
  109.                 }
  110.                 else if(elab[row][col]>64&&elab[row][col]<91){
  111.                     enemiesInRange.add(row);
  112.                     enemiesInRange.add(col);
  113.                 }
  114.             }
  115.             if(enemiesInRange.size()==0){
  116.                 System.out.println("Black king cannot move to get out of check");return;
  117.             }
  118.             while(enemiesInRange.size()>0){
  119.                 char[][] b=new char[8][8];
  120.                 ChessPuzzle n;
  121.                 for(int i=0;i<board.length;i++)
  122.                     b[i]=Arrays.copyOf(board[i],board.length);
  123.                 b[blackKing[0]][blackKing[1]]=EMPTY;
  124.                 b[enemiesInRange.remove(0)][enemiesInRange.remove(0)]='k';
  125.                 n=new ChessPuzzle(b);
  126.                 if(!n.isBlackKingInCheck()){
  127.                     System.out.println(
  128.                     new StringBuilder("Solution found, new king pos: ")
  129.                     .append(7-n.blackKing[0]+1).append((char)(65+(n.blackKing[1]))));
  130.                     n.printBoard();
  131.                     return;
  132.                 }
  133.             }
  134.         }
  135.         else{
  136.             System.out.println("Black King not in check");
  137.             for(char[] c:board)
  138.                 System.out.println(Arrays.toString(c));
  139.         }
  140.     }
  141.     /*Modify the array elab highlighting invalid moves for k*/
  142.     private void buidElab(){
  143.         for(int i=0;i<8;i++)
  144.             for(int j=0;j<8;j++)
  145.                 switch(elab[i][j]){
  146.                     case 'K':
  147.                         CalcDangerZones(i,j,ChessPiece.K);
  148.                         break;
  149.                     case 'Q':
  150.                         recursiveCalcDangerZones(-1,i,j,ChessPiece.Q);
  151.                         break;
  152.                     case 'N':
  153.                         CalcDangerZones(i,j,ChessPiece.N);
  154.                         break;
  155.                     case 'B':
  156.                         recursiveCalcDangerZones(-1,i,j,ChessPiece.B);
  157.                         break;
  158.                     case 'P':
  159.                         CalcDangerZones(i,j,ChessPiece.P);
  160.                         break;
  161.                     case 'R':
  162.                         recursiveCalcDangerZones(-1,i,j,ChessPiece.R);
  163.                         break;
  164.                 }
  165.     }
  166.     /*MArks invalid zones for black king,used for K P N*/
  167.     private void CalcDangerZones(int pieceRow,int pieceCol,ChessPiece cP){
  168.         int[][] a=cP.getMoves();
  169.         int newRow=-1,newCol=-1;
  170.         for(int i=0;i<a.length;i++){
  171.             newRow=pieceRow+a[i][0];
  172.             newCol=pieceCol+a[i][1];
  173.            
  174.             if(newRow<0||newRow>7||newCol>7||newCol<0)
  175.                 continue;
  176.             else if(elab[newRow][newCol]==EMPTY)
  177.                 elab[newRow][newCol]=INVALID;
  178.         }
  179.     }
  180.     /*Recursive method called to mark invalid zones used for Q R B*/
  181.     private void recursiveCalcDangerZones(int index,int pieceRow,int pieceCol,ChessPiece cP){
  182.         /*first call*/
  183.         if(index<0){
  184.             int[][] a=cP.getMoves();
  185.             for(int i=0;i<a.length;i++)
  186.                 recursiveCalcDangerZones(i,pieceRow+a[i][0],pieceCol+a[i][1],cP);
  187.         }
  188.         /*return conditions*/
  189.         else if(pieceRow<0||pieceRow>7||pieceCol<0||pieceCol>7)
  190.             return;
  191.         else if(elab[pieceRow][pieceCol]>64&&elab[pieceRow][pieceCol]<123&&elab[pieceRow][pieceCol]!='k')
  192.             return;
  193.         /*recursive steps*/
  194.         else if(elab[pieceRow][pieceCol]==INVALID||elab[pieceRow][pieceCol]=='k'){
  195.             int[] b=cP.getMoves()[index];
  196.             recursiveCalcDangerZones(index,pieceRow+b[0],pieceCol+b[1],cP);
  197.         }
  198.        
  199.         else if(elab[pieceRow][pieceCol]==EMPTY) {
  200.             int[] b=cP.getMoves()[index];
  201.             elab[pieceRow][pieceCol]=INVALID;
  202.             recursiveCalcDangerZones(index,pieceRow+b[0],pieceCol+b[1],cP);
  203.         }
  204.     }
  205.     /*Boolean methods used to verify if black king is in check*/
  206.     private boolean isBlackKingInCheck(){
  207.         boolean p=isPawnCheckingBlackKing();
  208.         boolean b=isBishopCheckingBlackKing(false);
  209.         boolean r=isRookCheckingBlackKing(false);
  210.         boolean n=isKnightCheckingBlackKing();
  211.         boolean q=isBishopCheckingBlackKing(true)||isRookCheckingBlackKing(true);
  212.  
  213.         return p||b||r||n||q;
  214.     }
  215.     private boolean isPawnCheckingBlackKing(){
  216.         if(blackKing[0]==7)return false;
  217.         char case1=EMPTY,case2=EMPTY;
  218.         if(blackKing[1]<7)
  219.             case2=board[blackKing[0]+1][blackKing[1]+1];
  220.         if(blackKing[1]>0)
  221.             case1=board[blackKing[0]+1][blackKing[1]-1];
  222.         return case1=='P'||case2=='P';
  223.     }
  224.     private boolean isKnightCheckingBlackKing(){
  225.         int row,col;
  226.         int[][] a=ChessPiece.N.getMoves();
  227.         for(int[] c:a){
  228.             row=blackKing[0]+c[0];
  229.             col=blackKing[1]+c[1];
  230.             if(row<0||row>7||col>7||col<0)
  231.                 continue;
  232.             else if(board[row][col]=='N')
  233.                 return true;
  234.         }
  235.         return false;
  236.     }
  237.     private boolean isBishopCheckingBlackKing(boolean isQueen){
  238.         int d1_row,d1_col,d2_row,d2_col;
  239.         String diag1,diag2;
  240.         String piece=(isQueen)?"Q":"B";
  241.         String regex1=new StringBuilder(".*").append(piece).append("\\u002D*k.*").toString();
  242.         String regex2=new StringBuilder(".*k\\u002D*").append(piece).append(".*").toString();
  243.        
  244.         StringBuilder d1=new StringBuilder(),d2=new StringBuilder();
  245.         if(blackKing[0]>=blackKing[1]){
  246.             d1_row=Math.abs(blackKing[0]-blackKing[1]);
  247.             d1_col=0;
  248.             d2_row=Math.abs((7-blackKing[0])-(7-blackKing[1]));;
  249.             d2_col=7;
  250.         }
  251.         else{
  252.             d1_row=0;
  253.             d1_col=Math.abs(blackKing[0]-blackKing[1]);
  254.             d2_row=0;
  255.             d2_col=Math.abs((7-blackKing[0])-(7-blackKing[1]));
  256.         }
  257.  
  258.         while(d1_row<8&&d1_col<8){
  259.             d1.append(board[d1_row][d1_col]);
  260.             d1_row++;d1_col++;
  261.         }
  262.         while(d2_row<8&&d2_col>-1){
  263.             d2.append(board[d2_row][d2_col]);
  264.             d2_row++;d2_col--;
  265.         }
  266.         diag1=d1.toString();
  267.         diag2=d2.toString();
  268.  
  269.         return diag1.matches(regex1)||diag1.matches(regex2)||
  270.                diag2.matches(regex1)||diag2.matches(regex2);
  271.     }
  272.     private boolean isRookCheckingBlackKing(boolean isQueen){
  273.         String row=new String(board[blackKing[0]]);
  274.         String col;
  275.         String piece=(isQueen)?"Q":"R";
  276.         String regex1=new StringBuilder(".*").append(piece).append("\\u002D*k.*").toString();
  277.         String regex2=new StringBuilder(".*k\\u002D*").append(piece).append(".*").toString();
  278.         StringBuilder buff=new StringBuilder();
  279.         for(int j=0;j<8;j++)
  280.             buff.append(board[blackKing[0]][j]);
  281.         col=buff.toString();
  282.         return row.matches(regex1)||row.matches(regex2)||
  283.                col.matches(regex1)||col.matches(regex2);
  284.     }
  285.     /*MAIN*/
  286.     public static void main(String[] args){
  287.         ChessPuzzle a=new ChessPuzzle("1r3kR1/4P3/6NB/8/8/Q7/8/4KR2");
  288.         a.solve();
  289.     }
  290. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement