用C语言怎么解数独

答案:2 悬赏:60 手机版

解决时间 2021-02-04 22:16

提问者网友：温旧梦泪无声
2021-02-04 15:06

用C语言怎么解数独

最佳答案

五星知识达人网友：千杯敬自由
2021-02-04 16:28

#include
#include

#define SIZE 9
#define get_low_bit(x) ((~x&(x-1))+1)

struct{
    int left;
    char num;
    char try;
}board[SIZE][SIZE];

int bit2num(int bit)
{
    switch(bit){
        case 1:case 2:
            return bit;
        case 4:
            return 3;
        case 8:
            return 4;
        case 16:
            return 5;
        case 32:
            return 6;
        case 64:
            return 7;
        case 128:
            return 8;
        case 256:
            return 9;
    }
}

void printf_res()
{
    int i, j, k;

    for(i=0; i     {
        if(i%3==0)
        {
            for(j=0; j                 putchar('-');
            putchar('\n');
        }

        for(j=0; j         {
            if(j%3==0)
                putchar('|');
            if(board[i][j].num > 0)
                printf("\033[0;31m%2d\033[0m", board[i][j].num);
            else
                printf("%2d", board[i][j].try);
        }
        printf("|\n");
    }
    for(i=0; i         putchar('-');
    putchar('\n');
}

void sub(int i, int j, int bit)
{
    int k, m;

    for(k=0; k     {
        board[k][j].left &= ~bit;
        board[i][k].left &= ~bit;
    }

    for(k=i/3*3; k<(i/3+1)*3; k++)
        for(m=j/3*3; m<(j/3+1)*3; m++)
            board[k][m].left &= ~bit;
}

void init()
{
    int i, j;

    for(i=0; i         for(j=0; j             if(board[i][j].num > 0)
                sub(i, j, 1<<(board[i][j].num-1));
            else if(board[i][j].try > 0)
                sub(i, j, 1<<(board[i][j].try-1));
}

void add(int i, int j, int bit)
{
    int k, m;

    for(k=0; k     {
        board[k][j].left |= bit;
        board[i][k].left |= bit;
    }
    for(k=i/3*3; k<(i/3+1)*3; k++)
        for(m=j/3*3; m<(j/3+1)*3; m++)
            board[k][m].left |= bit;
}

void solve(int pos)
{
    int i=pos/SIZE;
    int j=pos%SIZE;
    int bit, left;

    if(pos == SIZE*SIZE)
    {
        printf_res();
        exit(0);
    }
    if(board[i][j].num > 0)
        solve(pos+1);
    else
        for(left=board[i][j].left; left; left&=(left-1))
        {
            bit = get_low_bit(left);
            sub(i, j, bit);
            board[i][j].try = bit2num(bit);

            solve(pos+1);

            add(i, j, bit);
            board[i][j].try=0;
            init();
        }
}

int main()
{
    int i, j, c;

    for(i=0; i         for(j=0; j         {
            while((c=getchar())<'0' || c>'9')
                ;
            board[i][j].num = c-'0';
            board[i][j].try = 0;
            board[i][j].left = 0x0001FF;
        }
    init();
    solve(0);

    return 0;
}

全部回答

1楼网友：摆渡翁
2021-02-04 17:50

#include #include #include char sd[81]; bool isok = false; //显示数独 void show() { if (isok) puts("求解完成"); else puts("初始化完成"); for (int i = 0; i < 81; i++) { putchar(sd[i] + '0'); if ((i + 1) % 9 == 0) putchar('\n'); } putchar('\n'); } //读取数独 bool init() { file *fp = fopen("in.txt", "rb"); if (fp == null) return false; fread(sd, 81, 1, fp); fclose(fp); for (int i = 0; i < 81; i++) { if (sd[i] >= '1' && sd[i] <= '9') sd[i] -= '0'; else sd[i] = 0; } show(); return true; } //递归解决数独 void force(int k) { if (isok) return; if (!sd[k]) { for (int m = 1; m <= 9; m++) { bool mm = true; for (int n = 0; n < 9; n++) { if ((m == sd[k/27*27+(k%9/3)*3+n+n/3*6]) || (m == sd[9*n+k%9]) || (m == sd[k/9*9+n])) { mm = false; break; } } if (mm) { sd[k] = m; if (k == 80) { isok = true; show(); return; } force(k + 1); } } sd[k] = 0; } else { if (k == 80) { isok = true; show(); return; } force(k + 1); } } int main() { system("cls"); if (init()) { double start = clock(); force(0); printf("耗时%.0fms", clock() - start); } else puts("初始化错误"); getchar(); }

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！