指定区块和为素数的数独问题
这是德国谜题网站LMD上的一道题。规则和条件如下：
标准数独规则：每行，每列，每宫数字不重复且仅限1-9数字
附加条件：每个虚框内的数字不重复且和值是一个素数。
这道题的标题叫“原始本能(Primal Instinct)”
作者： Agent
不是很清楚作者为何给这题取这个名字。
解决这个问题会有些棘手，甚至会产生想放弃，逃避的念头，也是这就是人的一种本能。
但这道题提交正确答案的人相对比较多，且都对此题有比较高的评价。
对自己有自信的人，是不会在众多人面前露怯的，也许，这也算是人的一种本能。
嗯，中左的第4宫比较容易吸引眼球。但不能过度依赖。有蛮多人反映，尽管自己看上了第4宫，但还是折腾我好辛苦，言下之意就是，看MM，不能太专一。哈哈 刚才简单测试了一下，满足第4宫的1-9有1728种排列。:lol 第4，5，6，3宫联合判断可能会剪一大部分 先给四宫一点面子。
这三个单格肯定没有2，它们会占用3,5,7三个数。
有兴趣的，可以一起来玩玩这道题。 来个跳跃，给点信心。
俺第一个能确定的具体数字是这个2. 谜题通常玩的是灵感，灵感会照亮你的生活，令你兴奋，激动...
凭着那一丝灵感，这道题会显得格外简单... 穷举出来了，比较奇怪的是比较快的搜索方案是在搜完左中后，继续左下左上可以更快而不是中中，右中更快。
左中第一行为7,5,8 代码产生穷举代码，然后大概需要运行20分钟
#include <stdio.h>
#include <string.h>
typedef struct PL{
int len;
char *data;
}PL;
PL pls[]={
{2,"1112"},
{1,"13"},
{4,"14151617"},
{3,"182838"},
{4,"19293949"},
{3,"212231"},
{5,"2324323334"},
{2,"2737"},
{2,"3536"},
{1,"41"},
{1,"42"},
{3,"435253"},
{2,"4445"},
{2,"4656"},
{2,"4748"},
{1,"51"},
{2,"5758"},
{2,"5969"},
{3,"616263"},
{3,"646566"},
{2,"6768"},
{4,"71727374"},
{1,"75"},
{3,"767778"},
{5,"7987888999"},
{7,"81828393949596"},
{3,"848586"},
{1,"91"},
{1,"92"}
};
#define PLSN (sizeof(pls)/sizeof(pls))
int sorder={3,6,0,7,8,4,5,2,1};
#define NUMSET (PLSN+3*9)
__int128_t allsets;
void initallsets()
{
int i,j;
for(i=0;i<PLSN;i++){
__int128_t r=0;
for(j=0;j<pls.len;j++){
int row=pls.data-'1';
int col=pls.data-'1';
int index=row*9+col;
__int128_t x=1;
x<<=index;
r|=x;
}
allsets=r;
}
for(i=0;i<9;i++){//rows
__int128_t r=0;
for(j=0;j<9;j++){
__int128_t x=1;
x<<=i*9+j;
r|=x;
}
allsets=r;
}
for(i=0;i<9;i++){
__int128_t r=0;
for(j=0;j<9;j++){
__int128_t x=1;
x<<=i+j*9;
r|=x;
}
allsets=r;
}
for(i=0;i<9;i++){
__int128_t r=0;
for(j=0;j<9;j++){
__int128_t x=1;
x<<=((i%3)*3+(j%3))*9+((i/3)*3+(j/3));
r|=x;
}
allsets=r;
}
}
int main()
{
FILE *f=fopen("tmpsudk.c","w");
int i,j,k,s;
__int128_t r=0;
initallsets();
fprintf(f,"#include <stdio.h>\n");
fprintf(f,"int mset[%d];\n",(int)NUMSET);
fprintf(f,"char blocks;\n");
fprintf(f,"int isprime(int x){return (x==2||x==3||x==5||x==7||x==11||x==13||x==17||x==19||x==23||x==29||x==31||x==37||x==41);}\n");
fprintf(f,"void output(){\n");
fprintf(f,"int i;\n");
fprintf(f,"for(i=0;i<81;i++){\n");
fprintf(f,"printf(\"%%d,\",blocks);\n");
fprintf(f,"if(i%%9==8)printf(\"\\n\");\n");
fprintf(f,"}\n\nprintf(\"\\n\");fflush(stdout);\n}\n\n");
fprintf(f,"int main()\n");
fprintf(f,"{\n");
fprintf(f,"int ");
for(i=0;i<81;i++)fprintf(f,"i%d,s%d,",i,i);
fprintf(f,"s;\n");
for(i=0;i<9;i++){
int bb=sorder;
int brow=(bb/3)*3,bcol=(bb%3)*3;
for(j=0;j<3;j++)for(k=0;k<3;k++){
int bid=(brow+j)*9+(bcol+k);
fprintf(f,"for(i%d=1;i%d<=9;i%d++){\n",bid,bid,bid);
for(s=0;s<NUMSET;s++){
if((allsets>>bid)&1){
fprintf(f,"if((mset[%d]>>i%d)&1)continue;\n",s,bid);
}
}
fprintf(f,"blocks[%d]=i%d;\n",bid,bid);
__int128_t x=1;x<<=bid;
r|=x;
for(s=0;s<PLSN;s++){
if(((allsets>>bid)&1) && (r&allsets)==allsets){//reach the set
fprintf(f,"s=0;\n");
__int128_t y=1;
int t;
for(t=0;t<128;t++){
if(allsets&y){
fprintf(f,"s+=blocks[%d];\n",t);
}
y<<=1;
}
fprintf(f,"if(!isprime(s))continue;\n");
}
}
if(i==8&&j==2&&k==2){
fprintf(f,"output();\n");
}
//set of mset
for(s=0;s<NUMSET;s++){
if((allsets>>bid)&1){
fprintf(f,"mset[%d]|=1<<i%d;\n",s,bid);
}
}
}
}
for(i=8;i>=0;i--){
int bb=sorder;
int brow=(bb/3)*3,bcol=(bb%3)*3;
for(j=2;j>=0;j--)for(k=2;k>=0;k--){
int bid=(brow+j)*9+(bcol+k);
for(s=0;s<NUMSET;s++){
if((allsets>>bid)&1){
fprintf(f,"mset[%d]&=~(1<<i%d);\n",s,bid);
}
}
fprintf(f,"}//i%d\n",bid);
}
}
fprintf(f,"}\n");
fclose(f);
return 0;
}
高手解这题能在30分钟内解决。
此题的纸笔解题的过程之一：
页:
[1]
2