Skip to content

Instantly share code, notes, and snippets.

@alecnunn

alecnunn/ChessPuzzle.java

Created November 22, 2015 01:43
Show Gist options
  • Save alecnunn/ea01182e80ecade16d90 to your computer and use it in GitHub Desktop.
Save alecnunn/ea01182e80ecade16d90 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
ChessPuzzle.java
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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment