I know I have drawn the picture badly but can you tell how many ways we can go from point A to point B.
each path used once and no turning back...
Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this communityI know I have drawn the picture badly but can you tell how many ways we can go from point A to point B.
each path used once and no turning back...
Assuming we can go only right and/or up, my answer is (as @SayedMohdAli's answer)
321
which was produced by this C code
#include <stdio.h>
#define MINGRID 2
#define MAXGRID 7
int grid;
int paths;
void recur(int x, int y)
{
if(x == grid - 1 && y == grid - 1) {
paths++;
}
else if(x < grid && y < grid) {
recur(x + 1, y);
recur(x, y + 1);
recur(x + 1, y + 1);
}
}
int main(void)
{
for(grid = MINGRID; grid <= MAXGRID; grid++) {
paths = 0;
recur(0, 0);
printf(">! grid=%d paths=%d \n", grid, paths);
}
}
along with solutions for other sized grids:
grid=2 paths=3
grid=3 paths=13
grid=4 paths=63
grid=5 paths=321
grid=6 paths=1683
grid=7 paths=8989
and OEIS has this sequence A001850.
Central Delannoy numbers
3,13,63,321,1683,8989
Number of paths from (0,0) to (n,n) in an n X n grid using only steps north, northeast and east (i.e., steps (1,0), (1,1), and (0,1))
although I didn't look it up first!
There doesn't seem to be a clear and simple formula for it.
In a crude mathematical induction applied, I can
move in 3 ways, if there is one square, 31( 9{diagonally} + 11{lateral)} + 11{lateral}) ways, if there are 4 squares ... and so on...
And hence with
16 squares, it is 2^17 - 1 ways