Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement