糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 3120 Sudoku 搜索

题目大意:
给出一个已经完成的数独,和一个未完成的数独。
判断前者能否经过演化后成为后者的解。演化的操作有:
1)改变数字1~9的映射
2)旋转数独
3)交换3x9中的行或列
4)交换两个3x9

解法:
实际上就是常规的搜索,不过代码难写点。
4)中共有6*6种情况
3)中共有(6*6*6)*(6*6*6)种情况
在搜索3)的时候,首先固定列,然后枚举行,这样就可以节省一些时间。

我的代码 250ms
#include <stdio.h>
#include 
<string.h>
#include 
<algorithm>
#include 
<cmath>

using namespace std;

int b1[9][9], b2[9][9];
int p3[][3= {
    {
0,1,2},
    {
0,2,1},
    {
1,0,2},
    {
1,2,0},
    {
2,0,1},
    {
2,1,0}
};
int *colseg, *rowseg;
int *col[3];

int check3(int r, int *m);

int check4(int r, int *p, int *m)
{
    
int i, j, k, l;
    
int r1, c1, r2, c2;
    
int v1, v2;
    
int m2[10];

    memcpy(m2, m, 
sizeof(int)*10);
    
for (j = 0; j < 3; j++)
        
for (k = 0; k < 3; k++)
            
for (l = 0; l < 3; l++) {
                r1 
= p[j] + rowseg[r]*3;
                c1 
= colseg[k]*3 + col[k][l];
                r2 
= j + r*3;
                c2 
= k*3 + l;
                v1 
= b1[r1][c1];
                v2 
= b2[r2][c2];
                
if (v2) {
                    
if (!m2[v2])
                        m2[v2] 
= v1;
                    
else if (m2[v2] != v1)
                        
return 0;
                }
            }
    
return check3(r + 1, m2);
}

int check3(int r, int *m)
{
    
int i;
    
    
if (r == 3)
        
return 1;

    
for (i = 0; i < 6; i++
        
if (check4(r, p3[i], m))
            
return 1;

    
return 0;
}

int check2()
{
    
int i, j, k;

    
for (i = 0; i < 6; i++
        
for (j = 0; j < 6; j++)
            
for (k = 0; k < 6; k++) {
                
int m[10= {};
                col[
0= p3[i];
                col[
1= p3[j];
                col[
2= p3[k];
                
if (check3(0, m))
                    
return 1;
            }
    
return 0;
}

int check()
{
    
int i, j;

    
for (i = 0; i < 6; i++) {
        
for (j = 0; j < 6; j++) {
            colseg 
= p3[i];
            rowseg 
= p3[j];
            
if (check2())
                
return 1;
        }
    }
    
return 0;
}

int solve()
{
    
int i, j, b[9][9];

    
if (check())
        
return 1;
    
for (i = 0; i < 9; i++)
        
for (j = 0; j < 9; j++)
            b[i][j] 
= b1[8-j][i];
    memcpy(b1, b, 
sizeof(b));
    
return check();
}

int main()
{
    
int T, i;

    scanf(
"%d"&T);
    
for (; T--; ) {
        
for (i = 0; i < 81++i) scanf(" %1d", b1[i/9]+i%9);
        
for (i = 0; i < 81++i) scanf(" %1d", b2[i/9]+i%9);
        printf(solve() 
? "Yes\n" : "No\n");
    }

    
return 0;
}



标程 79ms
这个很牛逼,原理还没搞懂!
/* Sample solution for NWERC'06: Sudoku
 * Author: Per Austrin
 * Algorithm: 
 * Fix the position of one 3x3 block at a time, then try all
 * permutations within that block and proceed to the next 3x3-block.
 * Keep a partial remapping of the digits as we go, and break whenever
 * inconsistencies are found.
 
*/
#include 
<cstdio>
#include 
<algorithm>
#include 
<string.h>

using namespace std;

int b1[9][9], b2[9][9];
int brperm[3], bcperm[3];
int rperm[3][3], cperm[3][3];

bool tryperm(int blockrow, int blockcol, int *digmap) {
    
if (blockcol == 3++blockrow, blockcol = 0;
    
if (blockrow == 3return true;

    
for (int i = 0; i < 3++i)
        
if (blockcol == 0 && brperm[i] == -1 || 
                blockcol 
> 0 && brperm[i] == blockrow)
            
for (int j = 0; j < 3++j)
                
if (blockrow == 0 && bcperm[j] == -1 ||
                        blockrow 
> 0 && bcperm[j] == blockcol) {
                    
int rp[3], cp[3];
                    brperm[i] 
= blockrow;
                    bcperm[j] 
= blockcol;

                    
for (int k = 0; k < 3++k) rp[k] = cp[k] = k;
                    
// Check if any of these permutations have already been fixed.
                    if (blockrow > 0) memcpy(cp, cperm[blockcol], sizeof(cp));
                    
if (blockcol > 0) memcpy(rp, rperm[blockrow], sizeof(rp));

                    
do {
                        
do {
                            
// Check that row and column permutations for this block
                            
// are consistent with the current remapping of the digits.
                            bool inconsistent = false;
                            
int ndigmap[10];
                            memcpy(ndigmap, digmap, 
sizeof(int)*10);
                            
for (int r = 0!inconsistent && r < 3++r)
                                
for (int c = 0!inconsistent && c < 3++c) {
                                    
int v1 = b1[3*blockrow + r][3*blockcol + c];    
                                    
int v2 = b2[3*+ rp[r]][3*+ cp[c]];
                                    
if (v2) {
                                        
if (ndigmap[v2] && ndigmap[v2] != v1) inconsistent = true;
                                        ndigmap[v2] 
= v1;
                                    }
                                }
                            memcpy(cperm[blockcol], cp, 
sizeof(cp));
                            memcpy(rperm[blockrow], rp, 
sizeof(rp));
                            
if (!inconsistent && 
                                    tryperm(blockrow, blockcol
+1, ndigmap))
                                
return true;
                        } 
while (blockrow == 0 && next_permutation(cp, cp+3));
                    } 
while (blockcol == 0 && next_permutation(rp, rp+3));

                    
// Restore block permutations
                    if (blockcol == 0) brperm[i] = -1;
                    
if (blockrow == 0) bcperm[j] = -1;
                }
    
return false;
}

int main(void) {
    
int T, i;
    scanf(
"%d"&T);
    
for (; T--; ) {
        
for (i = 0; i < 81++i) scanf(" %1d", b1[i/9]+i%9);
        
for (i = 0; i < 81++i) scanf(" %1d", b2[i/9]+i%9);
        
// Only need to check rotation by 90 degrees since additional
        
// rotation by 180 degrees can be achieved by the permutations.
        for (i = 0; i < 2++i) {
            
int digmap[10];
            
int nb2[9][9];
            
for (int r = 0; r < 9++r)
                
for (int c = 0; c < 9++c)
                    nb2[r][c] 
= b2[c][8-r];
            memcpy(b2, nb2, 
sizeof(b2));
            memset(brperm, 
-1sizeof(brperm));
            memset(bcperm, 
-1sizeof(bcperm));
            memset(digmap, 
0sizeof(digmap));
            
if (tryperm(00, digmap)) {
                printf(
"Yes\n");
                
break;
            }
        }
        
if (i == 2) printf("No\n");
    }
    
return 0;
}



posted on 2011-02-21 20:41 糯米 阅读(2159) 评论(-1)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理