In a chess variant, a "lord" can move one space at a time, either upward, or to the right, or diagonally upward and to the right. How many ways are there for a lord to move from the bottom left to top right corner of the 8 by 8 chessboard?
its 48639
pascal triangle or somethin'
To find the number of ways for a lord to move from the bottom left to the top right corner of an 8 by 8 chessboard, we can use dynamic programming.
Let's define a 2D array, dp, with dimensions 8 by 8. Each element dp[i][j] represents the number of ways to reach the position (i, j) from the starting position (0, 0).
We can fill in this array using the following rules:
- For the first row (i.e., i = 0), since the lord can only move to the right, dp[0][j] will be 1 for all values of j.
- For the first column (i.e., j = 0), since the lord can only move upward, dp[i][0] will be 1 for all values of i.
- For the remaining positions (i, j), the number of ways to reach the position (i, j) is the sum of the number of ways to reach the position (i-1, j), (i, j-1), and (i-1, j-1) because the lord can move upward, move to the right, or move diagonally upward and to the right. Therefore, dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1].
Finally, the answer to our problem will be the value of dp[7][7] (since the indices are zero-based).
Let's calculate the number of ways:
Initialization:
dp[0][j] = 1 for j = 0 to 7
dp[i][0] = 1 for i = 0 to 7
Dynamic Programming:
for i = 1 to 7:
for j = 1 to 7:
dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]
The answer is dp[7][7].
Now you can use the above steps and perform the calculations to find the number of ways for a lord to move from the bottom left to the top right corner of the 8 by 8 chessboard.