这两天突然对数独产生了浓厚的兴趣，思考了一下如何用程序来解决数独问题。

解数独使用的方法为回溯法，按照顺序执行：

1. 若已经填满，输出结果
2. 对于没有填写数字的空格，检测在数独规则之下有哪些数字可填
3. 任意填入一个可能的数字，对下一个未填的空格执行步骤1-4
4. 当可填数字为空时说明填法出错，返回2选取另一个可填的数字

这样就获得了数独的解

其实人类解数独大概也是这样一个试错的过程，只不过人类不会死板地一切按照步骤观察并执行，而是进行模糊化的观察，这大概就是大部分人类解不出来高难度数独的原因吧233.

 

好的上代码，这里刻意选择了一个有多解的情况，当然了，正规的数独题目是单解的

python

#!/usr/bin/env python3
# -*-coding:utf-8 -*-

def canWrite(n,position,sudoku):
    x=position%9
    y=position//9
    for i in range(9):
        if sudoku[y*9+i]==n:
            return False
    for j in range(9):
        if sudoku[j*9+x]==n:
            return False
    b_x=(x//3)*3
    b_y=(y//3)*3
    for k in range(3):
        for i in range(3):
            if sudoku[(b_y+k)*9+b_x+i]==n:
                return False
    return True

def tryInsert(position,sudoku,resultNum):
    if position==81:
        resultNum[0]+=1
        showSudoku(sudoku)
        print('='*17)
        print('found %d answer(s)'%(resultNum[0]))
        print('='*17+'\n\n')
        return 1
    if sudoku[position]==0:
        for i in range(1,10):
            if canWrite(i,position,sudoku):
                sudoku[position]=i
                tryInsert(position+1,sudoku,resultNum)
                sudoku[position]=0
    if sudoku[position]!=0:
        tryInsert(position+1,sudoku,resultNum)
    return 0

    
def showSudoku(sudoku):
    print('='*17)
    for i in range(81):
        print(sudoku[i],end=' ')
        if (i+1)%9 == 0:
            print('')
    print('='*17)
        
if __name__ == '__main__':
    sudoku=[
        5,0,2,6,0,0,3,0,0,
        0,0,0,0,0,8,0,1,0,
        0,0,0,2,0,0,0,6,8,
        2,4,0,0,0,0,0,0,9,
        0,0,7,0,0,0,1,3,0,
        6,0,0,0,0,0,8,0,0,
        0,5,6,0,1,0,0,0,0,
        9,0,0,0,0,0,6,0,1,
        0,7,0,0,0,9,0,4,2
    ]
    showSudoku(sudoku)
    print('')
    resultNum=[0]
    tryInsert(0,sudoku,resultNum)
    print('finished. found %d answer(s)'%(resultNum[0]))

 

C++

#include<iostream>
using namespace std;

int sudoku[81] = {
    5,0,2,6,0,0,3,0,0,
    0,0,0,0,0,8,0,1,0,
    0,0,0,2,0,0,0,6,8,
    2,4,0,0,0,0,0,0,9,
    0,0,7,0,0,0,1,3,0,
    6,0,0,0,0,0,8,0,0,
    0,5,6,0,1,0,0,0,0,
    9,0,0,0,0,0,6,0,1,
    0,7,0,0,0,9,0,4,2
};

bool canWrite(int n,int position,int sudoku[81]);
int tryInsert(int position, int sudoku[81],int resultNum[1]);
void showSudoku(int sudoku[81]);

int main()
{
    int resultNum[1] = { 0 };
    tryInsert(0, sudoku, resultNum);
    cout << endl << "finished. found" << resultNum[0] << "answer(s)" << endl;
    system("pause");
    return 0;
}

bool canWrite(int n,int position, int sudoku[81])
{
    int x = position % 9;
    int y = position / 9;
    for (int i = 0; i < 9; i++)
    {
        if (sudoku[y * 9 + i] == n)
            return false;
    }
    for (int j = 0; j < 9; j++)
    {
        if (sudoku[j * 9 + x] == n)
            return false;
    }
    int p_x = (x / 3) * 3;
    int p_y = (y / 3) * 3;
    for (int k = 0; k < 3; k++)
    {
        for (int i = 0; i < 3; i++)
        {
            if (sudoku[(p_y + k) * 9 + p_x + i] == n)
                return false;
        }
    }
    return true;
}

int tryInsert(int position, int sudoku[81] ,int resultNum[1])
{
    if (position == 81)
    {
        resultNum[0]++;
        showSudoku(sudoku);
        cout << "=================" << endl;
        cout << "found " << resultNum[0] << " answer(s)" << endl;
        cout << "=================" << endl << endl;
        return 0;
    }
    if (sudoku[position] == 0)
    {
        for (int i = 1; i < 10; i++)
        {
            if (canWrite(i, position, sudoku))
            {
                sudoku[position] = i;
                tryInsert(position + 1, sudoku, resultNum);
                sudoku[position] = 0;
            }
        }
    }
    else
    {
        tryInsert(position + 1, sudoku, resultNum);
    }
    return 0;
}

void showSudoku(int sudoku[81])
{
    cout << "=================" << endl;
    for (int i = 0; i < 81; i++)
    {
        cout << sudoku[i] << " ";
        if ((i + 1) % 9 == 0)
            cout << endl;
    }
    cout << "=================" << endl;
}