Path Counting
 

I have just watched:
[URL]https://www.khanacademy.org/math/recreational-math/puzzles/brain-teasers/v/path-counting-brain-teaser[/URL]
This made me think what would happen of you removed the restriction to down and right. Could you use a similar method?
The method would have to be modified quite a bit. A special method of dealing with the possibility of getting trapped would be needed.
Can anyone come up with an efficient way of solving this problem?

[QUOTE=henryzz;383068]I have just watched:
[URL]https://www.khanacademy.org/math/recreational-math/puzzles/brain-teasers/v/path-counting-brain-teaser[/URL]
This made me think what would happen of you removed the restriction to down and right. Could you use a similar method?
The method would have to be modified quite a bit. A special method of dealing with the possibility of getting trapped would be needed.
Can anyone come up with an efficient way of solving this problem?[/QUOTE]

The first step is defining your new puzzle. For example, am I permitted to go back to the square I just left an unlimited number of times? Does your removal make diagonal moves possible? How about chess-knight moves?

Version 1: You can go in any direction, without crossing, without visiting the same square two times. No diagonal moves allowed (you still can go only left, right, up, down, like a chess rook, and only one square at a time). This makes a nice puzzle in itself. You are allowed (if you like) to make distinction between odd and even sized boards.

(edit: I just got the badge for 20 minutes of video watched totally, since I am member there, hahaha)

You may move left, right, up, down. No diagonals. You can't revisit squares you have already touched.

[code]
2x2: [spoiler] ......... 2[/spoiler]
3x3: [spoiler] ........ 12[/spoiler]
4x4: [spoiler] ....... 184[/spoiler]
5x5: [spoiler] ...... 8512[/spoiler]
6x6: [spoiler] ... 1262816[/spoiler]
[/code]
I assume path must starts at upper left corner and end at lower right corner.

[QUOTE=cuBerBruce;383096][code]
2x2: [spoiler] ......... 2[/spoiler]
3x3: [spoiler] ........ 12[/spoiler]
4x4: [spoiler] ....... 184[/spoiler]
5x5: [spoiler] ...... 8512[/spoiler]
6x6: [spoiler] ... 1262816[/spoiler]
[/code]I assume path must starts at upper left corner and end at lower right corner.[/QUOTE]
How did you come by those numbers? Can your method easily scale to 20x20 etc?

This is closely related to one of the fundamental problems of molecular biology: aligning DNA or protein sequences can be thought of as making a checkerboard with one sequence across the top and the other sequence down the left side. Then an alignment between the two sequences is a path that only goes in horizontal, vertical or diagonal steps from the top left to the bottom right.

If each such move has a score, finding the highest-scoring such path is very useful. It's even more useful to find all of the highest-scoring isolated paths somewhere inside the checkerboard. This turns out not to be easy given the number of paths to check; the Smith-Waterman and Needleman-Wunsch algorithms solve the sequence alignment problem via dynamic programming in a number of steps that's only quadratic in the sequences sizes. You can probably count the number of paths in the same way.

Believe it or not, this used to be my job :)

You can also represent the alignment problem as a graph, and the generalized problem you're considering would mean dealing a directed graph. Maybe use breadth-first search to do the counting?

[QUOTE=henryzz;383098]How did you come by those numbers? Can your method easily scale to 20x20 etc?[/QUOTE]

I wrote a brute force recursive algorithm using GAP. I'm trying 7x7 now, and its taking awhile. So far it's only tried { right, right } for the first two moves. As coded, I suspect 7x7 may be the practical limit.

It could probably made much more efficient, especially if recoded carefully in C, but the number of paths increases so rapidly with increase grid size, I doubt this brute force approach would be useful for much larger than 7x7.

[QUOTE=cuBerBruce;383102]I wrote a brute force recursive algorithm using GAP. I'm trying 7x7 now, and its taking awhile.[/QUOTE]

It finished. The value I got was [spoiler]575780564[/spoiler].

[SPOILER][url]http://oeis.org/A007764[/url][/SPOILER]

[YOUTUBE]Q4gTV4r0zRs[/YOUTUBE]
(using edges is like using a (n+1)*(n+1) board)