The discussion revolves around calculating the number of paths from point (1,1) to point (10,10) in a 10x10 grid, considering various movement options and constraints. Participants explore different approaches to the problem, including combinatorial methods and programming solutions, while addressing the implications of path length and grid wrapping.
Participants express various hypotheses and methods for calculating paths, but there is no consensus on a definitive answer or approach. Multiple competing views and uncertainties remain throughout the discussion.
Participants note limitations regarding the definition of path length and the constraints of the grid, particularly the implications of path wrapping and self-avoidance. The complexity of the problem increases significantly with larger grids, making exact calculations challenging.
Bartholomew said:
No; the path may not retrace itself, and it is limited to a 10x10 grid. There are no paths of 100 steps, for example, because there are only 100 squares total and since you start on one of them, only 99 are available as endpoints of steps.Problem+Solve=Reason said:
// size is the maximum coordinate value allowed, and is one less than you'd think - so 7 for a chessboard
#define SIZE 6
unsigned char grid[SIZE + 1][SIZE + 1];
unsigned long solutions;
void move(int x, int y, unsigned char n)
{
grid[x][y] = n;
if ((x == SIZE) && (y == SIZE))
solutions++;
else
{
if ((x < SIZE) && (grid[x + 1][y] == 0)) // look right
move(x + 1, y, n + 1);
if ((x > 0) && (grid[x - 1][y] == 0)) // look left
move(x - 1, y, n + 1);
if ((y < SIZE) && (grid[x][y + 1] == 0)) //look up
move(x, y + 1, n + 1);
if ((y > 0) && (grid[x][y - 1] == 0)) // look down
move(x, y - 1, n + 1);
}
grid[x][y] = 0;
}
int main(int argc, char* argv[])
{
int x, y;
for (y = 0; y <= SIZE; y++)
for (x = 0; x <= SIZE; x++)
grid[x][y] = 0;
solutions = 0L;
grid[0][0] = 1;
move(0, 1, 2);
printf("%lu solutions\n", solutions * 2);
return 0;
}