[C] Sudoku

上次寫C語言, 可能是在2專的時候, 在 1997年或 1998年, 這次挑戰用C 語言寫數獨(Sudoku) 的程式, 大約 0.009秒就可以計算出簡單版本數獨的結果. 試了一下, 好像要用亂數來幫忙做決定猜測的流程.

input:
194800203500012096203495008935700682418029500726500900600058324840936015000070060

output:
1948XX2X35XXX12096...
(Where X means any one of 1..9)

以下的程式只能解決簡單的情況, 無法解決 "需要去猜測" 的情況.

#include <stdio.h>

int option_ary[81][10];

//int main(int argc, char *argv[])
int main()
{
    /*
    if(argc < 2 || argc > 3)
    {
        printf("Pleae input one paramater.\n");
        return 0;
    }
    */
 
    //printf("input string is %s.\n",argv[1]);
    //printf("input strlen is %d.\n",strlen(argv[1]));
   
    char input_string[256];
    scanf("%s",input_string);
    //printf("your string: %s",input_string);
    //return 1;
   
    int i,j;
   
    // initial options table.
    // first [i][0] is the final answer.
    for(i=0;i<81;i++){
        option_ary[i][0]=0;
        for(j=1;j<=9;j++){
            option_ary[i][j]=j;
        }
    }
   
    // get input data.
    for(i=0;i<81;i++){
        //int input_value = argv[1][i]-48;
        int input_value = input_string[i]-48;
        option_ary[i][0]=input_value;
        if(option_ary[i][0]>0){
            remove_optins_in_table(i,input_value);
        }
    }

    int check_count=0;
    int check_result=0;
    for(i=0;i<100;i++){
        check_count++;
        check_result=check_answer(0);
        if(check_result==1)
        {
            break;
        }
    }
   
    // 無解(或多種解), 開始猜測可能的解.
    // (沒寫)

    if(check_result==1){
        printf("finish, check count:%d",check_count);
    }
    else
    {
        printf("check fail..., no answer.");
    }


   
    // test convert index
    //int index=80;
    //printf("row/col/block: %d/%d/%d", get_row(index), get_col(index), get_block(index));

    // output final answer
    //printf("\n");
    for(i=0;i<81;i++){
        printf("%d",option_ary[i][0]);
        /*
        if(i % 9==8){
            printf("\n");
        }
        */
    }
    return 1;
}


// purpose: check answer
// return:
//      1: finish.
//      0: not finish.
int check_answer(int try_to_guess)
{
    int ans_i=0,ans_j=0;
    int unknow_value_count=0;
    for(ans_i=0; ans_i<81; ans_i++)
    {
        int zero_count=0;
        int last_value=0;
        if(option_ary[ans_i][0]==0){
            unknow_value_count++;
            // value un-know.
            for(ans_j=1; ans_j <=9; ans_j++)
            {
                if(option_ary[ans_i][ans_j]==0)
                {
                    zero_count++;
                }
                else
                {
                    if(last_value==0){
                        // looking for first value.
                        last_value=option_ary[ans_i][ans_j];
                    }
                    // looking for last value.
                    //last_value=option_ary[ans_i][ans_j];
                }
            }
            if(zero_count==8)
            {
                // bingo.
                //printf("\n bingo %d,%d\n",ans_i,last_value);
                option_ary[ans_i][0]=last_value;
                remove_optins_in_table(ans_i,last_value);
            }
            else {
                if(zero_count==(8-try_to_guess)){
                    // two element, guess last one.
                    if(try_to_guess>=1){
                        option_ary[ans_i][0]=last_value;
                        remove_optins_in_table(ans_i,last_value);
                    }
                }
            }
        }
    }
   
    int return_value=0;
    if(unknow_value_count==0)
    {
        return_value=1;
    }
   
    return return_value;
}

int get_row(int index)
{
    return (index/9)+1;
}

int get_col(int index)
{
    return index%9;
}

int get_block(int index)
{
    int base_row=(index/27)*3+(index%9/3)+1;
}

int remove_optins_in_table(int index, int input_value)
{
    // remove options in row.
    remove_options_in_row(index, input_value);
   
    // remove options in col.
    remove_options_in_col(index, input_value);
   
    // remove options in block.
    remove_options_in_block(index, input_value);
}

// remove options in row.
int remove_options_in_row(int index, int input_value)
{
    int i=0;
    for(i=0; i<9; i++)
    {
        int target_index=((index/9)*9)+i;
        option_ary[target_index][input_value]=0;
    }
   
    return 1;
}

// remove options in col.
int remove_options_in_col(int index, int input_value)
{
    int i=0;
    for(i=0; i<9; i++)
    {
        int target_index=(index%9)+(i*9);
        option_ary[target_index][input_value]=0;
    }
   
    return 1;
}

// remove options in block.
int remove_options_in_block(int index, int input_value)
{
    int i=0;
    int target_block=get_block(index);
    for(i=0; i<81; i++)
    {
        if(get_block(i)==target_block)
        {
            option_ary[i][input_value]=0;
        }
    }
   
    return 1;
}