wu :: forums
wu :: forums - Chess puzzle - the Queen

Welcome, Guest. Please Login or Register.
Mar 25th, 2023, 7:57am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   general problem-solving / chatting / whatever
(Moderators: Icarus, william wu, ThudnBlunder, Grimbal, Eigenray, SMQ, towr)
   Chess puzzle - the Queen
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Chess puzzle - the Queen  (Read 1672 times)
Christine
Full Member
***





   


Posts: 159
Chess puzzle - the Queen  
« on: Jul 29th, 2015, 12:12am »
Quote Quote Modify 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: 1026
Re: Chess puzzle - the Queen  
« Reply #1 on: Jul 29th, 2015, 11:30am »
Quote Quote Modify 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: 1026
Re: Chess puzzle - the Queen  
« Reply #2 on: Jul 29th, 2015, 1:02pm »
Quote Quote Modify 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: 1026
Re: Chess puzzle - the Queen  
« Reply #3 on: Jul 29th, 2015, 1:54pm »
Quote Quote Modify 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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