指定区块和为素数的数独问题

小铃铛

这是德国谜题网站LMD上的一道题。

规则和条件如下：
标准数独规则：每行，每列，每宫数字不重复且仅限1-9数字
附加条件：每个虚框内的数字不重复且和值是一个素数。

这道题的标题叫“原始本能(Primal Instinct)”
作者： Agent

不是很清楚作者为何给这题取这个名字。
解决这个问题会有些棘手，甚至会产生想放弃，逃避的念头，也是这就是人的一种本能。

但这道题提交正确答案的人相对比较多，且都对此题有比较高的评价。
对自己有自信的人，是不会在众多人面前露怯的，也许，这也算是人的一种本能。

小铃铛

嗯，中左的第4宫比较容易吸引眼球。但不能过度依赖。有蛮多人反映，尽管自己看上了第4宫，但还是折腾我好辛苦，言下之意就是，看MM，不能太专一。哈哈

northwolves

刚才简单测试了一下，满足第4宫的1-9有1728种排列。

northwolves

第4，5，6，3宫联合判断可能会剪一大部分

小铃铛

先给四宫一点面子。
这三个单格肯定没有2，它们会占用3,5,7三个数。

有兴趣的，可以一起来玩玩这道题。

小铃铛

来个跳跃，给点信心。

俺第一个能确定的具体数字是这个2.

小铃铛

谜题通常玩的是灵感，灵感会照亮你的生活，令你兴奋，激动...

凭着那一丝灵感，这道题会显得格外简单...

mathe

穷举出来了，比较奇怪的是比较快的搜索方案是在搜完左中后，继续左下左上可以更快而不是中中，右中更快。
左中第一行为7,5,8

mathe

代码产生穷举代码，然后大概需要运行20分钟

1. #include <stdio.h>
   
2. #include <string.h>
   
3. 
   
4. typedef struct PL{
   
5.     int len;
   
6.     char *data;
   
7. }PL;
   
8. 
   
9. PL pls[]={
   
10.         {2,"1112"},
    
11.         {1,"13"},
    
12.         {4,"14151617"},
    
13.         {3,"182838"},
    
14.         {4,"19293949"},
    
15.         {3,"212231"},
    
16.         {5,"2324323334"},
    
17.         {2,"2737"},
    
18.         {2,"3536"},
    
19.         {1,"41"},
    
20.         {1,"42"},
    
21.         {3,"435253"},
    
22.         {2,"4445"},
    
23.         {2,"4656"},
    
24.         {2,"4748"},
    
25.         {1,"51"},
    
26.         {2,"5758"},
    
27.         {2,"5969"},
    
28.         {3,"616263"},
    
29.         {3,"646566"},
    
30.         {2,"6768"},
    
31.         {4,"71727374"},
    
32.         {1,"75"},
    
33.         {3,"767778"},
    
34.         {5,"7987888999"},
    
35.         {7,"81828393949596"},
    
36.         {3,"848586"},
    
37.         {1,"91"},
    
38.         {1,"92"}
    
39. };
    
40. #define PLSN (sizeof(pls)/sizeof(pls[0]))
    
41. int sorder[9]={3,6,0,7,8,4,5,2,1};
    
42. 
    
43. #define NUMSET (PLSN+3*9)
    
44. __int128_t allsets[NUMSET];
    
45. 
    
46. void initallsets()
    
47. {
    
48.     int i,j;
    
49.     for(i=0;i<PLSN;i++){
    
50.         __int128_t r=0;
    
51.         for(j=0;j<pls[i].len;j++){
    
52.             int row=pls[i].data[2*j]-'1';
    
53.             int col=pls[i].data[2*j+1]-'1';
    
54.             int index=row*9+col;
    
55.             __int128_t x=1;
    
56.             x<<=index;
    
57.             r|=x;
    
58.         }
    
59.         allsets[i]=r;
    
60.     }
    
61.     for(i=0;i<9;i++){//rows
    
62.         __int128_t r=0;
    
63.         for(j=0;j<9;j++){
    
64.              __int128_t x=1;
    
65.              x<<=i*9+j;
    
66.              r|=x;
    
67.         }
    
68.         allsets[PLSN+i]=r;
    
69.     }
    
70.     for(i=0;i<9;i++){
    
71.         __int128_t r=0;
    
72.         for(j=0;j<9;j++){
    
73.             __int128_t x=1;
    
74.             x<<=i+j*9;
    
75.             r|=x;
    
76.         }
    
77.         allsets[PLSN+9+i]=r;
    
78.     }
    
79.     for(i=0;i<9;i++){
    
80.         __int128_t r=0;
    
81.         for(j=0;j<9;j++){
    
82.             __int128_t x=1;
    
83.             x<<=((i%3)*3+(j%3))*9+((i/3)*3+(j/3));
    
84.             r|=x;
    
85.         }
    
86.         allsets[PLSN+18+i]=r;
    
87.     }
    
88. }
    
89. 
    
90. int main()
    
91. {
    
92.     FILE *f=fopen("tmpsudk.c","w");
    
93.     int i,j,k,s;
    
94.     __int128_t r=0;
    
95.     initallsets();
    
96.     fprintf(f,"#include <stdio.h>\n");
    
97.     fprintf(f,"int mset[%d];\n",(int)NUMSET);
    
98.     fprintf(f,"char blocks[81];\n");
    
99.     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");
    
100.     fprintf(f,"void output(){\n");
     
101.     fprintf(f,"int i;\n");
     
102.     fprintf(f,"for(i=0;i<81;i++){\n");
     
103.     fprintf(f,"printf("%%d,",blocks[i]);\n");
     
104.     fprintf(f,"if(i%%9==8)printf("\\n");\n");
     
105.     fprintf(f,"}\n\nprintf("\\n");fflush(stdout);\n}\n\n");
     
106.     fprintf(f,"int main()\n");
     
107.     fprintf(f,"{\n");
     
108.     fprintf(f,"int ");
     
109.     for(i=0;i<81;i++)fprintf(f,"i%d,s%d,",i,i);
     
110.     fprintf(f,"s;\n");
     
111.     for(i=0;i<9;i++){
     
112.         int bb=sorder[i];
     
113.         int brow=(bb/3)*3,bcol=(bb%3)*3;
     
114.         for(j=0;j<3;j++)for(k=0;k<3;k++){
     
115.             int bid=(brow+j)*9+(bcol+k);
     
116.             fprintf(f,"for(i%d=1;i%d<=9;i%d++){\n",bid,bid,bid);
     
117.             for(s=0;s<NUMSET;s++){
     
118.                 if((allsets[s]>>bid)&1){
     
119.                     fprintf(f,"if((mset[%d]>>i%d)&1)continue;\n",s,bid);
     
120.                 }
     
121.             }
     
122.             fprintf(f,"blocks[%d]=i%d;\n",bid,bid);
     
123.             __int128_t x=1;x<<=bid;
     
124.             r|=x;
     
125.             for(s=0;s<PLSN;s++){
     
126.                 if(((allsets[s]>>bid)&1) && (r&allsets[s])==allsets[s]){//reach the set
     
127.                     fprintf(f,"s=0;\n");
     
128.                     __int128_t y=1;
     
129.                     int t;
     
130.                     for(t=0;t<128;t++){
     
131.                         if(allsets[s]&y){
     
132.                             fprintf(f,"s+=blocks[%d];\n",t);
     
133.                         }
     
134.                         y<<=1;
     
135.                     }
     
136.                     fprintf(f,"if(!isprime(s))continue;\n");
     
137.                 }
     
138.             }
     
139.             if(i==8&&j==2&&k==2){
     
140.                 fprintf(f,"output();\n");
     
141.             }
     
142.             //set of mset
     
143.             for(s=0;s<NUMSET;s++){
     
144.                 if((allsets[s]>>bid)&1){
     
145.                     fprintf(f,"mset[%d]|=1<<i%d;\n",s,bid);
     
146.                 }
     
147.             }
     
148.         }
     
149.     }
     
150. 
     
151.     for(i=8;i>=0;i--){
     
152.         int bb=sorder[i];
     
153.         int brow=(bb/3)*3,bcol=(bb%3)*3;
     
154.         for(j=2;j>=0;j--)for(k=2;k>=0;k--){
     
155.             int bid=(brow+j)*9+(bcol+k);
     
156.             for(s=0;s<NUMSET;s++){
     
157.                 if((allsets[s]>>bid)&1){
     
158.                     fprintf(f,"mset[%d]&=~(1<<i%d);\n",s,bid);
     
159.                 }
     
160.             }
     
161.             fprintf(f,"}//i%d\n",bid);
     
162.         }
     
163.     }
     
164.     fprintf(f,"}\n");
     
165.     fclose(f);
     
166.     return 0;
     
167. }
     

复制代码

小铃铛

高手解这题能在30分钟内解决。

此题的纸笔解题的过程之一：