Knight Paths
Find the number of all paths of shortest possible length that a knight on a chessboard can use to go from the lower left corner to the upper right corner.
A chessboard is a square grid of 8 × 8 .
Details and assumptions
At each step of the path, a knight is allowed to move two squares in one of the four directions (up, down, right or left) and one square in the perpendicular direction. So, for example, it can go two squares to the right and one square up, or two squares to the right and one square down, or two squares up and one square to the left (or right), and so on. Of course, after each move, the knight has to stay on the chessboard (which is a square grid of size 8-by-8).
The answer is 108.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
5 solutions
Wowowowow!!! Recursion is really powerful... works like magic. Nice solution and very well explained.
A very elegant use of recursion!
This is a perfect example for applying Haskell 's list monad to simulate nondeterministic choice.
-- is a coordinate location on the board?
onBoard (x,y) = 1 <= x && x <= 8 && 1 <= y && y <= 8
-- generate knight moves from a location
-- there are more programmatic ways to do so, but they probably aren't worth the effort
knight (x,y) = [
(x+1, y+2),
(x+1, y-2),
(x-1, y+2),
(x-1, y-2),
(x+2, y+1),
(x+2, y-1),
(x-2, y+1),
(x-2, y-1)]
-- generate valid knight moves from a location
knightOnBoard loc = filter onBoard $ knight loc
-- move nondeterministically, find number of ways we can get to (8,8), get the first number that isn't 0
main = print $ head $ dropWhile (== 0) $ map (length . filter (== (8,8))) $ iterate (>>= knightOnBoard) [(1,1)]
You can also define a monad similar to the list monad and probability monad where each element has an associated number (in this case it would be the number of paths to a given square) which would speed things up and be cleaner. The type would be [(a, Int)] but you can do it for [(a, m)] where m is any monoid. Annoyingly, you can't really define it in Haskell, since you want to define
join :: (Monoid m) => [([(a, m)], m)] -> [(a, m)]
that behaves like in this example
join [([("x", 1), ("y", 2)], 1), ([("x", 3), ("y", 4)], 5)]
== [("x", 5 * 3 + 1 * 1), ("y", 5 * 4 + 1 * 2)]
== [("x", 16), ("y", 22)]
but doing this requires that a is an instance of Eq, which doesn't make it a proper monad.
Log in to reply
Actually, m should be a semiring since you also need multiplication.
Can I ask what kind of language you used there? It looks neat and tidy.
Log in to reply
Haskell ...
We use dynamic programming to calculate the minimum distance (best), and the number of ways(dp).
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
int dp[8][8],best[8][8];
int dr[] = {-2,-2,-1,-1,1,1,2,2};
int dc[] = {-1,1,-2,2,-2,2,-1,1};
memset(best,-1,sizeof best);
memset(dp,0,sizeof dp);
best[0][0] = 0; dp[0][0] = 1;
for(int mov = 1;mov <= 64;++mov){
for(int i = 0;i < 8;++i)
for(int j = 0;j < 8;++j){
if(best[i][j] == mov - 1){
for(int k = 0;k < 8;++k){
int r = i + dr[k],c = j + dc[k];
if(r >= 0 && r < 8 && c >= 0 && c < 8 && (best[r][c] == -1 || best[r][c] == mov)){
best[r][c] = mov;
dp[r][c] += dp[i][j];
}
}
}
}
}
printf("%d %d\n",best[7][7],dp[7][7]);
return 0;
}
Solved in Java. Got pretty crazy with for-loops in the debugging, but I finally got it. The code given assumes that the minimum move number is 6. This can be checked by adjusting the code for the assumption that the maximum number is 5 and then running the code to get the result of zero. Additionally, the code has the convenience of not only showing the number of move combinations, but also showing what those combinations are. The possible moves for the knight are indexed in the switch statement and elucidated in the comments. Anyway, here's my code:
import java.util.ArrayList;
public class KnightPath
{
public static void main(String[] args)
{
long startTime = System.currentTimeMillis();
int x = 0;
int y = 0;
int count = 0; //initializes number of paths to 0
ArrayList<Integer> moves = new ArrayList<Integer>(); //initializes moves array
for(int j = 0; j < 6; j++) //sets moves array to all zeros
{
moves.add(0);
}
for(int a = 0; a<8; a++) //loop on first move
{
for(int b = 0; b<8; b++) //loop on second move
{
for(int c = 0; c<8; c++) //loop on third move
{
for(int d = 0; d<8; d++) //loop on fourth move
{
for(int e = 0; e<8; e++) //loop on fifth move
{
for(int f = 0; f<7; f++) //loop on sixth move
{
x = 0;
y = 0;
moves.set(0,a); //resets moves array to current moves on each iteration
moves.set(1,b);
moves.set(2,c);
moves.set(3,d);
moves.set(4,e);
moves.set(5,f);
for(int i = 0; i < 6; i++)
{
switch(moves.get(i))
{
case 0: {x += 1; y += 2;} //vertUpRight();
break;
case 1: {x += 2; y += 1;} //horUpRight();
break;
case 2: {x += 2; y -= 1;} //horDownRight();
break;
case 3: {x += 1; y -= 2;} //vertDownRight();
break;
case 4: {x -= 1; y -= 2;} //vertDownLeft();
break;
case 5: {x -= 2; y -= 1;} //horDownLeft();
break;
case 6: {x -= 2; y += 1;} //horUpLeft();
break;
case 7: {x -= 1; y+= 2;} //vertUpLeft();
break;
}
if ((x < 0) || (y < 0) || (x > 7) || (y > 7))
{
break;
}
if ((x == 7) && (y == 7))
{
count++;
System.out.println("Count upped: " + moves);
break;
}
}
}
}
}
}
}
}
System.out.println("Paths: " + count);
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("Runtime: "+ elapsedTime + " ms");
}
}
With the output(many results omitted for space reasons):
Count upped: [0, 0, 0, 1, 3, 0]
Count upped: [0, 0, 0, 3, 0, 1]
...
Count upped: [1, 7, 2, 0, 1, 0]
Count upped: [1, 7, 2, 1, 0, 0]
Paths: 108
Runtime: 205 ms
Get number of paths by C# in the following function:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 |
|
First, I realized that the knight had to move 14 squares, so at least 5 moves are needed. However, 1 square would be unused, which is not possible. Then, I made a path with 6 moves, so 6 is the minimum length. To program this, you can just repeat my program for 5 as well, and get 0, and then try 6.
I use dynamic programming/recursion, and define a function f ( x , y , m ) on a position and the number of moves left. If the position is off the board, I return 0. If the number of moves is 0, and the position is the correct end position, I return 1, otherwise I return 0. Finally, if none of the previous conditions were satisfied, the knight must be somewhere in the middle of the board with moves left, and I return, with a list comprehension, the sum of the result when the function is called on every position that can be reached and with 1 less move.
Python code:
At the end, I print the function called on the starting corner with 6 moves, which returns 1 0 8 .