wu :: forums « wu :: forums - Chess puzzle - the Queen » Welcome, Guest. Please Login or Register. Apr 22nd, 2024, 1:03pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    general problem-solving / chatting / whatever (Moderators: Grimbal, SMQ, ThudnBlunder, william wu, Eigenray, towr, Icarus)    Chess puzzle - the Queen « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Chess puzzle - the Queen  (Read 1739 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ => general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board