20140915, 10:00  #1 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5818_{10} Posts 
Path Counting
I have just watched:
https://www.khanacademy.org/math/rec...gbrainteaser 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? 
20140915, 11:46  #2  
"William"
May 2003
New Haven
3×787 Posts 
Quote:


20140915, 13:53  #3 
Romulan Interpreter
Jun 2011
Thailand
2^{3}·19·61 Posts 
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) Last fiddled with by LaurV on 20140915 at 13:55 
20140915, 15:59  #4 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·2,909 Posts 
You may move left, right, up, down. No diagonals. You can't revisit squares you have already touched.

20140915, 17:02  #5 
Aug 2012
Mass., USA
2×3×53 Posts 
Code:
2x2: ......... 2 3x3: ........ 12 4x4: ....... 184 5x5: ...... 8512 6x6: ... 1262816 
20140915, 17:25  #6 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×2,909 Posts 

20140915, 17:38  #7 
Tribal Bullet
Oct 2004
2×3×19×31 Posts 
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 highestscoring such path is very useful. It's even more useful to find all of the highestscoring isolated paths somewhere inside the checkerboard. This turns out not to be easy given the number of paths to check; the SmithWaterman and NeedlemanWunsch 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 breadthfirst search to do the counting? Last fiddled with by jasonp on 20140915 at 17:46 
20140915, 18:09  #8  
Aug 2012
Mass., USA
2·3·53 Posts 
Quote:
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. 

20140915, 23:10  #9 
Aug 2012
Mass., USA
476_{8} Posts 

20140915, 23:12  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×3,109 Posts 
[url]http://oeis.org/A007764[/url]

20140915, 23:19  #11 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·3,109 Posts 
(using edges is like using a (n+1)*(n+1) board) 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A counting problem  jasonp  Puzzles  1  20171224 19:38 
The Fastest Path  a1call  Puzzles  23  20160323 17:46 
Best settings and upgrade path for i72600  emily  Hardware  20  20120302 08:45 
Expected Path Length  davar55  Puzzles  12  20080226 21:53 
Are you in the path of Isabel  jocelynl  Soap Box  14  20030922 20:38 