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.

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:

Output:

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

Example 2:

Input:

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...