All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Knight's Tour (3 & 4) (Posted on 2004-04-12) Difficulty: 5 of 5
Please see Knight's Tour (2) for the rules of a Knight's Tour.

A Magic Tour is a tour where, if you number each square with the corresponding knight's step, the result *is* a magic square.

A Semi-Magic Tour is a tour where, if you number each square with the corresponding knight's step, the result *is* a semimagic square.

(A magic square, as you may already know, is one in which the respective sums of the numbers in all the rows, columns, and long diagonals, add up to the same number -- whereas -- a semimagic square is one in which the respective sums of the numbers in all the rows, columns, but not necessarily the diagonals, add up to the same number.)
__________________________

The problem:
Find a Magic Tour, on a standard 8x8 chessboard, or prove that it is impossible.

If you find that is is impossible, find a Semimagic Tour, on a standard 8x8 chessboard or prove that it is impossible. Show your work!

So, the first square the knight is on, is marked (1). The next square the knight jumps to is marked (2), and so on... until (64).

* For extra credit, make sure that, at the end, the knight is exactly one knight's move away from the starting square.
_______________________

Since "Knight's Tour" is a term used outside the scope of this problem, I'm sure you can find an answer on the internet. Please find an independent solution.

This may require a computer program (hence the category).

No Solution Yet Submitted by SilverKnight    
Rating: 3.0000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
I'll have the answer in about an hour or so.... | Comment 1 of 9

I was NOT the one who cast that mean-spirited "1" rating vote. In fact, I just offset it by casting a "5".  But I did check out the Internet, not to solve it, but to see if a computer solution is feasible. Mathworld reports:

As had long been known, magic knight's tours are possible for all boards of siz 4k x 4k for k > 2. However, the n = 8 (k = 2) remained open even since it was first investigated by authors such as Beverley (1848). It was not resolved until an exhaustive computer enumeration of all possibilities was completed on August 5, 2003 (Stertenbrink 2003). This search required an exhaustive 61.40 CPU-days, corresponding to 138.25 days of computation at 1 GHz.

But SilverKnight didn't ask for ALL POSSIBILITIES !!!! Disregard this silly Penny post.  

 

 

Edited on April 13, 2004, 8:09 am
  Posted by Penny on 2004-04-12 18:10:36

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information