OK, new unit, new problem. You know how a knight moves in chess? Two one way, and one the other way. How many possible knight pairs are on a 3x3 board, and 4x4 board, and so on? There's some sort of pattern in it but I cannot figure it out. Help!

Leonhard Euler, a swiss mathematician, actually introduced this math problem referred to as Springerproblem or The Knight's Tour. He was interested in finding out if there was a path that a knight could move where he would only land on one square once. There have been several attempts during the past 250 years to solve this math problem and apparently was solved in the early 1990's by a group of students as a project for a german science contest. A translated page of their work can be found at Knight's Route. On this page, under the section entitled "Heuristics and Estimates" you will find calculations for the maximum number of paths available for a knight.

There have since been additional algorithms created to solve this problem. Here is the Ant Colony Algorithm which is written up in detail in the abstract entitled "Emumerating Knight's Tours using an Ant Colony Algorithm" And this site shows an approach for figuring out moves using a 4x4 board:

Suppose the board is numbered starting from 0:

0 1 2 3 (0,0) (0,1) (0,2) (0,3)
4 5 6 7 (1,0) (1,1) (1,2) (1,3)
8 9 10 11 (2,0) (2,1) (2,2) (2,3)
12 13 14 15 (3,0) (3,1) (3,2) (3,3)

There 8 types of knight moves:
right 1 down 2 left 1 down 2
right 2 down 1 left 2 down 1
right 1 up 2 left 1 up 2
right 2 up 1 left 2 up 1

Here's a definition for right 1 down 2. If the present location is X, then find the row and column numbers for X. For any X, ColX is X mod 4 and RowX is X div 4. E.g., if X = 0, then (RowX,ColX) = (0,0); if X = 6, then (RowX,ColX) = (1,2); if X = 15, the (RowX,ColX) = (3,3). After you compute (RowX,ColX), then moving right 1 down 2 gives (RowX+2,ColX+1). But then these numbers have to be converted back to square number using the formula: Y = Row * 4 + Col. Here's what it looks like in PROLOG.

move(X,Y) :-
ColX is X mod 4, % remainder of X/4
RowX is X // 4, % divisor of X/4
Col is ColX + 1, % right 1
Col < 4,
Row is RowX + 2, % down 2
Row < 4,
Y is Row * 4 + Col,
Y >= 0.