Author |
Topic: All paths in Chess Board (Read 4057 times) |
|
ashmish2
Newbie
Posts: 12
|
 |
All paths in Chess Board
« on: Nov 15th, 2011, 8:19am » |
 Quote  Modify
|
You have to find all paths from left upper corner to right lower corner in N*N chess board where
only either 1 step right or 1 step downward is allowed.
How to find all the paths possible
|
| « Last Edit: Nov 15th, 2011, 8:23pm by ashmish2 » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: All paths in Chess Board
« Reply #1 on: Nov 15th, 2011, 8:48am » |
Quote Modify
|
There are N-1 steps lefts, N-1 steps down and every combination of these gives a different path. So it's equal to the number of 2N-2 bit integers with exactly N-1 ones. So it's the coefficient of xN-1 in (x+1)2N-2. (Which can of course be simplified further.)
|
| « Last Edit: Nov 15th, 2011, 8:49am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: All paths in Chess Board
« Reply #2 on: Nov 15th, 2011, 12:51pm » |
Quote Modify
|
Hi Towr,
Could it be that you answered a different question?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: All paths in Chess Board
« Reply #3 on: Nov 15th, 2011, 1:21pm » |
Quote Modify
|
I think technically I haven't answered the question but just given some alternatives with the same answer.
At least, if the question is to give the number of paths, rather than all paths. (And assuming that we start in the upper right corner, because we can't go left if we start in the upper left corner.)
* Say you have a 3x3 board, then you can go LLDD, LDLD, LDDL, DDLL, DLDL, DLLD, so the number of paths is 6
* You could write 1 and 0 instead of L and D, 1100,1010,1001,0011,0101,0110
* (x+1)6-2 = (x+1)4 = x4+4 x3+6 x2+4 x+1, the coefficient of x3-1 = x2 in that expression is 6.
*It's also the middle number in the (2n-1)st row of Pascal's triangle.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
This is not coincidental (for example you'll recognize the other coefficients of (x+1)4 in that last row)
|
| « Last Edit: Nov 15th, 2011, 1:30pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ashmish2
Newbie
Posts: 12
|
|
Re: All paths in Chess Board
« Reply #4 on: Nov 15th, 2011, 8:23pm » |
Quote Modify
|
Hi Towr, Sry i said 1 step left
actually it is 1 step right and 1 step down (can never reach lower right with 1 step right)
Basically, we want to go to diagonally opposite corner and only 2 kind of movements towards the other corner i.e to go from upper left to lower right only 1 step right and 1 step down is allowed
Answer you gave gave is to find total number of different paths possible not all the paths.
we can take different combination for n-1 right and n-1 down step to get the answer but i am looking for an efficient answer if possible
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: All paths in Chess Board
« Reply #5 on: Nov 15th, 2011, 10:10pm » |
Quote Modify
|
on Nov 15th, 2011, 8:23pm, ashmish2 wrote:| Answer you gave gave is to find total number of different paths possible not all the paths. |
|
I'm not sure I understand; for example what answer would you want for N=3 if not 6?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ashmish2
Newbie
Posts: 12
|
|
Re: All paths in Chess Board
« Reply #6 on: Nov 16th, 2011, 12:52am » |
Quote Modify
|
What you gave is total number of paths possible not the actual paths.
I want for N=3 all the paths i.e
LLLDDD, LLDLDD etc..
this can be done by taking different combinations for n-1 Left and n-1 Down which is O(n2). I want some other efficient solution if possible.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: All paths in Chess Board
« Reply #7 on: Nov 16th, 2011, 1:07am » |
Quote Modify
|
something like this:
void generateAll(int n){
generate("", n, n);
}
void generate(String prefix, int m, int n){
if( m==0 && n==0 ) System.out.println(prefix);
if( m>0 ) generate(prefix+"D", m-1, n);
if( n>0 ) generate(prefix+"R", m, n-1);
}
|
| « Last Edit: Nov 16th, 2011, 1:09am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: All paths in Chess Board
« Reply #8 on: Nov 16th, 2011, 10:06pm » |
Quote Modify
|
on Nov 16th, 2011, 12:52am, ashmish2 wrote:| this can be done by taking different combinations for n-1 Left and n-1 Down which is O(n2). I want some other efficient solution if possible. |
|
Err, there are (2n-2)!/(n-1)!^2 paths, you can't get those efficiently, let alone in O(n^2)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: All paths in Chess Board
« Reply #9 on: Nov 28th, 2011, 11:42pm » |
Quote Modify
|
Agreed with towr except that there are N steps lefts, N steps down, so its 2N! / (n!)^2 . or am i missing something trivial?
|
| « Last Edit: Nov 28th, 2011, 11:43pm by kaka » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: All paths in Chess Board
« Reply #10 on: Nov 29th, 2011, 8:30am » |
Quote Modify
|
I'm assuming you start on a square on the board, moving from square to square; so if for example N=1, then the starting square is the end square is the only square, so you can't go left or down.
Another possible interpretation would be to move along the sides of the squares from cross-point to cross-point, and then you can do one more step left and down.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print