HDU 1016 Prime Ring Problem

Problem Description

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, …, n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input

n (0 < n < 20)

Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

Sample Input

6
8

Sample Output

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
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

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[] a = new int[21];
    static boolean[] visited = new boolean[21];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = 1;
        while (sc.hasNext()) {
            int n = sc.nextInt();
            System.out.println("Case " + t++ + ":");
            a[0] = 1;
            Arrays.fill(visited, true);
            dfs(1, n);
            System.out.println();
        }
    }

    private static void dfs(int num, int n) {
        // 如果数填满且首尾也符合条件，输出结果
        if (num == n && isPrime(a[num - 1] + a[0])) {
            for (int i = 0; i < n - 1; i++)
                System.out.print(a[i] + " ");
            System.out.println(a[n - 1]);
        } else {
            // 对每个数进行遍历
            for (int i = 2; i <= n; i++) {
                // 如果没有选过
                if (visited[i]) {
                    // 如果符合条件
                    if (isPrime(i + a[num - 1])) {
                        visited[i] = false;
                        a[num++] = i;
                        dfs(num, n);
                        // 回溯
                        visited[i] = true;
                        num--;
                    }
                }
            }
        }
    }

    /**
     * 判断素数
     */
    private static boolean isPrime(int x) {
        boolean flag = true;

        for (int i = 2; i < x; i++)
            if (x % i == 0) {
                flag = false;
                break;
            }

        return flag;
    }
}