CareerCup

Shortest Path in almost all cases is a breadth first search implementation. (BFS).

The idea is as follows:
1. Start from the source location.
2. Find all the possible locations Knight can move to from the given location.
3. As long as the possible locations are inside the chessboard, add all such locations to a queue (to process one after the other)
4. Perform steps 1 to 3 until queue is exhausted.
5. If destination location is found in Step 2, report the location and the path.

Note:
1. To find all possible locations a Knight can jump to:
I have used pythagorean theorem where a move makes a right angle triangle of one side to be of size 1 and second side to be of size 2 positions. So as per the theorem, the addition of squares of the 2 sides is equal to the square of 3rd side. (1^2 + 2^2 = 5)

2. To track back shortest path:
The chess board is created with Position Object which consists of X and Y co-ordinates and depth variable which says deep the location is from the source location.
X and Y objects are the co-ordinates of the source location from where the jump was made.

Below is the complete code which gives the number of jumps required for Knight to reach the destination location and also the actual path.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class KnightShortestPathToDest {

	static final Pos[][] chessboard = new Pos[8][8];

	static Queue<Pos> q = new LinkedList<Pos>();
	
	public static void main(String[] args) {
		
		//Populate the chessboard with position values as unreachable
		populateChessBoard();
		
		//Assume the position for simplicity. In real world, accept the values using Scanner.
		Pos start = new Pos(0, 1, 0); // Position 0, 1 on the chessboard
		Pos end = new Pos(4, 4, Integer.MAX_VALUE);
		
		//Assign starting depth for the source as 0 (as this position is reachable in 0 moves)
		chessboard[0][1] = new Pos(start.x, start.y, 0);
		
		//Add start position to queue
		q.add(start);

		while (q.size() != 0) // While queue is not empty
		{
			Pos pos = q.poll(); //read and remove element from the queue
			
			//If this position is same as the end position, you found the destination
			if (end.equals(pos)) {
				// We found the Position. Now trace back from this position to get the actual shortest path 
				Iterable<Pos> path = getShortestPath(start, end);
				System.out.println("Minimum jumps required: " + pos.depth );
				System.out.println("Actual Path");
				System.out.println("("+pos.x + " " + pos.y+")");
				
				for(Pos position: path) {
					System.out.println("("+position.x + " " + position.y+")");
				}
				
				return;
			}
			else {
				// perform BFS on this Pos if it is not already visited
				bfs(pos, ++pos.depth);
			}
		}

		//This code is reached when the queue is empty and we still did not find the location.
		System.out.println("End position is not reachable for the knight");
	}

	//Breadth First Search 
	private static void bfs(Pos current, int depth) {

		// Start from -2 to +2 range and start marking each location on the board
		for (int i = -2; i <= 2; i++) {
			for (int j = -2; j <= 2; j++) {
				
				Pos next = new Pos(current.x + i, current.y + j, depth);
			
				if(inRange(next.x, next.y)) {
					//Skip if next location is same as the location you came from in previous run
					if(current.equals(next)) continue;

					if (isValid(current, next)) {
						
						Pos position = chessboard[next.x][next.y] ;
						/* 
						 * Get the current position object at this location on chessboard. 
						 * If this location was reachable with a costlier depth, this iteration has given a shorter way to reach
						 */
						if (position.depth > depth) {
							chessboard[current.x + i][current.y + j] = new Pos(current.x, current.y, depth);
							q.add(next);
						}
					}
				}

			}

		}

	}

	private static boolean inRange(int x, int y) {
		return 0 <= x && x < 8 && 0 <= y && y < 8;
	}

	/*Check if this is a valid jump or position for Knight based on its current location */
	public static boolean isValid(Pos current, Pos next) {
		// Use Pythagoras theorem to ensure that a move makes a right-angled triangle with sides of 1 and 2. 1-squared + 2-squared is 5.
		int deltaR = next.x - current.x;
		int deltaC = next.y - current.y;
		return 5 == deltaR * deltaR + deltaC * deltaC;
	}

	/*Populate initial chessboard values*/
	private static void populateChessBoard() {
		for (int i = 0; i < chessboard.length; i++) {
			for (int j = 0; j < chessboard[0].length; j++) {
				chessboard[i][j] = new Pos(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE);
			}
		}
	}
	
	/*Get the shortest Path and return iterable object */
	private static Iterable getShortestPath(Pos start, Pos end) {
		
		Stack<Pos> path = new Stack<Pos>();
		
		Pos current = chessboard[end.x][end.y];
		while(! current.equals(start)) {
			path.add(current);
			current = chessboard[current.x][current.y];
		}
		path.add(new Pos(start.x, start.y, 0));
		return path;
	}

}

class Pos {

	public int x;
	public int y;
	public int depth;
	
	Pos(int x, int y, int depth) {
		this.x = x;
		this.y = y;
		this.depth = depth;
	}

	public boolean equals(Pos that) {
		return this.x == that.x && this.y == that.y;
	}

	public String toString() {
		return "("+this.x + " " + this.y+ " " + this.depth +")";
	}
}

The output of this program:

Minimum jumps required: 3
	Actual Path
	(4 4)
	(2 5)
	(1 3)
	(0 1)

Time complexity O(V+E) and space complexity of O(V) for storing vertices on queue.

In a real work scenario: a constructor would generate the chessboard with all possible positions where knight can move to.
Therefore time complexity for
1. API call for number of Jumps will be O(1)
2. giving the actual shortest path O(V)

Lets view chess as a graph. Each square is a node in graph, and there are edges between nodes, if knight can directly go from one location to another. Our goal is to find the shortest path from start to end location in this graph.

I solved it by using a breadth first search in this graph. Taken a 8 X 8 array, marked start position with 0. All the squares where knight can reach from starting location are marked as 1. All the locations where knight can reach from 1 locations, were marked as 2. This process was repeated, until we get a no. in our end location. No. in end location denotes the no. of moves needed, and we can backtrace from there to find the path sequence for knight.

void print_path(unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2) {
	if ((x1 > 7) || ((x2 > 7) || (y1 > 7) || (y2 > 7))
		return;

	unsigned int a[8][8], i, j;
	for (i = 0; i < 8; i++)
		for (j = 0; j < 8; j ++)
			a[i][j] = 9999;
	
	a[x1][y1] = 0;
	i = 0;
	while (a[x2][y2] != 9999) {
		i ++;
		move(a, i);
	}

	print_backtrace(a, x2, y2, i);
}

void move(unsigned int a[][], unsigned int n) {
	unsigned int i, j, b[8][2], c, k;
	for (i = 0; i < 8; i ++) 
		for (j = 0; j < 8; j ++) {
			if (a[i][j] == n - 1) {
				c = get_moves(a, i, j, b);
				for (k = 0; k < c; k++) {
					if (a[b[k][0]][b[k][1]]  == 9999)
						a[b[k][0]][b[k][1]] = n;
				}
			}
		}

	return;
}

unsigned int get_moves(unsigned int a[][], unsigned int x, unsigned int y, unsigned int b[][]) {
	int i = x + 1, j = y + 2;
	unsigned int c = 0;
	
	if ((i < 8) && (j < 8)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x + 1; j = y - 2;
	if ((i < 8) && (j >= 0)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x - 1; j = y + 2;
	if ((i >= 0) && (j < 8)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x - 1; j = y - 2;
	if ((i >= 0) && (j >= 0)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x + 2; j = y + 1;
	if ((i < 8) && (j < 8)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x + 2; j = y - 1;
	if ((i < 8) && (j >= 0)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x - 2; j = y + 1;
	if ((i >= 0) && (j < 8)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	i = x - 2; j = y - 1;
	if ((i >= 0) && (j >= 0)) {
		b[c][0] = i;
		b[c++][1] = j;
	}

	return c;
}

void print_backtrace(unsigned int a[][], unsigned int x, unsigned int y, unsigned int n) {
	if (n == 0) {
		printf("[%u, %u]\n", x, y);
		return;
	}

	unsigned int b[8][2], c, i;
	c= get_moves(a, x, y, b);
	for (i = 0; i < c; i ++) {
		if (a[b[i][0]][b[i][1]] == n - 1) {
			print_backtrace(a, b[i][0], b[i][1], n - 1);
			break;
		}
	}

	printf("[%u, %u]\n", x, y);
}

1) use BFS (shortest path with no weights on edge)
2) implement no nodes and no edges, just keep the parent-pointer of the BFS traversal tree as coordinates in the chess-board

from collections import deque

N = 8
board_p = [[(-1,-1) for f in range(0,N)] for i in range(0,N)]

def Adjacents(u):    
    adj = []
    for e in [(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(1,-2),(-1,2),(1,2)]:        
        v = (u[0] + e[0], u[1] + e[1])
        if v[0] >= 0 and v[0] < N and v[1] >= 0 and v[1] < N: adj.append(v)
    return adj;

def Moves(s,t):
    q = deque()
    q.append(s)
    board_p[s[0]][s[1]] = s # "root" of BFS-traversal points to it self (avoid loop over "back-edge" to s)
    while q:
        u = q.popleft()
        if u == t: break
        for v in Adjacents(u):
            if board_p[v[0]][v[1]] == (-1,-1):
                board_p[v[0]][v[1]] = u
                q.append(v)

    # walk the path back (using parent "pointers")
    path = [(t)]    
    while t != s:
        t = board_p[t[0]][t[1]]
        path.append(t)

    path.reverse()
    return path

   
print(Moves((1,1),(5,5)))

static int[,] offsets = { { -2, -1 }, { -1, -2 }, { 2, -1 }, { 1, -2 }, { -2, 1 }, { -1, 2 }, { 2, 1 }, { 1, 2 } };

static int GetIndex(int row, int col)
{
return row * 8 + col;
}

static int GetRow(int ind)
{
return ind / 8;
}

int GetCol(int ind)
{
return ind % 8;
}

List<int> FindShortestPath(int startInd, int endInd)
{
var path = new List<int>();
List<int> resultPath = null;
int[] field = new int[64];
for (int i = 0; i < 64; i++)
{
field[i] = -1;
}
FindRecursive(field, startInd, endInd, path, ref resultPath);
return resultPath;
}


List<int> GetNextIndexes(int curInd)
{
var row = GetRow(curInd);
var col = GetCol(curInd);
var nextInds = new List<int>();
for (int i = 0; i < offsets.GetLength(0); i++)
{
var newRow = row + offsets[i, 0];
var newCol = col + offsets[i, 1];
if (newRow >= 0 && newRow < 8 && newCol >= 0 && newCol < 8)
{
nextInds.Add(GetIndex(newRow, newCol));
}
}
return nextInds;
}

void FindRecursive(int[] field, int curInd, int endInd, List<int>path, ref List<int> resultPath)
{
field[curInd] = path.Count;
if (curInd == endInd && (resultPath == null || resultPath.Count > path.Count))
{
resultPath = new List<int>(path);
return;
}
foreach (var nextInd in GetNextIndexes(curInd))
{
if (path.Count <= 6 && (field[nextInd] == -1 || field[nextInd] > path.Count + 1))
{
path.Add(nextInd);
FindRecursive(field, nextInd, endInd, path, ref resultPath);
path.Remove(nextInd);
}
}
}

I wrote my own version using Java 8 constructs, and with some extra diagnostic code to show an optimization that rules out any jumps that would take the knight obviously in the wrong direction (away from the target). Note that the distance-comparison algorithm includes a "fudge factor" of 3 units squared, to account for cases where the knight is too close to the target and needs to move to a spot farther away.

This uses a breadth-first search similar to other implementations shown here, though I like to think that it models the knight's movement behavior more directly.

public class HelloWorld{
    public static void main(String []args) {
        KnightSolver solver = new KnightSolver();
        
        System.out.print("Unoptimized: ");
        solver.solve(4,4, 7, 0, false);

        System.out.print("Optimized  : ");
        solver.solve(4,4, 7, 0);

        System.out.println();
        System.out.println("More test cases:");
        solver.solve(4,2, 4,4);
        solver.solve(0,0, 2,1);
        solver.solve(3,2, 5,2);
        solver.solve(0,0, 0,1);
        solver.solve(0,0, 0,7);
        solver.solve(0,0, 7,4);
    }
}

===========

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class KnightSolver {
    private Cell[][] board;
    private Cell start;
    private Cell end;

    public void solve(int startX, int startY, int endX, int endY) {
        solve(startX, startY, endX, endY, true);
    }

    public void solve(int startX, int startY, int endX, int endY, boolean useOptimization) {
        this.start = new Cell(startX, startY);
        this.end = new Cell(endX, endY);

        board = new Cell[Cell.BOARD_SIZE][Cell.BOARD_SIZE];
        board[start.x][start.y] = start;

        // Note: We could also use a HashSet<Cell> to keep track of
        // cells we've already visited (with a sensible HashCode on Cell).
        // However, a HashSet could actually be much more memory-expensive
        // than a sparse 2D array because it allocates enough room for
        // 2^32 pointers + collision-resolution, whereas our array has
        // exactly size^2 slots (e.g. 8*8 = 64), and element access is O(1) in both cases.

        Queue<Cell> q = new LinkedList<>();
        q.add(start);
        int queuedItems = 1;

        while (!q.isEmpty()) {
            Cell curCell = q.remove();
            
            if (curCell.equals(end)) {
                Stack<Cell> path = traceBack(curCell);
                printPath(path, queuedItems);
                break;
            } else {
                // radiate outward from this position.
                for (Cell c : curCell.getPossibleJumps(board, end, useOptimization)) {
                    board[c.x][c.y] = new Cell(curCell.x, curCell.y);
                    q.add(c);
                    queuedItems++;
                }
            }
        }
    }
    
    private Stack<Cell> traceBack(final Cell endPath) {
        Cell curCell = end;

        Stack<Cell> path = new Stack<>();
        path.push(curCell);

        do {
            curCell = board[curCell.x][curCell.y];
            path.push(curCell);
        } while (!curCell.equals(start));

        return path;
    }
    
    private void printPath(final Stack<Cell> path, final int queuedItems) {
        StringBuilder sb = new StringBuilder();
        int numJumps = path.size() - 1;
        
        while (!path.isEmpty()) {
            Cell c = path.pop();
            sb.append(c);
            if (!path.isEmpty()) {
                sb.append(" -> ");
            }
        }

        System.out.println(String.format(
            "%d jump(s) from %s to %s: %s (%d space(s) considered)",
            numJumps, start, end, sb.toString(), queuedItems
        ));
    }
}

===============

import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Cell {
    public static final int BOARD_SIZE = 8;
    private static final int IDEAL_SQ_DISTANCE = 5; // 2x1 units = 2*2 + 1*1

    // Defines all the possible jump vectors from a given cell.
    private static List<Cell> jumps = Stream.of(
        new Cell(-2, -1),
        new Cell(-1, -2),
        new Cell(-2,  1),
        new Cell(-1,  2),
        new Cell( 2, -1),
        new Cell( 1, -2),
        new Cell( 2,  1),
        new Cell( 1,  2)
    ).collect(Collectors.toList());

    public int x;
    public int y;

    public Cell(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public boolean equals(Cell that) {
        return (x == that.x && y == that.y);
    }

    @Override
    public String toString() {
        return String.format("(%d,%d)", x, y);
    }
    
    public List<Cell> getPossibleJumps(
        final Cell[][] board,
        final Cell target,
        final boolean useOptimization
    ) {
        if (useOptimization && sqDistanceTo(target) == IDEAL_SQ_DISTANCE) {
            // This square is one move away from the target, so only return the target.
            return Stream.of(target).collect(Collectors.toList());
        }

        return jumps.stream()
            .map(c -> new Cell(x + c.x, y + c.y))
            .filter(c -> c.isOnBoard())
            .filter(c -> board[c.x][c.y] == null)
            .filter(c -> !useOptimization || isGoodJump(c, target))
            .collect(Collectors.toList());
    }

    private boolean isGoodJump(final Cell jump, final Cell target) {
        int sqDistThis = sqDistanceTo(target);
        int sqDistJump = jump.sqDistanceTo(target);

        if (sqDistThis == 4) { // 2 units orthogonal
            // Special case: Exactly two jumps will get us to the ideal distance from the target.
            return sqDistJump == IDEAL_SQ_DISTANCE;
        }

        // Normal cases: If the jump obviously moves us away from the target, disregard it.
        return sqDistJump < sqDistThis + 3;
    }

    private boolean isOnBoard() {
        return (0 <= x && x < BOARD_SIZE && 0 <= y && y < BOARD_SIZE);
    }

    public int sqDistanceTo(final Cell target) {
        int diffx = target.x - x;
        int diffy = target.y - y;
        return diffx*diffx + diffy*diffy;
    }
}

The output from the HelloWorld.main method is as follows:

Unoptimized: 3 jump(s) from (4,4) to (7,0): (4,4) -> (3,2) -> (5,1) -> (7,0) (64 space(s) considered)
Optimized  : 3 jump(s) from (4,4) to (7,0): (4,4) -> (3,2) -> (5,1) -> (7,0) (15 space(s) considered)

More test cases:                                                                                                                                                                                                                                              
2 jump(s) from (4,2) to (4,4): (4,2) -> (6,3) -> (4,4) (5 space(s) considered)
1 jump(s) from (0,0) to (2,1): (0,0) -> (2,1) (2 space(s) considered)
2 jump(s) from (3,2) to (5,2): (3,2) -> (4,4) -> (5,2) (5 space(s) considered)
5 jump(s) from (0,0) to (0,7): (0,0) -> (2,1) -> (0,2) -> (1,4) -> (2,6) -> (0,7) (28 space(s) considered)
5 jump(s) from (0,0) to (7,4): (0,0) -> (1,2) -> (3,1) -> (4,3) -> (5,5) -> (7,4) (42 space(s) considered)

def subStringReverse(my_arr, n):
    if n <= len(my_arr):
        sub_arr1 = my_arr[n-1::-1]
        sub_arr2 = my_arr[n:]
        return sub_arr1+sub_arr2
    return 0

my_arr = [1,2,3,4,5,6,7,8,9]
print subStringReverse(my_arr, 6)

How To Approach when moves are Perpendicular. In Knight Problem Grid is N*N?

public class Point
{
	int row;
	int col;
	
	public int hashCode()
	{
		return Objects.hashCode(new Integer(row), new Integer(col));
		
	}
	
	public boolean equals(Object obj)
	{
		if(obj==null||! obj instanceOf(Point))
		{
			return false;
		}
		Point p=(Point)obj;
		return p.hashCode()==hashCode();
	}
}

public ArrayList<Point> shortPath(Point start, Point end)
{
	if(start==null||end==null||start.row<0||start.row>=8||end.row<0||end.col>=8)
	{
		return null;
	}
	
	return bfs(start,end,new HashMap<Point,Point>());
}

private ArrayList<Point> bfs(Point start,Point end, HashMap<Point,Point> mp)
{
	ArrayList<Point> result=new ArrayList<Point>();
	
	Deque<Point> q=new LinkedList<Point>();
	q.addFirst(start);
	mp.put(start,null);
	while(!q.isEmpty())
	{
		Point top=q.removeFirst();
		if(top.equals(end))
		{
			Point key=top;
			while(key!=null)
			{
				result.add(0,key);
				key=mp.get(key);
			}
			break;
		}
		Point[] next={new Point(2,1),new Point(2,-1),new Point(-2,1),new Point(-2,-1),new Point(1,2),new Point(1,-2),new Point(-1,2),new Point(-1,-2)};
		for(Point p:next)
		{
			Point f=new Point(top.row+p.row,top.col+p.col);
			if(!mp.containsKey(f) && (f.row>=0 && f.row<8) && (f.col>=0 && f.col<8))
			{
				q.addLast(f);
				mp.put(f,top);
			}
		}
	}
	return result;
}


Time Complexity: O(1) Assuming chessboard is always 8x8. Otherwise O(N^2) where N is the number of rows. Space Complexity: O(1) in 8x8 case otherwise O(N^2).