算数独
闲暇的时候写的小程序，从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;
}