CareerCup

Unless I'm misunderstanding this problem, the algorithm part is way simpler than most of these answers are making it out to be. As long as the board is empty, bishops moves are trivial. Simply rotate the chessboard 45 degrees in your mind, so that the corners are oriented horizontally & vertically. Next, decompose the board into two subboards, one made up of white squares & the other of black ones, since a bishop can only move on one subset.

We now have two diamond-shaped boards, each containing 32 squares in the format (row length ordered top to bottom) 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, where our bishops move either side to side or up and down, just like rooks. The question is now equivalent to asking how a rook can move from one location to another in the fewest moves, which is simple - would you ever use Djikstra or any graph to move a rook? If not, you shouldn't use it to move a bishop, the problems are isomorphic under this transformation.

If the "rooks" are on different boards, there is no path. If they are on the same board, then if they are on the same row or column, it is a single move. If they are not, then there are 2 options: move up/down then left/right or vice versa.

This algorithm is very fast, but the direct translation into code is not particularly short, due to the transformations into and out of "bishop coordinates", and there are plenty of gotchas on the math. I'm not claiming this is the simplest solution to code, but it establishes that the answer is always either "impossible", 0, 1, or 2 moves; and gives you direct calculations for which the answer is, and what the moves are (if any).

If I were in an 45 min interview I would have used a Graph Representation of the problem. So, I would have created a Graph in which each Node correspond to a single square (x,y) and two nodes A,B are connected if a bishop can directly move from A to B (and viceversa),ie, they are in the immediate diagonal of one another. So, in a chess board, this Graph will have 32 nodes because the Bishop can only move in half of the chess board (all whites or all blacks).

So, suppose the chess board is 4x4. The graph will look like this:

(0,0)		(0,2)
    \		/   \
      \	   /     \
      (1,1)      (1,3)
	 /     \       /
    /		\     /
(2,0)        (2,2)
 			 /     \    
            /       \
         (3,1)     (1,3)

After I have constructed the Graph, I would just use Bread First Search on the initial position of the Bishop until I find the target position.

I think the big advantage of this solution is that it is quite easy to understand and that you can reuse the Graph for multiply queries of "find the shortest path from A to B". Another big advantage is that in case there are pieces blocking the way, it's as easy as eliminating the node where these pieces are. The BFS will continue to work.

The big disadvantage is, however, the memory usage.

Note: For further improvements on the solution, instead of using BFS, we can use A*, where the Heuristic(A,B) =euclidean distance (A,B) or norm(A-B)

Represent each square with a point (x,y) where both x and y integers. 0 <= x,y <=7. Possible moves of bishop can be represented as two lines y=x+c and y=-x +c. Similarly possible moves from destination can be represented as two lines. Find the intersection of lines. Check if solution point, say (a,b) is in acceptable limit or not. a,b both should be integers also and 0<= a,b <= 7

For an 8x8 board, you will always reach from source to target in maximum of 2 moves.
So we can determine whether a location is black or white in O(1).
A bishop in "Black" box will never be able to move to target lying in "White" box.

For move=1, this can be determined whether abs(x1-x2) == abs(y1-y2)
Rest all cases will always have move=2

find the difference b/w the horizontal co-ordinates (say h) n also for vertical coords (say v).
if (v==h) //a diagonal path to the target
moves=1;
path= diagonal

else //bishop will cover min(h.v) diagonally and the remaining in a straight line.
moves=2;
path=diagonal+ straight line to the target

Can we assume that there are no other pieces on the board that might be in the way of the bishop movement?

All the possible movement lines of the Bishops on the board can be described by 2 set of lines, namely:
y = x + c1
y = -x + c2

We have 2 points (x1, y1) i.e. start and (x2, y2) i.e. end

I've given a pseudocode, assuming there are no pieces which could block the shortest path.

// First ensure there is an actual bishop bath between the 2 points
// If the diff between the x coordinates is even, the diff between the
// y coordinates must also be even, or both should be odd.
// It cannot be a mix
bool xdiffeven = (| x1 - x2 | % 2 == 0)
bool ydiffeven = (| y1 - y2 | % 2 == 0)
if (xdiffeven != ydiffeven)
{
    return ERROR_MOVE_NOT_POSSIBLE
}
else if ((y1 - x1) == (y2 - x2) || (y1 + x1) == (y2 + x2))
{
    // We have a direct line connecting the 2 points.
    // We only need to figure if there are any other pieces which may be in this path
}
else
{
    // We can get from A(x1,y1) to B(x2,y2) using 2 possible paths, each in 2 moves
    // We determine the intermediate point next
    // The 2 points can be found at the intersection of the following pair of lines:
    // y = x + c1A and y = -x + c2B
    // y = -x + c2A and y = x + c1B

    // For y = x + c1A and y = -x + c2B
    x = ((y2 + x2) - (y1 - x1))/2
    y = (y2 + x2) - x

    // For y = -x + c2A and y = x + c1B
    x = ((y2 - x2) - (y1 + x1)) / 2
    y = x + (y1 + x1)
}

This logic could be extended to figure out a path around a piece which could block the path, but the problem then gets recursive to do the same for the sub-path which could again have pieces in the way.

This is not a difficult problem. Two simple observations can lead us to an optimal solution

1. For a given location (i,j) of bishop, the next possible moves will have locations (i+k, j+k) ,where k=1 or -1
2. if (srcI, srcJ) is the source location and (tgtI, tgtJ) is target location then AbsoluteValue(srcI-srcJ) and AbsoluteValue(tgtI-tgtJ) must both be even or both be odd to be considered as valid moves.
3. This leads us to a simple recursive solution where we can trace the path from the source to the target by incrementing or decrementing x and y coordinates values(and at the same time checking that we lie within the boudaries).

Follows is a complete implementation: The source and target locations can be given as:
1 1
8 8

import java.util.Scanner;

public class BishopMoves {

	public static void printMoves(int sourceI, int sourceJ, int targetI, int targetJ) {
		
		int tmpI, tmpJ;
		if (sourceI == targetI && sourceJ == targetJ) {
			System.out.println(targetI + " " + targetJ);
			return;			
		}
		
		if (targetI > sourceI) {
			tmpI = targetI - 1;
		} else if (targetI < sourceI){
			tmpI = targetI + 1;
		} else {
			if (targetI - 1 < 1) {
				tmpI = targetI + 1;
			} else {
				tmpI = targetI - 1;
			}
		}
		
		if (targetJ > sourceJ) {
			tmpJ = targetJ - 1;
		} else if (targetJ < sourceJ){
			tmpJ = targetJ + 1;
		}  else {
			if (targetJ - 1 < 1) {
				tmpJ = targetJ + 1;
			} else {
				tmpJ = targetJ - 1;
			}
		}
		
		printMoves(sourceI, sourceJ, tmpI, tmpJ);
		System.out.println(targetI + " " + targetJ);		
	}
	
	public static void main (String[] args) throws Exception {
		Scanner scanner = new Scanner(System.in);
		System.out.println("Input space delimited coordinates of the source location. Eg: 2 1");
		int sourceI = scanner.nextInt();
		int sourceJ = scanner.nextInt();
		System.out.println("Input space delimited coordinates of the target location. Eg: 5 4");
		int targetI = scanner.nextInt();
		int targetJ = scanner.nextInt();
		
		if (1 > sourceI || sourceI > 8) {
			throw new Exception("Range of the coordinates is between 1 and 8");
		}
		
		if (1 > sourceJ || sourceJ > 8) {
			throw new Exception("Range of the coordinates is between 1 and 8");
		}
		
		if (1 > targetI || targetI > 8) {
			throw new Exception("Range of the coordinates is between 1 and 8");
		}
		
		if (1 > targetJ || targetJ > 8) {
			throw new Exception("Range of the coordinates is between 1 and 8");
		}
		
		int sourceDiff = Math.abs(sourceI - sourceJ);
		int targetDiff = Math.abs(targetI - targetJ);
		
		if (Math.abs(sourceDiff - targetDiff)%2 != 0) {
			throw new Exception("Invalid source and target location coordinates");
		}
		
		System.out.println("The path from source to target is:");
		printMoves(sourceI, sourceJ, targetI, targetJ);
	}
}

I somehow feel that this should work but it is not working for all the inputs,howeever if you anyone has some corrections to make in this code than i WILL really appreciate.

#include <limits.h>
/* below is i and j target*/
#define T_I 0
#define T_J 4

#define TARGET(i, j) ((i==T_I && j== T_J)?1:0)

int min(int a, int b)
{
        return a>b?b:a;
}
int track[100][100]={0};

int foo(int i, int j)
{
        int value1, value2, value3, value4;
        value1=value2=value3=value4=0;
        if(i<0||j<0 ||i>7||j>7)
                return 99999;
        if(track[i][j]==1)
                return 99999;
        track[i][j]=1;
        if(TARGET(i, j)) {
                track[i][j]=0;
                return 1;
        }
        value1 = 1+ foo(i+1,j+1);
        value2 = 1+ foo(i-1,j-1);
        value3 = 1+ foo(i+1,j-1);
        value4 = 1+ foo(i-1, j+1);
        track[i][j]=0;
        return min(value1, min(value2, min(value3, value4)));
}

int main()
{
        /* starting point is 1,1*/
        printf("output %d\n", foo(1, 1));
}

I think the following works:

1- Start from the target cell
2- label all diagonal cells immediately around it as 1 (i.e. distance 1)
3- Now take all cells with distance 1 and label all diagonal cells immediately around them that are not yet labeled as 2.
4 - Continue until the entire board is labeled

5 - Now start with the starting cell.
6 - Pick a surrounding cell that has distance smaller than that of the starting cell.
7 - from that cell, again select one neighbor that has a smaller distance than the current cell.
8 - continue until you get to the target

Here is the code (that probably can be simplified by a bit):

class Point{
	int i;
	int j;
	
	public Point(int i, int j){
		this.i = i;
		this.j = j;
	}
}

public class Search {

	
	public static ArrayList<Point> calculateDistance(int[][] arr, int x, int y, int a, int b){
		
		for(int i=0; i<8; i++){
			for(int j=0; j<8; j++){
				arr[i][j] = -1;
			}
		}
		
		ArrayList<Point> points = new ArrayList<Point>();
		points.add(new Point(x, y));
		arr[x][y] = 0;
		int distance = 1;
		
		while(!points.isEmpty()){
			
			ArrayList<Point> temp = new ArrayList<Point>();
			
			for(Point p : points){
				if(p.i+1 < 8 && p.j+1 < 8 && arr[p.i+1][p.j+1] == -1){
					arr[p.i+1][p.j+1] = distance;
					temp.add(new Point(p.i+1, p.j+1));
				}
				if(p.i+1 < 8 && p.j-1 >=0 && arr[p.i+1][p.j-1] == -1){
					arr[p.i+1][p.j-1] = distance;
					temp.add(new Point(p.i+1, p.j-1));
				}
				if(p.i-1 >=0 && p.j-1 >=0 && arr[p.i-1][p.j-1] == -1){
					arr[p.i-1][p.j-1] = distance;
					temp.add(new Point(p.i-1, p.j-1));
				}
				if(p.i-1 >=0 && p.j+1 < 8 && arr[p.i-1][p.j+1] == -1){
					arr[p.i-1][p.j+1] = distance;
					temp.add(new Point(p.i-1, p.j+1));
				}
			}
			points = temp;
			distance ++;	
		}
		
		int currD = arr[a][b];
		ArrayList<Point> path = new ArrayList<Point>();
		
		while (a != x || b != y){			
			if(a+1 < 8 && b+1 <8 && arr[a+1][b+1] < currD){
				currD = arr[a+1][b+1];
				path.add(new Point(a+1, b+1));
				a +=1;
				b +=1;
			}
			else if(a+1 < 8 && b-1 >= 0 && arr[a+1][b-1] < currD){
				currD = arr[a+1][b-1];
				path.add(new Point(a+1, b-1));
				a +=1;
				b -=1;
			}
			else if(a-1 >= 0 && b-1 >= 0 && arr[a-1][b-1] < currD){
				currD = arr[a-1][b-1];
				path.add(new Point(a-1, b-1));
				a -=1;
				b -=1;
			}
			else if(a-1 >= 0 && b+1 < 8 && arr[a-1][b+1] < currD){
				currD = arr[a-1][b+1];
				path.add(new Point(a-1, b+1));
				a -=1;
				b +=1;
			}
		}
		return path;
	}
}

Would this be a worthy solution?

public class Bishop {
	public Bishop (int x, int y){
		this.x = x;
		this.y = y;
	}
	public boolean Move (int targetX, int targetY){
		int tmp1 = abs(this.x - this.y);
		int tmp 2 = abs(targetX - targetY);
		if (tmp1 % 2 != tmp2 % 2)
			return false;
		int moveX = CheckMovement(this.x, targetX);
		if (moveX == -1)
			return false;
		this.x = moveX;
		int moveY = CheckMovement(this.y, targetY);
		if (moveY == -1)
			return false;
		this.y = moveY;
		return true;
	}
	private int CheckMovement(int origin, int target){
		if (origin == target)
			return -1;
		else if (origin > target)
			return origin + 1;
		else if (origin < target)
			return origin - 1;
	}
}

If its a phone interview, simple recursion with visited mark on all visited cells should do..

Here is pseudo code:
================

int f(srcRow, srcCol, tgtRow, tgtCol, numStepsSoFar){
	
	/* boundary check row/cols */
	if outOfBoundary(sRow, sCol) || outOfBoundary(tRow, tCol) 
		return Integer.MAX_VALUE;

	if(sRow==tgtRow && sCol==tgtCol)	return numStepsSoFar;

	visitedCells.add(sRow, sCol);

	if(!visisted(srcRow+1, sCol+1)		num1=f(sRow+1, sCol+1, numStepsSoFar+1);
	if(!visisted(srcRow-1, sCol+1)		num1=f(sRow-1, sCol+1, numStepsSoFar+1);
	if(!visisted(srcRow+1, sCol-1)		num1=f(sRow+1, sCol-1, numStepsSoFar+1);
	if(!visisted(srcRow-1, sCol-1)		num1=f(sRow-1, sCol-1, numStepsSoFar+1);

	return min(num1, num2, num3, num4);
}

#include<stdio.h>
#include<conio.h>

int findPos(int src,int dest)
{
int flag = 0,arr[8],temp=0,i=0,j=0,diff=0,min=65;
static int count,k,valid[64];


do{
++count;
i=0;

if((src % 8 == 3)||(src % 8 == 4)||(src % 8 == 5)||(src % 8 == 6))
{
temp=src-(8*2)-1;
if(temp > 0)
arr[i++]=temp;

temp=src-(8*2)+1;
if(temp > 0)
arr[i++]=temp;

temp=src-8+2;
if(temp > 0)
arr[i++]=temp;

temp=src-8-2;
if(temp > 0)
arr[i++]=temp;

temp=src+(8*2)-1;
if(temp > 0)
arr[i++]=temp;

temp=src+(8*2)+1;
if(temp > 0)
arr[i++]=temp;

temp=src+8+2;
if(temp > 0)
arr[i++]=temp;

temp=src+8-2;
if(temp > 0)
arr[i]=temp;
}

else if((src % 8 == 0)||(src % 8 == 7))
{
temp=src-(8*2)-1;
if(temp > 0)
arr[i++]=temp;

/*temp=src-(8*2)+1;
arr[i++]=temp;

temp=src-8+2;
arr[i++]=temp;*/

temp=src-8-2;
if(temp > 0)
arr[i++]=temp;

temp=src+(8*2)-1;
if(temp > 0)
arr[i++]=temp;
/*
temp=src+(8*2)+1;
arr[i++]=temp;

temp=src+8+2;
arr[i++]=temp;*/

temp=src+8-2;
if(temp > 0)
arr[i]=temp;

}

else if((src % 8 == 1)||(src % 8 == 2))
{/*
temp=src-(8*2)-1;
arr[i++]=temp;
*/
temp=src-(8*2)+1;
if(temp > 0)
arr[i++]=temp;

temp=src-8+2;
if(temp > 0)
arr[i++]=temp;
/*
temp=src-8-2;
arr[i++]=temp;

temp=src+(8*2)-1;
arr[i++]=temp;*/

temp=src+(8*2)+1;
if(temp > 0)
arr[i++]=temp;

temp=src+8+2;
if(temp > 0)
arr[i]=temp;

//temp=src+8-2;
//arr[i]=temp;
}
min = 65;
for(j=0;j<=i;j++)
{
if((arr[j] < 1)||(arr[j] > 64))
continue;
if(dest > arr[j])
diff = dest - arr[j];

else if(dest < arr[j])
diff = arr[j] - dest;

else
return count;

if((diff < min)&&(valid[arr[j]]!=1))
{
min = diff;
src=arr[j];
valid[arr[j]]=1;
flag=1;
}
}

//src=min;

}while(flag == 1);
}

int main()
{
int src=0,dest=0,count=0;

printf("\nEnter what is your source and destination : ");
scanf("%d %d",&src,&dest);

count=findPos(src,dest);
printf("\nTotal number of counts : %d",count);

getch();
return 0;
}

Graph with each square (x,y) as vertex and cost of edge((x,y),(x+/-1),(y+/-1))=1 and other edge costs are INT_MAX.

Use single source shortest path algorithm to find the shortest from (x,y) to (l,k) .

it's really not a programming problem, it is a MATH problem. if you try a to move a bishop from (a,b) to (c,d), and only allowed to move to the adjacent position, then then minimum steps required is min(abs(a-c), abs(b-d)). Of course when you play chess, you do not have to move only to the adjacent position, so at most 2 steps is required to move from (a,b) to (c,d).

private static List<string> shortestPath = new List<string>();
        public static void ChessMoves(bool[,] matrix, int startX, int startY, int endX, int endY, List<string> path)
        {
            ChessMovesInternal(matrix, startX, startY, endX, endY, path);
            foreach (string p in shortestPath)
                Console.WriteLine(p);
        }
        public static void ChessMovesInternal(bool[,] matrix, int startX, int startY, int endX, int endY, List<string> path)
        {
            if (startX< 0
                ||  startY <0
                ||  startX>=matrix.GetLength(0)
                ||  startY>=matrix.GetLength(1)
                ||  matrix[startX, startY])
            {
                return;
            }
            if (startX == endX && startY == endY)
            {
                path.Add(endX + ", " + endY);
                if (path.Count < shortestPath.Count 
                    || shortestPath.Count ==0 /*no path found yet*/)
                {
                    shortestPath = new List<string>();
                    foreach (string p in path) 
                        shortestPath.Add(p);
                }
                path.Remove(endX + ", " + endY);
                return;
            }
            List<int[]> nextStep = new List<int[]>();
            nextStep.Add(new int[] { startX - 1, startY - 1 });
            nextStep.Add(new int[] { startX + 1, startY + 1 });
            nextStep.Add(new int[] { startX - 1, startY + 1 });
            nextStep.Add(new int[] { startX + 1, startY - 1 });

            matrix[startX, startY] = true;//visited in this path
            path.Add(startX + ", " + startY);
            foreach (int[] nextStart in nextStep)
            {
                ChessMovesInternal(matrix, nextStart[0], nextStart[1], endX, endY, path);
            }
            path.Remove(startX + ", " + startY);
        }

Here's my O(1) code in java:

public class Main {
    public static void main(String[] args) {
        moveBishop(1, 1, 6, 2);
    }

    private static void moveBishop(int x1, int y1, int x2, int y2) {
        if ((x1 + y1) % 2 != (x2 + y2) % 2) {
            System.out.println("Impossible");
            return;
        } else if (Math.abs(x1 - x2) != Math.abs(y1 - y2)) {
            int x = (y2 + x2 - y1 + x1) / 2;
            int y = x + y1 - x1;

            if (x < 0 || y < 0) {
                x = (y2 - x2 - y1 - x1) / 2;
                y = x + y2 - x2;
            }
            System.out.println("(" + x + ", " + y + ")");
        }
        System.out.println("(" + x2 + ", " + y2 + ")");
    }
}

function findPath(i, j, ti, tj) {
if (ti < 0 || tj < 0) {
document.write("<BR> Invalid Target Position!!");
return;
}
while (1) {
if (((i+j)%2 != (ti+tj)%2) || i < 0 || j < 0 || i > 7 || j > 7) {
document.write("<BR> Invalid Target Position!!");
return;
}
if (ti + tj == i + j) {
if (ti < i) { i = i - 1; j = j + 1; }
else
if (ti > i) { i = i + 1; j = j - 1; }
}
else
if (ti <= i) {
i = i - 1; j = j - 1;
}
else {
i = i + 1;j = j + 1;
}
document.write("<BR> i:" + i + " j:" + j);
if (ti == i && tj == j) {
return;
}
}
}

function findPath(i, j, ti, tj) {
                if (ti < 0 || tj < 0) {
                    document.write("<BR> Invalid Target Position!!");
                    return;
                }
                while (1) {
                    if (((i+j)%2 != (ti+tj)%2) ||  i < 0 || j < 0 || i > 7 || j > 7) {
                        document.write("<BR> Invalid Target Position!!");
                        return;
                    }
                    if (ti + tj == i + j) {
                        if (ti < i) { i = i - 1; j = j + 1; }
                        else
                        if (ti > i) { i = i + 1; j = j - 1; }
                    }
                    else
                        if (ti <= i) {
                        i = i - 1; j = j - 1;
                    }
                    else {
                        i = i + 1;j = j + 1;
                    }
                    document.write("<BR> i:" + i + " j:" + j);
                    if (ti == i && tj == j) {
                        return;
                    }
                }
            }

NxN chessboard,

start (x1,y1)
end (x2,y2)

minimum moves required by bishop to go from start to end


1,1 1,2 1,3 1,4 1,5

2,1 2,2 2,3 2,4 2,5

3,1 3,2 3,3 3,4 3,5

4,1 4,2 4,3 4,4 4,5

5,1 5,2 5,3 5,4 5,5



int findMinMoves(int x1,int y1, int x2, int y2){

if(Math.abs(x2-x1) == Math.abs(y2-y1)){
return 1; // same diagonal
}

else
if( (Math.abs(x2-x1) + Math.abs(y2-y1))%2!=0 ){
return -1; //path does not exist
}
else{/*path exists*/
/* max 2 moves possible*/

return 2;
}
}

NxN chessboard,

start (x,y)
end (x,y)

minimum moves req by bishop to go from start to end


(1,1) : (5,5)

1 move


1,1 1,2 1,3 1,4 1,5

2,1 2,2 2,3 2,4 2,5

3,1 3,2 3,3 3,4 3,5

4,1 4,2 4,3 4,4 4,5

5,1 5,2 5,3 5,4 5,5

int findMinMoves(int x1,int y1, int x2, int y2){

       if(Math.abs(x2-x1) == Math.abs(y2-y1)){
           return 1;    // same diagonal
       }
       
       else
       if(    (Math.abs(x2-x1) + Math.abs(y2-y1))%2!=0    ){
           return -1;    //path does not exist
       }
       else{/*path exists*/
            /* max 2 moves possible*/
            
            return 2;
       }
}

Just use a DP Algorithm will solve this problem. Initiate a 8*8 matrix, start from the target position and use BFS to update the path in each possible position.