闲暇的时候写的小程序,从map输入数独的题目后自动计算。

#include "stdafx.h"

#include <vector>
#include <map>
#include <iostream>
#include <assert.h>

// 获取行index
std::vector<int> askRow(int index)
{
    std::vector<int> rownum;

    auto rowindex = index / 10;
    for (int i = 0; i < 9; i++)
    {
        rownum.push_back(rowindex * 10 + i);
    }
    return rownum;
}

// 获取列index
std::vector<int> askCol(int index)
{
    std::vector<int> colnum;

    auto colindex = index % 10;
    for (int i = 0; i < 9; i++)
    {
        colnum.push_back(i * 10 + colindex);
    }
    return colnum;
}

// 获取宫index
std::vector<int> askBlock(int index)
{
    std::vector<std::vector<int>> blocknum = {
        {0,1,2,10,11,12,20,21,22},
        {3,4,5,13,14,15,23,24,25},
        {6,7,8,16,17,18,26,27,28},
        {30,31,32,40,41,42,50,51,52},
        {33,34,35,43,44,45,53,54,55},
        {36,37,38,46,47,48,56,57,58},
        {60,61,62,70,71,72,80,81,82},
        {63,64,65,73,74,75,83,84,85},
        {66,67,68,76,77,78,86,87,88},
    };

    for (const std::vector<int>& item : blocknum)
    {
        if (item.end() != std::find(item.begin(), item.end(), index))
            return item;
    }
    assert(false);
    return std::vector<int>();
}

// 检查冲突(入参为格子的值,而非index)
bool check(const std::vector<char>& block)
{
    char checknum[9] = { 0 };
    for (auto item : block)
    {
        if (item == 0)
            continue;

        // 同一位置已经有值了
        if (checknum[item - 1] == 1)
            return false;

        // 占位
        checknum[item - 1] = 1;
    }
    return true;
}

// 获取一个检查数据
std::vector<char> getBlock(const std::vector<char>& table, const std::vector<int>& block)
{
    assert(block.size() == 9);

    std::vector<char> blockData;
    for (size_t i = 0; i < block.size(); ++i)
    {
        blockData.push_back(table.at(block.at(i)));
    }
    return blockData;
}

bool calcBackup(std::vector<char>& table, std::vector<std::pair<char, std::vector<char>>>& backupmap)
{
    // 侯选数
    backupmap.clear();
    for (int index = 0; index < 90; ++index)
    {
        if (index % 10 == 9)
            continue;

        if (table.at(index) > 0)
            continue;

        // 获取三种类型的数据集
        auto blockRow = askRow(index);
        auto blcokDataRow = getBlock(table, blockRow);
        auto blockCol = askCol(index);
        auto blcokDataCol = getBlock(table, blockCol);
        auto block = askBlock(index);
        auto blcokData = getBlock(table, block);

        // 获取每个格子的候选数
        std::vector<char> vec;
        for (int i = 1; i < 10; i++)
        {
            if (blcokDataRow.end() == std::find(blcokDataRow.begin(), blcokDataRow.end(), i) &&
                blcokDataCol.end() == std::find(blcokDataCol.begin(), blcokDataCol.end(), i) &&
                blcokData.end() == std::find(blcokData.begin(), blcokData.end(), i))
                vec.push_back(i);
        }

        // 如果只有一个候选数,则重算
        assert(vec.size() > 0);
        if (vec.size() == 1)
        {
            table.at(index) = vec[0];
            return true;
        }
        backupmap.push_back(std::make_pair(index, vec));
    }
    return false;
}

// 递归,一个个的试
bool calc(std::vector<char>& table, const std::vector<std::pair<char, std::vector<char>>>& backupmap, int num, int index)
{
    int currentIndex = backupmap.at(num).first;
    table.at(currentIndex) = backupmap.at(num).second.at(index);

    auto blockRow = askRow(currentIndex);
    auto blockCol = askCol(currentIndex);
    auto block = askBlock(currentIndex);
    if (check(getBlock(table, block)) && check(getBlock(table, blockRow)) && check(getBlock(table, blockCol)))
    {
        if (num >= backupmap.size() - 1)
        {
            // 计算到最后一格,出现全部备选数据相匹配的情况
            return true;
        }
        else
        {
            // 当前格子匹配正常,继续计算下一个
            for (int index = 0; index < backupmap.at(num + 1).second.size(); ++index)
            {
                if (calc(table, backupmap, num + 1, index))
                {
                    return true;
                }
            }
        }
    }
    table.at(currentIndex) = 0;
    return false;
}

void prinfTable(const std::vector<char>& table)
{
    for (int row = 0; row < 9; ++row)
    {
        if (row % 3 == 0)
        {
            printf("------------------------------------------ \n");
        }

        printf("%4d%4d%4d | %4d%4d%4d | %4d%4d%4d \n", table[row * 10], table[row * 10 + 1], table[row * 10 + 2],
            table[row * 10 + 3], table[row * 10 + 4], table[row * 10 + 5],
            table[row * 10 + 6], table[row * 10 + 7], table[row * 10 + 8]);
    }
}

bool fill(const std::map<char, char>& origin, std::vector<char>& table)
{
    for (auto item : origin)
    {
        table.at(item.first) = item.second;
    }

    int i = 0;
    std::vector<std::pair<char, std::vector<char>>> backupmap;
    while (calcBackup(table, backupmap))
    {
        if (i++ > 90)
            break;
    }

    if (backupmap.size() > 0)
    {
        for (int index = 0; index < backupmap.front().second.size(); ++index)
        {
            if (calc(table, backupmap, 0, index))
            {
                return true;
            }
        }
        return false;
    }
    return true;
}

int main()
{
    std::map<char, char> origin;
    origin.insert(std::make_pair(12, 1));
    origin.insert(std::make_pair(15, 9));
    origin.insert(std::make_pair(18, 7));
    origin.insert(std::make_pair(20, 7));
    origin.insert(std::make_pair(22, 9));
    origin.insert(std::make_pair(23, 4));
    origin.insert(std::make_pair(27, 2));
    origin.insert(std::make_pair(28, 3));
    origin.insert(std::make_pair(32, 4));
    origin.insert(std::make_pair(33, 7));
    origin.insert(std::make_pair(36, 6));
    origin.insert(std::make_pair(43, 1));
    origin.insert(std::make_pair(44, 5));
    origin.insert(std::make_pair(47, 8));
    origin.insert(std::make_pair(55, 4));
    origin.insert(std::make_pair(61, 2));
    origin.insert(std::make_pair(66, 7));
    origin.insert(std::make_pair(67, 3));
    origin.insert(std::make_pair(70, 5));
    origin.insert(std::make_pair(71, 8));
    origin.insert(std::make_pair(74, 1));
    origin.insert(std::make_pair(78, 2));
    origin.insert(std::make_pair(84, 4));
    origin.insert(std::make_pair(85, 3));

    std::vector<char> table(90, 0);
    if (fill(origin, table))
    {
        std::cout << "happy end" << std::endl;
        prinfTable(table);
    }
    else
    {
        std::cout << "sorry" << std::endl;
    }

    getchar();
    return 0;
}