﻿<?phpxml version="1.0" encoding="utf-8"?>
<rss version="2.0" 
xmlns:content="http://purl.org/rss/1.0/modules/content/"
xmlns:wfw="http://wellformedweb.org/CommentAPI/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
>
<channel>
<title>Common Interview Questions - Lonely knight</title>
<link>http://commoninterview.com/interview_puzzles/lonely-knight-1/</link>
<description>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 ...</description>
<pubDate>Sun, 03 Jan 2010 11:21:33 MST</pubDate>
<language>en</language>
<item>
<title>Comment #181</title>
<link>http://commoninterview.com/interview_puzzles/lonely-knight-1/#c181</link>
<pubDate>Wed, 14 Jul 2010 22:40:21 MDT</pubDate>
<dc:creator>CMaster</dc:creator>
<guid isPermaLink='false'>181</guid>
<description><![CDATA[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. <br/>0 Vote(s) ]]></description>
</item>

<item>
<title>Comment #37</title>
<link>http://commoninterview.com/interview_puzzles/lonely-knight-1/#c37</link>
<pubDate>Wed, 27 Jan 2010 09:07:49 MST</pubDate>
<dc:creator>lrreiche</dc:creator>
<guid isPermaLink='false'>37</guid>
<description><![CDATA[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.<br/>0 Vote(s) ]]></description>
</item>

<item>
<title>Comment #21</title>
<link>http://commoninterview.com/interview_puzzles/lonely-knight-1/#c21</link>
<pubDate>Sun, 24 Jan 2010 22:49:33 MST</pubDate>
<dc:creator>jane</dc:creator>
<guid isPermaLink='false'>21</guid>
<description><![CDATA[Hmm.. I don't think it will yield to "minimum number of moves" required by the problem definition. But I might be wrong.<br/>0 Vote(s) ]]></description>
</item>

<item>
<title>Comment #20</title>
<link>http://commoninterview.com/interview_puzzles/lonely-knight-1/#c20</link>
<pubDate>Sun, 24 Jan 2010 00:57:11 MST</pubDate>
<dc:creator>lrreiche</dc:creator>
<guid isPermaLink='false'>20</guid>
<description><![CDATA[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<br/>2 Vote(s) ]]></description>
</item>

</channel>
</rss>

