數獨程式:

一般的數獨解答程式大多由暴力法來測出解答，透過不斷的嘗試填值與修正，才能完成好解答，而此程式是先透過一般解數獨題目的方式來判斷出號碼，直到沒有符合其他條件後，才採用暴力法求解。好處為可以持續為程式新增更多人工智慧的判斷方法，也可以練習不好矩陣的觀念，若要節省記憶體的使用，可以在修改為動態記憶體配置來解題。

參考資料

C 語言數獨解題程式原始碼

http://oddest.nc.hcc.edu.tw/su304.htm

程式碼部份

allfuction.h

int read_sudoku();
void check_column();
void    check_row();
void check_little_square();

int find_mapping_row(int i, int round);
int find_mapping_column(int i, int round);
void find_unique_element();

void numberOfZero(int zero_counter, int number_check, int row_or_column);
void modify(int x, int y);
void findNumber_row_square();
void findNumber_column_square();
void try_and_error();

main.cpp

#include <stdio.h>
#include <stdlib.h>
#include "allfunction.h"

int sudoku[9][9] = {0};
int sudoku_2[81] = {0};

int column[9][10] = {0};
int row[9][10] = {0};
int little_square[9][10] = {0};
int change;

int main()
{
    read_sudoku();                //讀取數獨並填入相關資訊

    int counter = 0;
    int i, j;
    for(i = 0 ; i < 9 ; i++)
    {
        for(j = 0 ; j < 9 ; j++)
        {
            printf("%d ", sudoku[i][j]);
            if(++counter % 9 == 0)
                printf("\n");
        }
    }
    printf("*******************\n");

    check_column();            //將每一行陣列缺少的號碼填入其對映的行陣列   
    check_row();                //將每一列陣列缺少的號碼填入其對映的列陣列
    check_little_square();    //將每一小正方形缺少的號碼填入其對映的小正方形陣列

    change = 1; //設為有修改過  使其進入while迴圈
    while(change == 1)
    {
        change = 0; //預設為0 表示沒有寫入號碼
        findNumber_row_square();
        findNumber_column_square();
        find_unique_element();
    }


    for(i = 0 ; i < 9 ; i++)
    {
        for(j = 0 ; j < 9 ; j++)
        {
            sudoku_2[i * 9 + j] = sudoku[i][j];
        }
    }

    try_and_error();

    counter = 0;
    for(i = 0 ; i < 81 ; i++)
    {
        printf("%d ", sudoku_2[i]);
        if(++counter % 9 == 0)
            printf("\n");
    }
    system("pause");
    return 0;
}

read_sudoku.cpp

//數獨解題 By Zheng yu cheng
//解題針對9*9數獨題目

#include <stdio.h>
#include <stdlib.h>
#include "allfunction.h"
extern int sudoku[9][9];

int read_sudoku()
{
    FILE *stream;
    stream = fopen("sudoku.txt","r");
   
    int i = 0;

    if(stream != NULL)
    {
        for( i = 0 ; i < 9 ; i++)
        {
            fscanf(stream, "%d %d %d %d %d %d %d %d %d", &sudoku[i][0], &sudoku[i][1], &sudoku[i][2], &sudoku[i][3],
                &sudoku[i][4], &sudoku[i][5], &sudoku[i][6], &sudoku[i][7], &sudoku[i][8]);
        }
        fclose(stream);
    }

    return 0;
}

check_row.cpp

#include <stdio.h>
#include <stdlib.h>
#include "allfunction.h"

extern int row[9][10];
extern int sudoku[9][9];
void find_number_row(int x);

void    check_row()
{
    int x;
    for(x = 0 ; x <= 8 ; x++)
        find_number_row(x);
}

void find_number_row(int x)
{
    int  j = 0;
    int counter = 1;// 1~9個號碼
    int flag = 0;
    int total_number = 0;

    while(counter < 10)
    {
        for(j = 0 ; j <= 8; j++)
            if(sudoku[x][j] == counter)
            {
                flag = 1;
                continue;
            }

        if(flag == 0)//沒找到
        {
            total_number++;
            row[x][0] = total_number;//找出小正方形內有多少個空格
            row[x][total_number] = counter;//存入缺的號碼
        }
        counter++;
        flag = 0;
    }   
}

check_column.cpp

#include <stdio.h>
#include <stdlib.h>
#include "allfunction.h"

extern int column[9][10];
extern int sudoku[9][9];
void find_number_col(int y);

void check_column()
{
    int y;
    for(y = 0 ; y <= 8 ; y++)
        find_number_col(y);
}

void find_number_col(int y)
{
    int i = 0;
    int counter = 1;// 1~9個號碼
    int flag = 0;
    int total_number = 0;

    while(counter < 10)
    {
        for(i = 0 ; i <= 8; i++)
            if(sudoku[i][y] == counter)
            {
                flag = 1;
                continue;
            }

        if(flag == 0)//沒找到
        {
            total_number++;
            column[y][0] = total_number;//找出小正方形內有多少個空格
            column[y][total_number] = counter;//存入缺的號碼
        }
        counter++;
        flag = 0;
    }   
}

check_little_sqare.cpp

#include <stdio.h>
#include <stdlib.h>
#include "allfunction.h"
void find_number_squ(int x, int y);

extern int little_square[9][10];
extern int sudoku[9][9];

void check_little_square()
{
    int x, y;
    for(x = 0 ; x <= 6 ; x = x + 3)
        for(y = 0 ; y <= 6 ; y = y +3)
            find_number_squ(x, y);
}

void find_number_squ(int x, int y)
{
    int i = 0, j = 0;
    int counter = 1;// 1~9個號碼
    int flag = 0;
    int total_number = 0;

    while(counter < 10)
    {
        for(i = 0 ; i < 3 ; i++)
            for(j = 0 ; j < 3 ; j++)
                if(sudoku[x+i][y+j] == counter)
                {
                    flag = 1;
                    continue;
                }

        if(flag == 0)//沒找到
        {
            total_number++;
            little_square[x + y/3][0] = total_number;//找出小正方形內有多少個空格
            little_square[x + y/3][total_number] = counter;//存入缺的號碼
        }
        counter++;
        flag = 0;
    }   
}

find_mapping_row.cpp

#include <stdio.h>
#include <stdlib.h>
#include "allfunction.h"

extern int row[9][10];
extern int column[9][10];
extern int little_square[9][10];
extern int sudoku[9][9];

int find_mapping_row(int row_num, int round)
{
    int i, j;

    for(i = round ; i < 3 + round ; i++)
    {
        for(j = 1 ; j <= row[i][0] ; j++)
        {
            if(row_num == row[i][j])
            {
                return i;
            }
        }
    }
    return -1;
}

find_mapping_column.cpp

#include <stdio.h>
#include <stdlib.h>
#include "allfunction.h"

extern int row[9][10];
extern int column[9][10];
extern int little_square[9][10];
extern int sudoku[9][9];

int find_mapping_column(int column_num, int round)
{
    int i, j;

    round *= 3;//column每一回合round為加1, 但column的回合還是每3個一組(0 1 2), (3 4 5), (6 7 8)

    for(i = round ; i < 3 + round ; i++)
    {
        for(j = 1 ; j <= column[i][0] ; j++)
        {
            if(column_num == column[i][j])
            {
                return i;
            }
        }
    }
    return -1;
}

find_unique_element.cpp

#include <stdio.h>
#include <stdlib.h>
#include "allfunction.h"

extern int row[9][10];
extern int column[9][10];
extern int little_square[9][10];
extern int sudoku[9][9];

void find_unique_element()
{
    int x, y, z;

    for(x = 0 ; x < 9 ; x++)
    {
        if(row[x][0] == 1)
        {
            for(y = 0 ; y < 9 ; y++)
            {
                if(sudoku[x][y] == 0)
                {
                    sudoku[x][y] = row[x][1];
                    modify(x, y);
                    break;
                }
            }
        }
    }

    for(x = 0 ; x < 9 ; x++)
    {
        if(column[x][0] == 1)
        {
            for(y = 0 ; y < 9 ; y++)
            {
                if(sudoku[y][x] == 0)
                {
                    sudoku[y][x] = column[x][1];
                    modify(y, x);
                    break;
                }
            }
        }
    }

    for(z = 0 ; z < 9 ; z++)
    {
        if(little_square[z][0] == 1)
        {
            for(x = 0 ; x < 3 ; x++)
            {
                for(y = 0 ; y < 3 ; y++)
                {
                    if(sudoku[z/3*3 + x][z%3*3 + y] == 0)
                    {
                        sudoku[z/3*3 + x][z%3*3 + y] = little_square[z][1];
                        modify(z/3*3 + x, z%3*3 + y);
                        break;
                    }
                }           
            }       
        }
    }
}

findNumber_row_square.cpp

#include <stdio.h>
#include <stdlib.h>
#include "allfunction.h"

extern int row[9][10];
extern int column[9][10];
extern int little_square[9][10];
extern int sudoku[9][9];

int original_row;
int target_square;

void findNumber_row_square()
{
    //開始判斷, 先由最上方的3列開始  搭配小正方形
    int i, j;
    int round = 0;
    int row_major = 1;

    int number_counter[10] = {0};
    int number_mapping_square[10] = {0};

    while(round < 9)//回合數計數  每一回合+3
    {
        for(i = round ; i < 3 + round ; i++)
            for(j = 0 ; j < little_square[i][0] ; j++)
            {
                number_counter[little_square[i][j+1]]++;//對缺少的號碼出現次數做計數
                number_mapping_square[little_square[i][j+1]] = i;//判斷是屬於0~8哪一個小正形
            }

        for(i = 1 ; i < 10 ; i++)
        {
            if(number_counter[i] == 1)
            {
                target_square = number_mapping_square[i];
                original_row = find_mapping_row(i, round);

                int zero_counter = 0;
                for(j = 0 ; j < 3 ; j++)
                {
                    if(sudoku[original_row][target_square%3*3 + j] == 0)
                    {
                        zero_counter++;
                    }
                }

                if(zero_counter <= 2)
                {
                    numberOfZero(zero_counter, i, row_major);//引數為0個數量及需判斷可否寫入的號碼
                }
            }
        }
        for(i = 0 ; i < 10 ; i++)
        {
            number_counter[i] = 0;
            number_mapping_square[i] = 0;       
        }
        round += 3;
    }
}

findNumber_column_square.cpp

#include <stdio.h>
#include <stdlib.h>
#include "allfunction.h"

extern int row[9][10];
extern int column[9][10];
extern int little_square[9][10];
extern int sudoku[9][9];

int original_column;
extern int target_square;

void findNumber_column_square()
{
    //開始判斷, 先由最上方的3列開始  搭配小正方形
    int i, j;
    int round = 0;
    int column_major = 0;

    int number_counter[10] = {0};
    int number_mapping_square[10] = {0};

    while(round < 3)
    {
        for(i = round ; i < 9 ; i += 3)
            for(j = 0 ; j < little_square[i][0] ; j++)
            {
                number_counter[little_square[i][j+1]]++;//對缺少的號碼出現次數做計數 行是以(0 3 6)(1 4 7)(2 5 8)為分組
                number_mapping_square[little_square[i][j+1]] = i;//判斷是屬於0~8哪一個小正形
            }

        for(i = 1 ; i < 10 ; i++)
        {
            if(number_counter[i] == 1)
            {
                target_square = number_mapping_square[i];
                original_column = find_mapping_column(i, round);

                int zero_counter = 0;
                for(j = 0 ; j < 3 ; j++)
                {
                    if(sudoku[target_square/3*3 + j][original_column] == 0)
                    {
                        zero_counter++;
                    }
                }

                if(zero_counter <= 2)
                {
                    numberOfZero(zero_counter, i, column_major);//引數為0個數量及需判斷可否寫入的號碼
                }
            }
        }
        for(i = 0 ; i < 10 ; i++)
        {
            number_counter[i] = 0;
            number_mapping_square[i] = 0;       
        }
        round +=1;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include "allfunction.h"

extern int row[9][10];
extern int column[9][10];
extern int little_square[9][10];
extern int sudoku[9][9];

extern int original_column;
extern int original_row;
extern int target_square;

 

numberOfZero.cpp

void numberOfZero(int zero_counter, int number_check, int row_or_column)
{
    int i;
    int temp_1 = 0, temp_2 = 0; //記憶兩個零時, 其x座標
    int counter = 0;
    int flag = 0;

    if(row_or_column == 1)//針對row
    {
        switch(zero_counter)
        {
            case 2:
                for(i = 0 ; i < 3 ; i++)
                {
                    if(sudoku[original_row][target_square%3*3 + i] == 0)
                    {
                        counter++;
                        if(counter ==1)
                            temp_1 = target_square%3*3 + i;
                        else
                            temp_2 = target_square%3*3 + i;
                    }
                }
               
                for(i = 0 ; i < 9 ; i++)
                {
                    if(sudoku[i][temp_1] == number_check)//對映的行是否已存在要寫入的號碼, 有的話存另一個零元素的行內
                    {
                        sudoku[original_row][temp_2] = number_check;
                        modify(original_row, temp_2);//x y座標
                        flag = 1;
                        break;
                    }
                }
               
                for(i = 0 ; i < 9 && flag == 0 ; i++)
                {
                    if(sudoku[i][temp_2] == number_check)
                    {
                        sudoku[original_row][temp_1] = number_check;
                        modify(original_row, temp_1);//x y座標
                        break;                   
                    }
                }
                break;

            case 1:
                for(i = 0 ; i < 3 ; i++)
                {
                    if(sudoku[original_row][target_square%3*3 + i] == 0)
                    {
                        sudoku[original_row][target_square%3*3 + i] = number_check;
                        modify(original_row, target_square%3*3 + i);//x y座標
                        break;
                    }
                }
                break;
               
            default:
                {
                    printf("error");
                }
        }
    }
    else//針對column
    {
        switch(zero_counter)
        {
            case 2:
                for(i = 0 ; i < 3 ; i++)
                {
                    if(sudoku[target_square/3*3 + i][original_column] == 0)
                    {
                        counter++;
                        if(counter ==1)
                            temp_1 = target_square/3*3 + i;
                        else
                            temp_2 = target_square/3*3 + i;
                    }
                }
               
                for(i = 0 ; i < 9 ; i++)
                {
                    if(sudoku[temp_1][i] == number_check)//對映的列是否已存在要寫入的號碼, 有的話存另一個零元素的列內
                    {
                        sudoku[temp_2][original_column] = number_check;
                        modify(temp_2, original_column);//x y座標
                        flag = 1;
                        break;
                    }
                }
               
                for(i = 0 ; i < 9 && flag == 0 ; i++)
                {
                    if(sudoku[temp_2][i] == number_check)
                    {
                        sudoku[temp_1][original_column]= number_check;
                        modify(temp_1, original_column);//x y座標
                        break;                   
                    }
                }
                break;

            case 1:
                for(i = 0 ; i < 3 ; i++)
                {
                    if(sudoku[target_square/3*3 + i][original_column] == 0)
                    {
                        sudoku[target_square/3*3 + i][original_column] = number_check;
                        modify(target_square/3*3 + i, original_column);//x y座標
                        break;
                    }
                }
                break;   

            default:
                {
                    printf("error");
                }
        }
    }
}

try_and_error.cpp的話一般網路上都可以找得的暴力法解題, 所以就不提供了...