API tools faq
paste
Advertisement
Guest User

Chess Puzzle: can black king get out of check?

a guest
Nov 21st, 2015
295
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 8.49 KB | None | 0 0
raw download clone embed print report
  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
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!