Let G be a rectangular grid of unit squares with 3 rows and 8 columns. How many self-avoiding walks are there from the bottom left square of G to the top left square of G?
Brilliant qn! hint for you : use recursion
To find the number of self-avoiding walks from the bottom left square to the top left square of the given rectangular grid, we can use a technique called dynamic programming.
First, let's define the state of a square in the grid as the number of self-avoiding walks to that square. We start by initializing the state of the bottom left square as 1 (since there is only one way to reach the starting square).
Next, we can calculate the state of each square in the grid by summing up the states of its adjacent squares that have already been calculated. Since a self-avoiding walk cannot visit the same square twice, we only need to consider the squares to the right, above, and diagonally up-right of the current square.
To illustrate this, let's create an auxiliary matrix (let's call it "dp") with dimensions 3x8 to store the states of each square. We initialize this matrix with all zeros.
Starting from the bottom left square, we iterate through each square in the grid row by row, left to right. At each square, we calculate its state by summing up the states of the adjacent squares as described above.
After iterating through all the squares, the final state (number of self-avoiding walks) of the top left square will be the answer to our problem.
Here's the step-by-step process:
1. Create a 3x8 matrix called "dp" and initialize it with all zeros.
2. Set dp[0][0] = 1 (since the bottom left square is our starting point).
3. Iterate through each square in the grid row by row, left to right:
- For each square, calculate its state by summing up the states of its adjacent squares:
- dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], where i is the row index and j is the column index.
4. The final state (number of self-avoiding walks) of the top left square (dp[2][0]) will be the answer to our problem.
By following this approach, we can calculate the number of self-avoiding walks from the bottom left square to the top left square of the given rectangular grid.