Author 
Topic: Chess puzzle  the Queen (Read 1672 times) 

Christine
Full Member
Posts: 159


Chess puzzle  the Queen
« on: Jul 29^{th}, 2015, 12:12am » 
Quote Modify

Using Queen legal moves, how many pathways from a1 to h8. No block can be visited twice in same transit.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Chess puzzle  the Queen
« Reply #1 on: Jul 29^{th}, 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 (southwest) and that the "h" corner is at the top right (northeast), is the Queen restricted to always move only East or North or NorthEast? 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: 1026


Re: Chess puzzle  the Queen
« Reply #2 on: Jul 29^{th}, 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 + SouthWest. The result should be a sort of triangular matrix symmetric about its main diagonal "a1h8": 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 rowsandcolumnsswapped transposed version: A = A^{T} [/e]

« Last Edit: Jul 30^{th}, 2015, 11:59am by rloginunix » 
IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Chess puzzle  the Queen
« Reply #3 on: Jul 29^{th}, 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: c_{n} = (n  1)^{2} + n^{2} [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 d_{n} = (4/3)n^{3}  2n^{2} + (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 Eastbound. The numbers in the last column "h" then should form a 7th degree polynomial. [/e2]

« Last Edit: Jul 30^{th}, 2015, 12:30pm by rloginunix » 
IP Logged 



