回溯九宫格质数c++

题目

• 在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) {// 小于2的数不是质数if (n <= 1) {return false;}// 2是最小的质数if (n == 2) {return true;}// 排除所有偶数if (n % 2 == 0) {return false;}// 检查从3到sqrt(n)的奇数是否能整除nfor (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]) ;
}
/*从1~12个数中选9个数进行全排列用九宫格的方式进行， 0 1 23 4 56 7 83行3列，坐标从0开始，从(0,0)开始填空，用回溯法fillGrid函数中的(x,y)即为坐标。每扫一次，y+1,当纵坐标的值等于3时归0，同时横坐标+1。当横坐标为3的时候，说明九宫格填满了，函数完毕。 
*/ 
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.push_back(num);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;
//            grid.pop_back();}}
}
int main() {vector<int> grid(9,0);vector<int> used;fillGrid(grid, 12, 0, used);cout<<"总数"<<total.size()<<endl;
//	for(vector<int>a:total){
//		if(isGood(a))
//			k++;
//	}
//	cout<<k;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;
} 
//每行给出与对应位置左右相邻或上边相邻的位置 ，-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},
};
//找出当前候选解中还未使用，并大于等于start的最小整数
int selectNum(int start){int j;for(j=start;j<=N;j++){if(b[j])return j;}return 0;
} 
//pos位置及与其相邻的并已有数字的位置，记录它们之和的合理性
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);//从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);
}