Day 7 : Prime Ring

hardBacktracking with pruning

A ring is composed of n (even number) circles.
Put natural numbers 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: The number in the first circle should always be 1.

Prime Ring for n=6
One Possible Prime Ring for n = 6.

Input Format:

The first and only line of input contains an integer $n$ denoting the number of circles.

Output Format:

You need to output $k$ lines where $k$ is the number of total combinations satisfying above condition. Each of the $k$ line should give the permutation satisfying the above condition, i.e. numbers of circles in clockwise order. Give the lines in sorted order.

Constraints:

($2 \le n \le 16$)

Examples:

Example 1:

Input:

6

Output:

1 4 3 2 5 6 
1 6 5 2 3 4

Example 2:

Input:

8

Output:

1 2 3 8 5 6 7 4 
1 2 5 8 3 4 7 6 
1 4 7 6 5 8 3 2 
1 6 7 4 3 8 5 2

Code

Loading Editor...