题目
- 在3*3个方格的方阵中要填入数字1~n(n>=10)内的某9个数,每个方格填入一个整数,要求所有两个相邻方格(左右,上下)内的两个整数之和为质数。
递归算法
思路
- 用递归算法从12个数中选取9个数进行全排列。
- 构造递归函数void fillGrid(vector& grid, int n, int b, vector& used),用vector模拟9宫格,忽略它的形状。n=12,即从12个数中选取(9个数)。b是从数组的哪个下标开始。used数组记录已经选取的数。
- fillGrid(grid, 12, 0, used)表示,12个数中选9个全排列,从下标0开始选。
- 当下标为0的数符合条件时,再选取九宫格的后8个数(从下标为1开始选),即fillGrid(grid, 12, 1, used);
- 递归出口。当下标为9,即b==9时,说明九宫格的9个数选好了。
代码
#include <iostream>
#include <vector>
#include <cmath>
#include<algorithm>
using namespace std;
int k=0;
vector<vector<int>> total;
bool isPrime(int n) {if (n <= 1) {return false;}if (n == 2) {return true;}if (n % 2 == 0) {return false;}for (int i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {return false;}}return true;
}
bool isGood(vector<int> &a){return isPrime(a[0]+a[1]) && isPrime(a[1]+a[2]) && isPrime(a[3]+a[4]) && isPrime(a[4]+a[5]) && isPrime(a[6]+a[7]) && isPrime(a[7]+a[8]) && isPrime(a[0]+a[3]) && isPrime(a[1]+a[4]) && isPrime(a[5]+a[2]) && isPrime(a[3]+a[6]) && isPrime(a[4]+a[7]) && isPrime(a[5]+a[8]) ;
}
void fillGrid(vector<int>& grid, int n, int b, vector<int>& used) {if (b == 9) {total.push_back(grid);return;}for (int num = 1; num <= n; ++num) {if (find(used.begin(), used.end(), num) == used.end()) {
grid[b]=num;bool valid=false;switch(b){case 0:valid=true;break;case 1:valid=isPrime(grid[0]+grid[1]);break;case 2:valid=isPrime(grid[1]+grid[2]);break;case 3:valid=isPrime(grid[0]+grid[3]);break;case 4:valid=isPrime(grid[3]+grid[4]) && isPrime(grid[1]+grid[4]);break;case 5:valid=isPrime(grid[4]+grid[5]) && isPrime(grid[2]+grid[5]);break;case 6:valid=isPrime(grid[3]+grid[6]);break;case 7:valid=isPrime(grid[6]+grid[7]) && isPrime(grid[7]+grid[4]);break;case 8:valid=isPrime(grid[7]+grid[8]) && isPrime(grid[5]+grid[8]);break;}if(!valid) continue;used.push_back(num);fillGrid(grid, n, b + 1, used);used.pop_back();grid[b]=0;
}}
}
int main() {vector<int> grid(9,0);vector<int> used;fillGrid(grid, 12, 0, used);cout<<"总数"<<total.size()<<endl;
return 0;
}
非递归算法
#include<stdio.h>
#define N 12
int kk=0;
void write(int a[]){int i,j;for(i=0;i<3;i++){for(j=0;j<3;j++){printf("%3d",a[3*i+j]);}printf("\n");}printf("\n");if(kk++ %4==0){scanf("%*c");}
}
int b[N+1];
int a[10];
int isPrime(int m){int i;int primes[]={2,3,5,7,11,13,17,19,23,29,-1};if(m==2){return 1;}if(m==1 || m%2 ==0){return 0;}for(i = 0;primes[i]>0;++i){if(m==primes[i]){return 1;}}for(i=3;i*i<=m;){if(m%i==0)return 0;i+=2;}return 1;
}
int checkMarix[][3]={{-1 },{0,-1},{1,-1},{0,-1},{1,3,-1},{2,4,-1},{3,-1},{4,6,-1},{5,7,-1},
};
int selectNum(int start){int j;for(j=start;j<=N;j++){if(b[j])return j;}return 0;
}
int check(int pos){int j;if(pos<0) return 0;for(int i=0;(j=checkMarix[pos][i])>0;i++){if(!isPrime(a[pos]+a[j])) return 0;}return 1;
}
int extend(int pos){a[++pos]=selectNum(1);b[a[pos]]=0;return pos;
}
int change(int pos){int j;while(pos>=0 && (j=selectNum(a[pos]+1))==0){b[a[pos--]]=1;}if(pos<0)return -1;b[a[pos]]=1;a[pos]=j;b[j]=0;return pos;
}
void find(){int ok=1,pos=-1, n= 8;do{if(ok){if(pos==n){write(a);pos=change(pos);}else{pos=extend(pos);}}else{pos=change(pos);}ok=check(pos);}while(pos!=-1);
}
int main(){int i;for(i=1;i<=N;++i){b[i]=1;}find();printf("\nKK=%d\n",kk);
}