wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Chess puzzle - the Queen
        
(Message started by: Christine on Jul 29^th, 2015, 12:12am)

Title: Chess puzzle - the Queen
Post by Christine on Jul 29^th, 2015, 12:12am

Using Queen legal moves, how many pathways from a-1 to h-8. No block can be visited twice in same transit.

Title: Re: Chess puzzle - the Queen
Post by rloginunix on Jul 29^th, 2015, 11:30am

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.

Title: Re: Chess puzzle - the Queen
Post by rloginunix on Jul 29^th, 2015, 1:02pm

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 = A^T
[/e]

Title: Re: Chess puzzle - the Queen
Post by rloginunix on Jul 29^th, 2015, 1:54pm

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)² + n²

[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³ - 2n² + (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]