淘先锋技术网

首页 1 2 3 4 5 6 7

    论坛上看到一个回溯算法题,这里小记一下。

    原题:在3×3个方格的方阵中要填入数字1到N(N≥10)内的某9个数字,每个方格填一个整数,似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。

    为了简化代码突出回溯思想,程序中有很多简化了的东西。


    代码:

#include <iostream>
#include <stdio.h>

using namespace std;
#define N 10
#define INIT -2
#define MARK -1

int num[9];
int mark[N];

int main()
{
    int test(int pos);
    for(int i=0;i<9;i++)
    {
        num[i]=INIT;
    }
    for(int i=0;i<N;i++)
    {
        mark[i]=INIT;
    }
    test(0);
    return 0;
}

int isPrime(int num)
{
    for(int i=2;i<=num/2;i++)
    {
        if(num%i==0)
        {
            return 0;
        }
    }
    return 1;

}

int check()
{
    if(!isPrime(num[0]+num[1]))
        return 0;
    if(!isPrime(num[2]+num[1]))
        return 0;
    if(!isPrime(num[3]+num[4]))
        return 0;
    if(!isPrime(num[4]+num[5]))
        return 0;
    if(!isPrime(num[6]+num[7]))
        return 0;
    if(!isPrime(num[7]+num[8]))
        return 0;
    if(!isPrime(num[0]+num[3]))
        return 0;
    if(!isPrime(num[3]+num[6]))
        return 0;
    if(!isPrime(num[1]+num[4]))
        return 0;
    if(!isPrime(num[4]+num[7]))
        return 0;
    if(!isPrime(num[2]+num[5]))
        return 0;
    if(!isPrime(num[5]+num[8]))
        return 0;
    return 1;

}

void print_info()
{
    for(int i=0;i<9;i++)
    {
        printf("%d ",num[i]);
    }
    printf("\n");
}

void test(int pos)
{
    if(pos==(9))
    {
        if(check()==1)
        {
            print_info();
        }
        return;
    }
    for(int i=0;i<N;i++)
    {
        if(mark[i]!=MARK)
        {
            num[pos]=i+1;
            mark[i]=MARK;
            test(pos+1);
            mark[i]=INIT;
        }
    }

}

    运行结果:

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