放格填数数独

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 const int maxn = 6;
 5 int table[maxn][maxn];
 6 int hash_col[maxn][maxn], hash_row[maxn][maxn], hash_gro[maxn][maxn];
 7 int gro_id[maxn][maxn];
 8 int cas = 0;
 9 void next_pos(int& r, int& c)
10 {
11     if(5 == c)//这里写成了if(6 == c),害得我调了2个多小时
12     {
13         r ++; c = 0;
14     }
15     else
16     {
17         c ++;
18     }
19 }
20 void dfs(int r, int c)
21 {
22    if(r >= 6)
23     {
24         printf("%d\n", ++ cas);
25         for(int i = 0; i < 6; i ++)
26         {
27             for(int j = 0; j < 6; j ++)
28             {
29                 printf(j == 0 ? "%c" : " %c", 'A' + table[i][j]);
30             }
31             printf("\n");
32         }
33         return ;
34     }
35     int nr = r, nc = c;
36     next_pos(nr, nc);
37     if(-1 == table[r][c])
38     {
39         for(int i = 0; i < 6; i ++)
40         {
41             int z = gro_id[r][c];
42             if(hash_row[r][i] || hash_col[c][i] || hash_gro[z][i])
43                 continue;
44             //modify the state value
45             table[r][c] = i;
46             hash_row[r][i] = hash_col[c][i] = hash_gro[z][i] = 1;
47             dfs(nr, nc);
48 
49             //recover the state value
50             table[r][c] = -1;
51             hash_row[r][i] = hash_col[c][i] = hash_gro[z][i] = 0;
52         }
53     }
54     else
55     {
56         dfs(nr, nc);
57     }
58 }
59 int main(void)
60 {
61     freopen("data.txt", "r", stdin);
62     memset(table, -1, sizeof(table));
63     for(int  i = 0; i < 6; i ++)
64     {
65         char str[maxn + 1];
66         scanf("%s", str);
67         for(int j = 0; j < 6; j ++)
68         {
69              gro_id[i][j] = str[j] - '0';
70         }
71     }
72     int n;
73     scanf("%d", &n);
74     char tmp[5];
75     while(n --)
76     {
77         scanf("%s", tmp);
78         int r = tmp[0] - '0', c = tmp[1] - '0';
79         int v = tmp[2] - 'A';
80         int z = gro_id[r][c];
81         table[r][c] = v;
82         hash_row[r][v] = hash_col[c][v] = hash_gro[z][v] = 1;
83 
84     }
85     dfs(0, 0);
86     return 0;
87 }

 1 #include<stdio.h>
 2 
 3 int bj_r[6][6],bj_c[6][6],bj_q[6][6];//分别用来标记行、列和划分的区域中的字母是否已用
 4 int in[6][6],out[6][6];//分别表示输入的表格和生成的数组表格
 5 int count=1;//计数器
 6 
 7 void dfs(int r,int c)
 8 {
 9     int i,j,nr,nc,x;
10     if(r==6)//数组从0-5,6说明已经填满
11     {
12         printf("%d\n",count++);//计数器加一，输出
13         for(i=0;i<6;i++)
14         {
15             for(j=0;j<6;j++)
16                 printf("%c ",'A'+out[i][j]);
17             printf("\n");
18         }
19         return;
20     }
21     //nr、nc是确定下个填充的位置
22     if(5==c) 
23     {
24         nr=r+1;
25         nc=0;
26     }
27     else 
28     {
29         nr=r;
30         nc=c+1;
31     }
32     
33     if(-1==out[r][c])//该位置可以填充
34     {
35         for(i=0;i<6;i++)//从A-E尝试填充
36         {
37             x=in[r][c];
38             if(bj_r[r][i]||bj_c[c][i]||bj_q[x][i])//行、列和划分的区域中的字母有一个或多个已用则退出
39                 continue;
40             //搜索
41             out[r][c]=i;
42             bj_r[r][i]=bj_c[c][i]=bj_q[x][i]=1;
43             dfs(nr,nc);
44 
45             bj_r[r][i]=bj_c[c][i]=bj_q[x][i]=0;
46             out[r][c]=-1;
47             //
48         }
49     }
50     else 
51     dfs(nr,nc);
52 }
53 
54 int main()
55 {
56     int i,j,n,r,c,x,z;
57     char inc[7];
58     for(i=0;i<6;i++)//输入
59     {
60         scanf("%s",inc);
61         for(j=0;j<6;j++)
62         {
63             in[i][j]=inc[j]-'0';
64             out[i][j]=-1;
65         }
66     }
67     scanf("%d",&n);
68     while(n--)
69     {
70         scanf("%s",inc);
71         r=inc[0]-'0';
72         c=inc[1]-'0';
73         z=inc[2]-'A';//用数字便于运算和存储
74         x=in[r][c];//x表示输入的数所在的区域
75         bj_r[r][z]=bj_c[c][z]=bj_q[x][z]=1;//标记该区域中的第z号字母已经被用
76         out[r][c]=z;
77     }
78     dfs(0,0);//搜索
79     return 0;
80 }

放格填数 数独

放格填数数独