Question

用C语言怎么解数独

Answer 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[0;31m%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;  
}