Register | Login
RSS  RSS

2

You are given a standard chessboard consisting of 64 squares (eight rows and eight columns) arranged in two alternating colors. There are no pieces on the board except for one knight. The knight moves according to standard chess rules.

It can move two squares horizontally and one square vertically, or two squares vertically and one square horizontally. The completed move therefore looks like the letter 'L'. The green dots on the image represent all eight possible moves.

The task is to write a function based on the input of the beginning and end positions, and will return a minimum number of moves required for the knight to reach the end, indicated by a checkmark on the chessboard:

int FindPath(int x, int y, int x1, int y1)


4 Answers  |  Bury | 
Interview Puzzles | microsoft chess puzzle all All


Attached file(s)

http://interviewpattern.com/pics/chess.png

Who Voted for this Question


Article

Answers

User Avatar
Written by lrreiche


The problem as posed puts no premium on an efficient solution, so we'll not worry about that.

initialize an 8x8 integer array with -1 // represents the chessboard
put a zero at x, y // the knight's initial position
while (the array element at x1, y1 is -1) do // the knight's final position
for each element of the array
if that element is not -1
remember that element's value+1
for each of the eight move directions
if (the resulting position is in bounds) then
if (the resulting position's value is -1) then
set the resulting position's value to the remembered value
return the value of the array element at x1, y1


User Avatar
Written by jane


Hmm.. I don't think it will yield to "minimum number of moves" required by the problem definition. But I might be wrong.


User Avatar
Written by lrreiche


It does give the minimum number of moves necessary to go from x,y to x1,y1, but computes the path length inefficiently. It is a breadth-first search: All paths of n moves are explored before any paths of n+1 moves, thus, if x1,y1 is reachable in n moves, we've found an n-move path before trying any longer paths.

The spec didn't say that our algorithm had to be optimal, as well.


User Avatar
Written by CMaster


The key to solving this problem is to realize that it is actually about the graph. Let’s assume that the passed starting point is the source of our graph, while eight possible moves are the vertexes connected to that point. We can continue building our graph moving from vertex to vertex and finding the point to where the knight might move from there. On the image below you can see a small subset of this graph. For instance, from point d6 you can get to the point f5, e8, and c8 (five more points are not displayed on the image for the sake of simplicity).


Although this solution is very simple, we need to traverse this graph with a breadth-first search, counting the number of visited vertexes, until we reach the final point. The only problem is that the adjacency matrix will be really big and might require a lot of effort to build. From the over side, for any given point (x,y) in the graph we can always find its eight or fewer neighbors as (x+2,y+1), (x+2,y-1), (x+1,y+2), (x+1,y-2), (x-1,y+2), (x-1,y-2), (x-2,y+1), (x-2,y+1). A simple check will be required for verifying if the neighbor lies outside of the chess board. Taking this into consideration, we don’t need to store the graph in memory at all; we just need to know our current point on the board.



Log in to comment or answer questions or register here.


CommonInterview
Common Interview is a place to help people keep up with the latest trends in job interviewing. You can interact by asking interview questions or by providing answers and ratings. Choose from thousands behavioural, technical, testing or program management questions and interview puzzles.
Top Users
FOLLOW ONCommonInterview Twitter Account
Live