Author |
Topic: Chess puzzle - the Queen (Read 1741 times) |
|
Christine
Full Member
Posts: 159
|
 |
Chess puzzle - the Queen
« on: Jul 29th, 2015, 12:12am » |
 Quote  Modify
|
Using Queen legal moves, how many pathways from a-1 to h-8. No block can be visited twice in same transit.
|
|
 IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Chess puzzle - the Queen
« Reply #1 on: Jul 29th, 2015, 11:30am » |
Quote Modify
|
1). When you say "block" - you actually mean "square" - a smallest legal area unit on a chessboard?
2). Is there a "shortest possible path" constraint on the Queen's moves?
In other words, assuming that the "a" corner is at the bottom left (south-west) and that the "h" corner is at the top right (north-east), is the Queen restricted to always move only East or North or North-East? Or. Can she also move in all the other cardinal directions (modulo visiting the same square more than once)?
For example. With the N, E, NE restriction the paths to a 2x2 corner b2 are:
1) N, E
2) E, N
3) NE
while without the restriction they are also:
4) E, NW, E
5) N, SE, N
Please clarify. Thanks.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Chess puzzle - the Queen
« Reply #2 on: Jul 29th, 2015, 1:02pm » |
Quote Modify
|
1) For the shortest possible path version I get 48,639 paths (though it's quite possible I've fat fingered something).
Logic: simple arithmetic brute force. Into every square of the board we put down the total number of paths it takes to get from that square to "a1" (using a sort of reverse travel approach). Obviously for the very bottom row and the very left column of the entire board these numbers will be just ones.
For the next 7x7 square its bottom row and leftmost column are the odds: 3, 5, 7, 9, 11, 13, 15.
For the main diagonal "c3" it is a sum of the paths at "c2" (5), "b3" (5) and "b2" (3): 5 + 5 + 3 = 13. That, I take it, becomes the rule to fill out the rest of the squares - (immediate) South + West + South-West. The result should be a sort of triangular matrix symmetric about its main diagonal "a1-h8":
1, 15, 113, 575, 2241, 7183, 19825, 48639
1, 13, 85, 377, 1289, 3653, 8989, 19825
1, 11, 61, 231, 681, 1683, 3653, 7183
1, 9, 41, 129, 321, 681, 1289, 2241
1, 7, 25, 63, 129, 231, 377, 575
1, 5, 13, 25, 41, 61, 85, 113
1, 3, 5, 7, 9, 11, 13, 15
a, 1, 1, 1, 1, 1, 1, 1
Please double check.
Note the numbers on the main diagonal, rows and columns - must be some sort of sequences. Not sure what is going on here. But now on to an analytic solution.
[e]
This matrix is called symmetric since it is equal to its rows-and-columns-swapped transposed version: A = AT
[/e]
|
| « Last Edit: Jul 30th, 2015, 11:59am by rloginunix » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Chess puzzle - the Queen
« Reply #3 on: Jul 29th, 2015, 1:54pm » |
Quote Modify
|
For example, we can easily pick the sequence for the "c" column or the "3" row as a sum of two consecutive squares:
cn = (n - 1)2 + n2
[e]
The method of finite differences works for the "d" column or "4" row:
1 7 25 63 129 231 377 575
6 18 38 66 102 146 198
12 20 28 36 44 52
8 8 8 8 8
a third degree polynomial dn = (4/3)n3 - 2n2 + (8/3)n - 1
[/e]
[e2]
The method of finite differences also works for the "e" column or "5" row:
1 9 41 129 321 681 1289 2241
8 32 88 192 360 608 952
24 56 104 168 248 344
32 48 64 80 96
16 16 16 16
a fourth degree polynomial, etc.
So the conjecture now is that the power will grow by one as we move East-bound. The numbers in the last column "h" then should form a 7-th degree polynomial.
[/e2]
|
| « Last Edit: Jul 30th, 2015, 12:30pm by rloginunix » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print