The Knights of the Round Table

The Knights of the Round Table are well-known knights under the king Arthur. In order to become one of the knights of the Round Table, a knight had to be proved worthy and swore a Code of Chivalry. The Code of Chivalry is as follows:

• To never do outrage nor murder.
• Always to flee treason.
• To by no means be cruel but to give mercy unto him who asks for mercy.
• To always do ladies, gentlewomen and widows succor.
• To never force ladies, gentlewomen or widows.
• Not to take up battles in wrongful quarrels for love or worldly goods.

Now every time the knights of the Round Table meet, they sit at a circular table. Each knight will be numbered according to the order they were accepted to the table. There can be at most 16 knights at any given time. There is a traditional belief that when they meet, there must be at least two knights and there must be an even number of knights to start the meeting. They also believe that the sum of the numbers of any two adjacent knights must be a prime number. Write a program to find all possible seat settings satisfying the traditional beliefs.

Input Specification

The input consists of several test cases. Each test case consists of a single line containing n (0 < n ≤ 16), the number of knights to be presented at the meeting. n is always an even number.

Output Specification

For each test case, output all possible seat settings that satisfy the belief explained above. The format of the output is as shown below. Each row represents a series of knight numbers in the table beginning from knight number 1 clockwise and anticlockwise. The seat settings must be listed in lexicographic order. Print an empty line between two consecutive outputs.

Sample Input

1. 6
2. 8

download as text file

Output for Sample Input

1. Case 1:
2. 1 4 3 2 5 6
3. 1 6 5 2 3 4
5. Case 2:
6. 1 2 3 8 5 6 7 4
7. 1 2 5 8 3 4 7 6
8. 1 4 7 6 5 8 3 2
9. 1 6 7 4 3 8 5 2

download as text file