用C语言怎么解数独

Python027

用C语言怎么解数独,第1张

#include <stdio.h>  

#include <stdlib.h>  

  

#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<SIZE i++)  

    {  

        if(i%3==0)    

        {  

            for(j=0 j<SIZE*2+4 j++)  

                putchar('-')  

            putchar('\n')  

        }         

          

        for(j=0 j<SIZE j++)  

        {  

            if(j%3==0)  

                putchar('|')  

            if(board[i][j].num > 0)  

                printf("\033[031m%2d\033[0m", board[i][j].num)  

            else  

                printf("%2d", board[i][j].try)  

        }     

        printf("|\n")  

    }  

    for(i=0 i<SIZE*2+4 i++)  

        putchar('-')  

    putchar('\n')  

}  

  

void sub(int i, int j, int bit)  

{  

    int k, m     

      

    for(k=0 k<SIZE 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<SIZE i++)  

        for(j=0 j<SIZE 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<SIZE 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<SIZE i++)  

        for(j=0 j<SIZE 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.9*9个格子对应一个数组A,数组的第一个值从0到9表示其中填的数字,0就是不填,另一个值表示它在桌面上的位置就是坐标

2.需要10张图片,空白和9个数字

3.通过对鼠标点击的反应改变格子数组A的值,且将相应图片覆盖在相应坐标上

4.事先输入若干组数组A的值(每组81个数),作为题库

5.进行游戏时随机抽取题库中的一组,再随机抽取若干格子显示出来,其他留白.

6.填完后用三个循环判断下每行每列每块是否有相同的数字,没有则通过.

具体编按钮、放图、鼠标点击响应等各种问题查一下书,有很多书上有很多教的这种一小段一小段的程序源代码,直接抄下就行了。

加油^^

#include<stdio.h>

int num[9][9], xy[9][9]

int check(int x, int y) {

    int i, m, n

    for(i = 0 i < 9 i++)

        if ((xy[x][y] == xy[i][y]&&i != x)||(xy[x][y] == xy[x][i]&&i != y))

            return 0

    for(i = 0, m = x / 3 * 3, n = y / 3 * 3 i < 9 i++)

        if (xy[x][y] == xy[m + i / 3][n + i % 3]&&m + i / 3 != x&&n + i % 3 != y)

            return 0

    return 1

}

void search(int x, int y) {

    if (x == 9)

        for(x = 0 x < 9 x++) {

            for(y = 0 y < 9 y++)

                printf("%d ", xy[x][y])

            printf("\n")

        }

    else if (num[x][y])

        search(x + (y + 1) / 9, (y + 1) % 9)

    else

        for(xy[x][y] = 1 xy[x][y] <= 9 xy[x][y]++)

            if (check(x, y))

                search(x + (y + 1) / 9, (y + 1) % 9)

    return

}

int main() {

    int i, j

    for(i = 0 i < 9 i++)

        for(j = 0 j < 9 j++) {

            scanf("%d", &num[i][j])

            xy[i][j] = num[i][j]

        }

    search(0, 0)

    return 0

}

输入为9行9列整数,已知的整数填写对应的数字,尚待计算的未知数字填写0。

该代码的思路很简单,就是从第一行第一列开始依次填入数字,检查是否是在同一行、同一列、同一宫有没有填入重复数字,如果没有就继续填入下一个数字,如果有就返回。

虽然效率稍低,但原理简单、表述直白、易于理解,更有效率的代码是使用十字链表完成,如有兴趣可继续深入