回溯法

回溯法

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<set>
#include<map>
#include<list>
#include<cctype>
#include<algorithm>
#include<thread>
#include<mutex>
#include<sstream>
using namespace std;
bool isValid(vector<vector<int>> arr, int i, int j, int obj)
{
    //判断所在行
    for (int k = 0; k < 9; k++)
    {
        if (arr[i][k] == obj)
            return false;
    }
    //判断所在列
    for (int k = 0; k < 9; k++)
    {
        if (arr[k][j] == obj)
            return false;
    }
    //判断所在单元格
    int Lrow = i / 3 * 3;
    int Lcol = j / 3 * 3;
    for (int row = Lrow; row < Lrow + 3; row++)
        for (int col = Lcol; col < Lcol + 3; col++)
        {
            if (arr[row][col] == obj)
                return false;
        }

    //成功
    return true;
}
bool Find(vector<vector<int>> arr, int &row, int &col)
{
    int i, j;
    while (row < 9 && col < 9)
    {
        if (arr[row][col] == 0)
            return true;
        else
        {
            col++;
            if (col == 9)
            {
                col = 0;
                row++;
            }
        }
    }
    return false;
}
bool func(vector<vector<int>> &arr, int row, int col)
{
    int obj;
    bool res = false;

    if (col > 8)
    {
        col = col % 9;
        row++;
    }

    if (!Find(arr, row, col))
        return true;

    //尝试赋值
    for (obj = 1; obj <= 9; obj++)
    {
        if (isValid(arr, row, col, obj))
        {
            arr[row][col] = obj;
            res = func(arr, row, col+1);
            if (res == false)
                continue;
            else
                return true;
        }
    }
    if (res == false)
    {
        arr[row][col] = 0;
        return false;
    }        
}

int main()
{
    vector<vector<int>> arr(9, vector<int>(9, 0));

    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            cin >> arr[i][j];
    func(arr, 0, 0);

    cout << endl;
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
            cout << arr[i][j] << " ";
        cout << endl;
    }

    return 0;
}