Chessboard Steps
Starting at the bottom left-hand corner of a chessboard, how many different ways are there of moving to the top right-hand comer if
(a) You can move only one square at a time and
(b) You can move bottom to top or left to right or a diagonal combination of the two?
(a) You can move only one square at a time and
(b) You can move bottom to top or left to right or a diagonal combination of the two?
Labels: mathschallenge
posted by Rajesh Lal at
7:42 AM
54 Comments:
When you say "How many different ways".. i'm assuming that means how many unique paths..
I'm not sure yet, but I'm going say 512 as a guess.. that's 8^3.
(1+2+3+4+5+6+7+8)*8*2=592
3432. It's Pascal's Triangle down to the eighth row.
well, my brother is the real mathmatition in the family.. but I don't see what 3432 has to do with the 8th row of Pascal's triangle...
i see 3432 as the center coefficient further down the triangle on row 16 (17th from the top). But don't see how it relates to this..
Well.. i believe all the above are wrong.. Not counting the diagonal moves, I get 40320 unique pathways.
that's 8!
I did it manually up to 4x4 square (which has 24 paths).
I found many more unique paths.
45,968
I labeled the path with U, R, and D
for up, right, diagonal.
Of course the shortest path is 7 D's
Many of you are saying 8, but you forgot you begin a row 1.
The table below says there 1 way using seven moves, 7 D'
There are 56 ways with 8 moves.
# moves....How many Example
7...........1........DDDDDDD
8..........56........DDDDDDRU
9.........756........DDDDDRRUU
10.......4200........DDDDRRRUUU
11......11543........DDDRRRRUUUU
12......16266........DDRRRRRUUUUU
13......10733........DRRRRRRUUUUUU
14.......2413........RRRRRRRUUUUUUU
I can list the unique 45,968 ways if someone wants a long email.
I was going to list this as the first post, but I thought I would see what others thought.
What about the L moves?
I guess that you mustn't revisit any square on a given path (e.g. can't do L then R).
Below are the moves that required 8 moves....56 of them.
The numbers following each move shows the square you would be on after the move. You start on square 1, moving up puts you on #9, a diagonal, to 10, Right puts you on square #2.
moves-----1----2----3-----4----5---6----7-----8
-----------------------------------------------
DDDDDDRU—--10---19---28---37---46---55---56---64
DDDDDDUR---10---19---28---37---46---55---63---64
DDDDDRDU---10---19---28---37---46---47---56---64
DDDDDRUD---10---19---28---37---46---47---55---64
DDDDDUDR---10---19---28---37---46---54---63---64
DDDDDURD---10---19---28---37---46---54---55---64
DDDDRDDU---10---19---28---37---38---47---56---64
DDDDRDUD---10---19---28---37---38---47---55---64
DDDDRUDD---10---19---28---37---38---46---55---64
DDDDUDDR---10---19---28---37---45---54---63---64
DDDDUDRD---10---19---28---37---45---54---55---64
DDDDURDD---10---19---28---37---45---46---55---64
DDDRDDDU---10---19---28---29---38---47---56---64
DDDRDDUD---10---19---28---29---38---47---55---64
DDDRDUDD---10---19---28---29---38---46---55---64
DDDRUDDD---10---19---28---29---37---46---55---64
DDDUDDDR---10---19---28---36---45---54---63---64
DDDUDDRD---10---19---28---36---45---54---55---64
DDDUDRDD---10---19---28---36---45---46---55---64
DDDURDDD---10---19---28---36---37---46---55---64
DDRDDDDU---10---19---20---29---38---47---56---64
DDRDDDUD---10---19---20---29---38---47---55---64
DDRDDUDD---10---19---20---29---38---46---55---64
DDRDUDDD---10---19---20---29---37---46---55---64
DDRUDDDD---10---19---20---28---37---46---55---64
DDUDDDDR---10---19---27---36---45---54---63---64
DDUDDDRD---10---19---27---36---45---54---55---64
DDUDDRDD---10---19---27---36---45---46---55---64
DDUDRDDD---10---19---27---36---37---46---55---64
DDURDDDD---10---19---27---28---37---46---55---64
DRDDDDDU---10---11---20---29---38---47---56---64
DRDDDDUD---10---11---20---29---38---47---55---64
DRDDDUDD---10---11---20---29---38---46---55---64
DRDDUDDD---10---11---20---29---37---46---55---64
DRDUDDDD---10---11---20---28---37---46---55---64
DRUDDDDD---10---11---19---28---37---46---55---64
DUDDDDDR---10---18---27---36---45---54---63---64
DUDDDDRD---10---18---27---36---45---54---55---64
DUDDDRDD---10---18---27---36---45---46---55---64
DUDDRDDD---10---18---27---36---37---46---55---64
DUDRDDDD---10---18---27---28---37---46---55---64
DURDDDDD---10---18---19---28---37---46---55---64
RDDDDDDU---2----11---20---29---38---47---56---64
RDDDDDUD---2----11---20---29---38---47---55---64
RDDDDUDD---2----11---20---29---38---46---55---64
RDDDUDDD---2---11---20---29---37---46---55---64
RDDUDDDD---2---11---20---28---37---46---55---64
RDUDDDDD---2---11---19---28---37---46---55---64
RUDDDDDD---2---10---19---28---37---46---55---64
UDDDDDDR---9---18---27---36---45---54---63---64
UDDDDDRD---9---18---27---36---45---54---55---64
UDDDDRDD---9---18---27---36---45---46---55---64
UDDDRDDD---9---18---27---36---37---46---55---64
UDDRDDDD---9---18---27---28---37---46---55---64
UDRDDDDD---9---18---19---28---37---46---55---64
URDDDDDD---9---10---19---28---37---46---55---64
Chris,
The diagonal IS the right and left, or maybe the left and right.
Either way, a diagonal is one step.
I sorry, you can't move left. I should have said up/right is a diagonal
I see he did say LEFT, but that would be an error, if you could move left, the answer would be infinity.
Has anyone looked on the web for an answer?
Maybe Rajesh Lal will post it if he has one.
Here's a way to check my method.
If the square is just a 4X4, then there would be 63 ways. Someone should be able to verify these.
#moves..path
------------
3 DDD
4 DUDR
4 UDDR
4 UDRD
4 URDD
4 RDDU
4 DURD
4 RDUD
4 RUDD
4 DDRU
4 DDUR
4 DRDU
4 DRUD
5 RRUUD
5 DUURR
5 RUURD
5 RUUDR
5 RURDU
5 RDRUU
5 RDUUR
5 DURUR
5 RDURU
5 UDURR
5 RUDUR
5 RUDRU
5 RRDUU
5 URRUD
5 UURRD
5 UURDR
5 UUDRR
5 DRRUU
5 DRURU
5 URURD
5 UDRRU
5 DRUUR
5 DURRU
5 URRDU
5 URDUR
5 URDRU
5 RURUD
5 UDRUR
5 RRUDU
5 URUDR
6 RUUURR
6 UURURR
6 UURRUR
6 UURRRU
6 URUURR
6 URURUR
6 URURRU
6 URRUUR
6 RURURU
6 URRRUU
6 RRRUUU
6 RUURUR
6 RUURRU
6 UUURRR
6 RURUUR
6 RURRUU
6 RRUUUR
6 RRUURU
6 RRURUU
6 URRURU
Hi Ragknot. To kill the infinity, you must assume that you are not allowed to visit a square twice on a given path. The question really should have stated that. That actually boils down to RL or LR is illegal. You don't need any other "rules", except the obvious three: L is illegal at the left edge, etc. I'm not sure if this is a hard problem or not. It certainly looks like a sheet or two of paper is needed though. I would definitely not accept the RU is the same as a right diagonal move (I'll use R' and L' for the diagonal move if I post any thoughts) even though you end on the same square. Take that idea to the logical conclusion by considering groups of three moves that end at the same place then four etc.
For a greatly simplified version of the problem, only allow R and U moves. We must have 7R and 7U moves. The order of the moves is the only variable. Consider a given path e.g. RRRRRRRUUUUUUU. In general have 14 places where we can put the first R, 13 for the second ... 8 for the 7th R. There is then no choice about where to put the 7 U moves. So there are 14!/8! = 2 162 160 even for this problem.
The posted problem is much harder. There are more variables and some awkward looking constraints. The path lengths can vary between 7 and 14 and of course to disallow moving off the board we also require that:
0 ≤ #R+#R'-#L-#L' ≤ 7 at all stages. ('=>diagonal).
... another rule: 0 ≤ #U+#R'+#L' ≤ max(7,#moves).
The previous rule should also have been:0 ≤ #R+#R'-#L-#L' ≤ max(7,#moves).
No doubt the rules can be made stronger (and possibly simpler ^^).
I've got a feeling that considering smaller chess boards and building way up to bigger ones may be a good strategy. You might guess the formula before the counting becomes impossible.
I seem to be taking a liking to combinatoric problems. Sadly, I've got more computer to fix and my extended coffee break must end.
Couldn't stay away. I just checked my simplified answer. I made an error. #paths = 14!/7! = 17 297 280. Really gotta go now.
Chris,
There should only be 3 moves that are acceptible, R, U, and D. Omit left. I counted a R, U and U, R and D as 3 distinct moves... But and RU and a UR are two moves where a D is one move.
A Left move is moving away from the goal. I think Raj made an error when talking about a left move... I think he meant UP. But he did say LEFT, but I want to assume it was an error, unless shown a better reasoning. Left might be another option, but I don't why, Just URD is hard enough for me.
I'll investigate L if Raj confirms he meant L.
I thought he should have said Checker board. Chess suggests maybe an L "Knight" move.
Just took at look at your post and re-read the question. You're right, I read it wrong. The only moves are R, U and D (D=R' in my previous posts). That makes it much easier. OK I think I'm close, so I'll delay the computer fixing and have another coffe break. Back soon.
There is no mistake in the question and the answer lies in the neighborhood of 50,000.
Thanks Rajesh. Back to the previous simplified problem, I notice that I've done permutations instead of combinations. So should have said 14!/(8!*7!) = 429 (that's seems more intuitive). I guess that Ragknot's 3:42 PM post is probably right then. Back soon.
45,968
That was my computation. And the comutation was not easy.
I don't have a nice expression, but barring errors in totting up, I get 48639.
Chris,
Do you have a way to determine how many of each path length you have?
Like there only one with 7 steps.
But 16,266 with 12 steps.
What I did is to start at the bottom left corner, then look at how many ways there are to get to each square. Keep on going and you get a sort of Pascal's triangle. But you add the number of paths from the left, backward diagonal and below square. I've padded with 0s to get the layout right.
1 15 113 575 2241 7183 19825 48639
1 13 085 377 1289 3653 08989 19825
1 11 061 231 0681 1683 03653 07183
1 09 041 129 0321 0681 01289 02241
1 07 025 063 0129 0231 00377 00575
1 05 013 025 0041 0061 00085 00113
1 03 005 007 0009 0011 00013 00015
1 01 001 001 0001 0001 00001 00001
I'll post this now. I'll see if I can find a nice expression for the table.
Chris,
Am I reading this right? Do you have 63 ways to get the 4x4?
It looks like, If so I could check the 5x5... etc.
I got 321 for a 5x5
and 1683 for a 6x6
Those seem to agree with your table.
BUT, I got 8986 for a 7x7 and you have 8989... 3 more. I'll check mine again.
Chris,
I got 8989 this time, so your on my same calcuation at 7x7!
Wow, that make me nervous about my 8x8.
I did a Google with "48639 chess" and came across a paper that showed the expression corresponding to the "squared" Pascal's triangle is:
g(n,r) = Sum[a=0 to r, 2^a * c(n,a) * c(r,a)]
where c(a,b)=a!/((b-a)!b!)
The result we want is g(7,7)=48639
The link to the paper is:
http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pjm/1102913231
Here's my Mathematica code and output (going to 9*9 board):
For[n = 0, n < 9, n++,
Print[Table[
Sum[2^a Binomial[n, a] Binomial[r, a], {a, 0, n}], {r, 0, n}]]]
{1}
{1,3}
{1,5,13}
{1,7,25,63}
{1,9,41,129,321}
{1,11,61,231,681,1683}
{1,13,85,377,1289,3653,8989}
{1,15,113,575,2241,7183,19825,48639}
{1,17,145,833,3649,13073,40081,108545,265729}
Hi Ragknot. That's weird that your code failed like that. Goodnight.
PS for a 42*42 board (and why not?) board, the answer is:
2 177 132 498 065 215 626 644 755 632 547
that's 2.17713*10^30 approx.
I still get 45,968, and when I review your numbers I see something strange.
When you get closer to the last square (at upper right, my square 64). The number of possible numbers decrease dramatically, but the method does not seem to do that. Like when you get to square 55, there only 3 possible moves.
I am not convinced that your method is right.
Hi EB. For an (n+1)*(n+1) chessboard the Pascal's triangle solution (which is correct if don't do diagonal moves) is c(2n,n)=(2n)!/(n!)². For n+1=8 => n=7, you get 14!/(7!)²=3432. It's a bit weird as you count from 0, not 1.
I read one of the articles, and they are using and 8x8 board, which is right, but they use 8 in the equation, and there's only 7 up and 7 to the right.
Until some can show me a string of U,R, and D that I missed, I'll stick to my answer.
This post has been removed by the author.
Hi Ragknot. The table I did is better than what you're asking for. Just go over it and see that each square is the number of ways to get to it using R,U and D. Once you've done a few the hard way, it'll be obvious what I've done.
Might have a delete or two as the posts seem to be getting jammed.
This post has been removed by the author.
Really doing this post in an attempt to get the posts to go through, theres's 3 or 4 stuck in cyberspace. A set of RUD etc moves would be list of 48639 items of between 7 and 14 Rs, Us and Ds. That's a very big list.
Ragknot, I've just seen that you're casting aspersions on my table. I'm confident that it's right. Really that's just an excuse to try to kick the post through :)
I didn't realize moving diagonally was one step. In that case the answer is indeed 48639, and using a kind of Pascal's Triangle is still the easiest way to get to it.
Imagine you have a 2x2 board. There are 3 paths to the top right. Now imagine you have a 2x3 board. There are 3 fields you can go on the first step: one of then is the one where you had 3 possible paths, from the other two there is only 1 possible path each. So on that board, there are 1+1+3=5 possible paths. On a 3x3 board, there are 3+5+5=13 possible paths, etc, etc. As I said, it's a kind of Pascal's Triangle.
wooooooooooooooooooowwww,,
i have never seen soo many answers in a span of 26 hrs!!!!!!!!!
Oh btw about the question.....i have no idea :P
Well, I am going to have to learn Pascal's Triangle and see what I am missing. I am still not convinced until I find out I made an err.
Mo, thanks for your explanation. I was surprised that you'd not got it right at first. I've seen some other responses of yours - clearly you're on the ball. I readily accept that you misread the question, I certainly did - but with hindsight I don't really understand why. I guess I read it too fast and jumped to conclusions.
Ragknot, mo has provided a good explanation of how to create the modified Pascal's triangle. You don't need to study it up theoretically. I had no idea that I was going in that territory when I started counting the paths to every square. It wasn't until I had started the second row, that I saw the algorithm to generate all the path counts. It also wasn't until I had the number 48639 that I tried a spot of Googling. But other than finding someone else having got the result, the most interesting result was the summation over combinations formula. I was pleased to see that as it was easy to bung it into Mathematica. I've even calculated the result for a 10000*10000 chess board: 3.206898813*10^7652 (approx), but it took 5 seconds. A 1000*1000 board gives 1.1063658761*10^763 (approx) but only took the blink of an eye to do.
Armed with confidence, I tried a table when also allow a left and a left diagonal, but got into a mess very quickly. I might give it another shot tonight. But suspect that I won't find a nice formula and will give up as I don't like really hard work.
Aaarrghh, I am so clumsy. My post OCT 5 7:11 PM should have said 14!/((14-7)! 7!) = 14!/(7!)² = 3432 (and not the 429 that I gave).
The numbers in these types of problems are known as Delannoy numbers. No-one seems to be calling the pattern Dellanoy's triangle though. After a bit of trawling via Google, I'm now certain that 48639 is the correct answer.
Hi Ragknot. Just to cover an comment of yours; except for the left column and bottom row, all the numbers are the sum of the three numbers from the immediate below, left below diagonal and the left of a given square. I expect that you've realised that long ago.
Chris,
I've been working all day, and I see Ive missed a lot of post.
I see a problem, I under estimated the combinations ... this will bring back memories... With 3 possible movements (URD) and 14 places... base 3 with 14 places gives 4,782,969. I had looked for combinations of URD but I had only looked to 3 million, so there quite a few combinations at 14 places I missed.
Out of the 4,782,969 combinations
I found 3432 that added up to 64, and I had only 2413 before. I found a few others in slots less than 14.
7.......1
8.......56
9.......756
10......4200
11......11550
12......16632
13......12012
14......3432
Total.. 48,639
I salute your skills.
Wow, 50 comment!
I'll credit for getting Chris excited enough to keep kicking posts thru one after the other.
Hi Ragknot. Remember me, the man who hates combinatoric problems ;) The trouble is, once I've got a bite on, I won't let go easily. I'm pleased to see you got there. I assumed that you'd only written a program and wasn't doing it with lots of manual intervention.
I just noticed you're doing the bases stuff again. Bases are just about how to write definite numbers; they are not what I regard as having any true mathematical significance. I usually only use other bases (2 and 16) when writing in assmbly language,and even then only when it is especially convenient or tidy to do so. Otherwise it's base 10 for everything.
I'm impressed by your doggedness. I don't think I'd like to have done it your way though - mainly because by the time I'd decided what the agorithm had to do, I'd have knocked up the answer (not sure what I'd have done if chessboards were only a little bigger than 8*8.
Also happy to see mo's contributions. He seems very bright to me. He got that "What is X?" problem when everyone else (including me) had given up. Plus several other things. Enough of my witterings.
Chris,
I was working on the combinations of "URD". At first I looked at one million combinations within a 14 digit string. I learned that was not enough, so I went to 3 million, and thought I had them all. But I should have thought about 3 symbols and 14 places. That's what I did with the stargate deal. Using base 3 at 14 places is 3^14 = 4 million plus.
Using base 3 and 14 places gave me the necessary strings to finish all the combinations.
I had a very efficient way to find the true paths from cell 1 to cell 64. I just added the strings where U was 8 points, R was worth 1 point and D was 9 points. At any point the total was 64, I had a true path. Any other result was tossed away. Finally I was left with 48,639 strings that added to 64. It was brute force to the max, but I was stopping a 3 million, and missed strings above 3 million.
I should have used 3^14 = 4,782,969
but I didn't think it through.
Hi Ragknot. I see you're now using the word base in an OK way. I've been going on about it possibly under a misunderstanding from the stargate problem. I thought you were talking about base b number notation, rather the base of an exponential term.
I tried an approach starting from the case without a U move, and tried to build it in afterwards. I found it very difficult to keep a track of all the permutations. I wasn't surprised about my difficulty after I seeing the g(n,r) summation formula that I mentioned in an earlier post.
Then I realised that I only needed to work out how many ways there were to get to a given square and that all such combinatoric difficulties disappeared as there were no strange interdependencies involved.
I'm abandoning the idea of solving the more general problem with the leftward moves added.
Post a Comment
Links to this post:
Create a Link
<< Home