回溯法求解素数填表问题

问题是这样的：3*3的方格，填入1-10（比10更大也可以），要求相邻两数之和为素数。 这个题目除了回溯似乎没有别的方法了。一开始还想遍历所有可能的排列，然后一个一个检查。把排列的算法写出来之后就是一个递归算法（不是效率最高的，应该说是效率最差的），但有个好处，可以在里头插入检查是否满足问题约束的代码，这样就减少了搜索的数量，也就是剪枝。希望有算法大牛来看看我这个解法对不对，心里还有些没底。

#include <cstdio>
#include <algorithm>

using std::printf;
 
const int N = 3;
const int Max = N*N + 1;
const int MaxSum = 2*Max – 1;

bool used[Max];
int square[N][N];
bool prime[MaxSum];

void GetAllPrimes()
{
    std::fill(prime,prime + MaxSum,true);
    prime[0] = prime[1] = false;
    for(int i = 2;i < MaxSum;++i)
        if(prime[i])
            for(int j = i*i;j < MaxSum;j += i)
                prime[j] = false;
}

void Print()
{
    for(int i = 0;i < N;++i)
    {
        for(int j = 0;j < N;++j)
            printf(“%d\t“,square[i][j]);
        printf(“\n“);
    }
}

void Search(int line,int col)
{
    if(line == N)
    {
        Print();
        printf(“\n“);
        return;
    }
    if(col == N)
    {
        Search(line + 1,0);
        return;
    }
    for(int n = 0;n < Max;++n)
    {
        if(!used[n])
        {
            if((col > 0 && !prime[n + 1 + square[line][col - 1]])
                || (line > 0 && !prime[n + 1 + square[line - 1][col]])) 
                continue;  
            square[line][col] = n + 1;
            used[n] = true;
            Search(line,col + 1);
            used[n] = false;
            square[line][col] = 0;
        }
    }
}

int main()
{
    GetAllPrimes();
    Search(0,0);
    return 0;
}