CareerCup

Here's my solution. I gave in interview adjacency Iist based solution.
Here I am giving both, adjacency-list and adjacency-matrix based solution for your reference:

//+--------------------------------------+
//| == ADJACENCY MATRIX BASED SOLUTION ==|
//+--------------------------------------+

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>

using namespace std;

#define MAX_MOVES 8
struct coord
{
	int row;
	int col;
};

coord possibleMoves[] = 
{    
	{-2, +1},
	{-1, +2},
	{+1, +2},
	{+2, +1},
	{+2, -1},
	{+1, -2},
	{-1, -2},
	{-2, -1}
};
int isValid(int r, int c)
{
	if((r >= 0 && r <= 7)&&
		(c >= 0 && c <= 7))
		return 1;
	return 0;
}

void getValidMoves(int r, int c, coord *lst, int *size)
{
	assert(lst);
	assert(size);
	*size = 0;
	for(size_t i = 0; i<sizeof(possibleMoves)/sizeof(possibleMoves[0]); i++)
	{
		if(isValid(r + possibleMoves[i].row, c + possibleMoves[i].col))
		{
			lst[*size].row = r + possibleMoves[i].row;
			lst[*size].col = c + possibleMoves[i].col;
			(*size)++;
		}
	}

	return ;
}

int ChessBoard[MAX_MOVES*MAX_MOVES][MAX_MOVES*MAX_MOVES];

void backTrack(int row, int col)
{
	int size = 0;
	coord moves[MAX_MOVES] = {{0, 0}};
	getValidMoves(row, col, moves, &size);
	for(int i = 0; i < size; i++)
	{
		if(ChessBoard[row*8+col][moves[i].row*8 + moves[i].col] != 1)
		{
			ChessBoard[row*8+col][moves[i].row*8 + moves[i].col] = 1;
			backTrack(moves[i].row, moves[i].col);
		}
	}
}

void getAllPositions()
{
	int r = 0, c = 0;

	cout << "Cell's row index = ";
	cin >> r;
	cout << "Cell's column index = ";
	cin >> c;

	//r = 3, c = 3;
	backTrack(r, c);
	cout << "   " ;
	for(int i = 0; i < MAX_MOVES*MAX_MOVES; i++)
		printf("%2d ", i);
	cout << endl;

	for(int i = 0; i < MAX_MOVES*MAX_MOVES; i++)
	{
		printf("%2d ", i);
		for(int j = 0; j < MAX_MOVES*MAX_MOVES; j++)
			printf("%2d ", ChessBoard[i][j]); // << endl;
		cout << endl;
	}
	return;
}
/////////////////////////////////////////////////////////////////////////
//+------------------------------------+
//| == ADJACENCY LIST BASED SOLUTION ==|
//+------------------------------------+
#define MAX_CHILDREN 8
#define POSITIONS 8


class graphNode
{
	static bool bChessBoard[POSITIONS][POSITIONS];
public:
	coord pos;
	graphNode* children[MAX_CHILDREN];
	int count;
	static bool isOccupied(int r, int c)
	{
		if(isValid(r, c))
			return bChessBoard[r][c];
		return false;
	}

	static void setOccupied(int r, int c)
	{
		if(isValid(r, c))
			bChessBoard[r][c] = 1;
	}

	graphNode():count(0)
	{
		pos.row = -1;
		pos.col = -1;
	}

	graphNode(int r, int c):count(0)
	{
		pos.row = r;
		pos.col = c;
	}


	static graphNode *getGraphNode(int r, int c)
	{
		graphNode *aNode = new graphNode(r, c);
		memset(aNode->children, 0, MAX_CHILDREN*sizeof(graphNode*));
		return aNode;
	}
};
bool graphNode::bChessBoard[POSITIONS][POSITIONS];

void backTrackAdjList(graphNode *root, int row, int col)
{
	assert(root);
	int size = 0;
	coord moves[MAX_MOVES] = {{0, 0}};
	getValidMoves(row, col, moves, &size);
	for(int i = 0; i < size; i++)
	{
		if(!graphNode::isOccupied(moves[i].row, moves[i].col) )
		{
			graphNode *g = graphNode::getGraphNode(moves[i].row, moves[i].col);
			root->children[root->count++] = g;
			graphNode::setOccupied(moves[i].row, moves[i].col);
			backTrackAdjList(g, moves[i].row, moves[i].col);
		}
	}
}

void dfsVisit(graphNode* root)
{
	if(!root)
		return;
	cout << "row = " << root->pos.row << " col = " << root->pos.col << endl;

	for(int i = 0; i < root->count; i++)
		dfsVisit(root->children[i]);

	return;
}
void freeGraph(graphNode* root)
{
	if(!root)
		return;

	for(int i = 0; i < root->count; i++)
		freeGraph(root->children[i]);
	free(root);
	root = NULL;
	return;
}

void getAllPositionsAdjList()
{
	int r = 0, c = 0;

	cout << "Cell's row index = ";
	cin >> r;
	cout << "Cell's column index = ";
	cin >> c;

	//r = 3, c = 3;
	if(!isValid(r, c))
		return;

	graphNode *root = graphNode::getGraphNode(r, c);
	graphNode::setOccupied(r, c);
	backTrackAdjList(root, r, c);

	dfsVisit(root);

	freeGraph(root);
	return;

}

A knight can move in 8 directions from the current position
2 in front, 4 sideways and 2 backwards.
Thus we can easily calculate the position using recursion from the current position where a knight can move.

Here is a algo that I have thought
void KnightMove(int **a, int m, int n, int currx, curry)
{
if(currx<0 || curry <0)
return;
if(currx >= n || curry >=m)
return;
if(a[currx][curry] == VISITED)
return;
else
{
a[currx][curry] == VISITED;

//move forward
KnightMove(a, m, n, currx-1, curry+2);
KnightMove(a, m, n, currx+1, curry+2);

//move sideways
KnightMove(a, m, n, currx-2, curry+1);
KnightMove(a, m, n, currx-2, curry-1);
KnightMove(a, m, n, currx+2, curry+1);
KnightMove(a, m, n, currx+2, curry-1);

//move backward
KnightMove(a, m, n, currx-1, curry-2);
KnightMove(a, m, n, currx+1, curry-2);

}
}

Please do let me know If I am missing something here

Do you need all the places that the knight can eventually reach, or all the places the knight can reach in one move? A knight can eventually reach any square on a standard chessboard.

@aka: Trust me this will eventually stop :). And it will stop when u reach invalid cells .
Invalid cell means something like: (-1, -2) or (8, 8) or (-1, 2) etc etc...
I hope this makes it clear.

This problem reduces to the standard BFS algorithm with the only difference being the edges are not present! Instead of going out from the source square following the adjacent edges we need to follow the knight move pattern and find the adjacent squares that are reachable from any square by the knight.

[DebuggerDisplay("{ToString()}, Visited = {Visited}")]
    public class ChessSquare
    {
        private readonly int _row;
        private readonly int _column;

        public ChessSquare(int row, int column)
        {
            _row = row;
            _column = column;
            Visited = false;
            Parent = null;
        }

        public int Row { get { return _row; } }
        public int Column { get { return _column; } }
        public ChessSquare Parent { get; set; }
        public bool Visited { get; set; }

        public static bool IsValid(int row, int column)
        {
            return (row >= 0 && row < 8 && column >= 0 && column < 8);
        }

        public override string ToString()
        {
            return string.Format("{0}{1}", (char)((int)'a' + _row), _column + 1);
        }
    }

    public class Chess
    {
        ChessSquare[,] _board;

        public Chess()
	    {
		    _board = new ChessSquare[8, 8];
		    InitializeSquares();
        }

        private void InitializeSquares()
        {
            for (int row = 0; row < 8; row++)
            {
                for (int col = 0; col < 8; col++)
                {
                    _board[row, col] = new ChessSquare(row, col);
                }
            }
        }

        public void DiscoverKnightMoves(int row, int column)
        {
            var queue = new Queue<ChessSquare>();
            var sourceSquare = _board[row, column];
            sourceSquare.Visited = true;
            queue.Enqueue(sourceSquare);

            while (queue.Count > 0)
            {
                var current = queue.Dequeue();
                var adjacentSquares = GetAdjacentSquares(current.Row, current.Column);
                foreach (var square in adjacentSquares)
                {
                    square.Visited = true;
                    square.Parent = current;
                    queue.Enqueue(square);
                }
            }

            PrintPaths();
        }

        private List<ChessSquare> GetAdjacentSquares(int row, int col)
        {
            var adjacentSquares = new List<ChessSquare>();

            //north-east quadrant
            CheckAdd(row - 1, col + 2, adjacentSquares);
            CheckAdd(row - 2, col + 1, adjacentSquares);

            //south-east quadrant
            CheckAdd(row + 1, col + 2, adjacentSquares);
            CheckAdd(row + 2, col + 1, adjacentSquares);

            //north-west quadrant
            CheckAdd(row - 1, col - 2, adjacentSquares);
            CheckAdd(row - 2, col - 1, adjacentSquares);

            //south-west quadrant
            CheckAdd(row + 1, col - 2, adjacentSquares);
            CheckAdd(row + 2, col - 1, adjacentSquares);

            return adjacentSquares;
        }

        private void CheckAdd(int row, int column, List<ChessSquare> adjacentSquares)
        {
            if (ChessSquare.IsValid(row, column) && !_board[row, column].Visited)
                adjacentSquares.Add(_board[row, column]);
        }

        private void PrintPaths()
        {
            foreach (var square in _board)
            {
                //only if square has been visited it is reachable from the source square
                if (square.Visited)
                {
                    PrintPath(square);
                    Console.WriteLine();
                }
            }
        }

        private void PrintPath(ChessSquare square)
        {
            if (square != null)
            {
                Console.Write("{0}", square);
                if (square.Parent != null)
                    Console.Write(" <- ");

                PrintPath(square.Parent);
            }
        }
    }

public static bool FindAllPos(int x, in y, int[,] reachTable)
{
//x= 1,...,8; y= 1,...,8
if(x<1||x>8||y<1||y>8) return false;
if( reachTable[x-1,y-1] !=0) return false;
bool flag = false;
for( int i =-2;i<=2;++)
{
for(int j = -2; j<=2; ++j)
{
if( (i*i)+(j*j) != 5 ) continue; //Knight always jump this distance. Total 8 cases.

if( FindAllPos(x+i, y+j, reachTable) )
{ //reach table element remember the previous position
reachTable[x+i,y+j] = x + (y-1)*8; // To identify 8*8 tatal 1,2,3,...,64 possible positions
flag = true;
}

}
}
return flag;
}

public static main()
{ int x = 2; int y =3;
int[8,8] reach_table = new int[8,8]{0};
FindAllPos(x,y, reach_table);
}

1) Use BFS to compute all the positions that are reachable from the knight.
2) For each position, store it in a Hash
3) Compute a trie structure when doing BFS, basically is you can reach positions Y and Z from X, then X has two children Y and Z; and also maintain parent pointer for Y and Z which point to X

If the query is if P can be reached, then look the hashtable and return true if present.
If path is requested, then trace the path from P to root (starting position) using parent pointers.

If the query is to

package graphs.search;

import utility.Queue;

import java.util.ArrayList;
import java.util.List;

class ChessCell {

    private int x;
    private int y;
    //Path to reach the cell from the start cell
    List<ChessCell> pathList;

    public ChessCell(int x, int y) {
        this.x = x;
        this.y = y;
        this.pathList = new ArrayList<>();
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public String toString() {
        return "("+x+","+y+")";
    }

    public boolean compareAnotherChessCell(ChessCell cell) {

        return this.getX() == cell.getX() && this.getY() == cell.getY();

    }

}

public class KnightPositionChess {

    private static final int[] XMOVE = new int[]{2, 1, -1, -2, -2, -1, 1, 2};
    private static final int[] YMOVE = new int[]{1, 2, 2, 1, -1, -2, -2, -1};
    private static final int N = 3;
    private ChessCell startCell;
    private List<ChessCell> reachableFromStartCell;

    public KnightPositionChess(int x,int y) {
        startCell = new ChessCell(x,y);
        reachableFromStartCell = findAllReachable();
    }

    public Iterable<ChessCell> findPath(int x,int y) {

        ChessCell newChessCell = new ChessCell(x,y);

        if(reachableFromStartCell.isEmpty()) {
            findAllReachable();
        }

        for (ChessCell cell : reachableFromStartCell) {
            if(cell.compareAnotherChessCell(newChessCell)) {
                return cell.pathList;
            }
        }

        return null;

    }

    public Iterable<ChessCell> getReachableCells() {
        return reachableFromStartCell;
    }

    private List<ChessCell> findAllReachable() {

        startCell.pathList.add(startCell);

        Queue<ChessCell> queue = new Queue<>();
        queue.enqueue(startCell);
        List<ChessCell> reachableCells = new ArrayList<>();

        boolean[][] visited = new boolean[N][N];
        visited[startCell.getX()][startCell.getY()] = true;

        while (!queue.isEmpty()) {

            ChessCell current = queue.dequeue();
            int currentX = current.getX();
            int currentY = current.getY();

            for (int i=0;i<8;i++) {

                int newX = currentX + XMOVE[i];
                int newY = currentY + YMOVE[i];

                if(isValid(newX,newY,visited)) {
                    ChessCell newCell = new ChessCell(newX,newY);
                    //Visited true is marked as soon as the cell is visited, so that it is not visited while bfs of another cell
                    visited[newX][newY] = true;
                    newCell.pathList = new ArrayList<>(current.pathList);
                    newCell.pathList.add(newCell);
                    queue.enqueue(newCell);
                    reachableCells.add(newCell);
                }

            }

        }

        return reachableCells;


    }

    private boolean isValid(int x,int y,boolean[][] visited) {

        return (x>=0 && y>=0 && x<N && y<N && !visited[x][y]);

    }


    public static void main(String[] args) {

        KnightPositionChess kp = new KnightPositionChess(2,0);
        Iterable<ChessCell> iterable = kp.getReachableCells();

        System.out.println("All reachable vertices are : ");
        for (ChessCell coordinates : iterable) {
            System.out.print(coordinates.toString() +  " ");
        }


        System.out.println("path for element 0,2 :  " );
        for (ChessCell coordinates : kp.findPath(0,2)) {
            System.out.print(coordinates.toString() +  " ");
        }

    }

}