回溯法+约束编程-LeetCode37（数独扫雷问题、Tuple使用）
回溯法+约束编程-LeetCode37（数独扫雷问题、Tuple使用）
作者：TeddyZhang，公众号：算法工程师之路
回溯问题：LeetCode #37
1
编程题
【STL中的Tuple容器】
在Python中，大家都知道tuple这个概念，是一个只读的元素容器，容器内的元素数据类型可以不同，而在CPP中大部分的容器只能储存相同数据类型的数据，而std::pair函数是为数不多的可以将两个不同类型的值放到一起。我们今天说的tuple是std::pair的推广，表示固定大小的异类值的汇集。 std::tuple是C++11标准开始提出的，其有很多用途，比如一个函数如果拥有多个不同类型的返回值，就可以直接返回一个tuple.不用再像以前一样，定义一个class或者struct保存结果进行返回那么麻烦了！ 其使用的重要函数有：
- std::make_tuple 创建一个tuple对象
- std::tie 创建左值引用的tuple，或将tuple解包为独立对象
- std::get(std::tuple) 元组式访问指定的元素
- 结构化绑定（重要，效率最高），避免使用std::tie函数
使用Demo示例：
#include <tuple>
#include <iostream>
#include <string>
#include <stdexcept>
std::tuple<double, char, std::string> get_student(int id)
{
if (id == ) return std::make_tuple(3.8, 'A', "Lisa Simpson");
if (id == ) return std::make_tuple(2.9, 'C', "Milhouse Van Houten");
if (id == ) return std::make_tuple(1.7, 'D', "Ralph Wiggum");
throw std::invalid_argument("id");
}
int main()
{
auto student0 = get_student();
std::cout << "ID: 0, "
<< "GPA: " << std::get<>(student0) << ", "
<< "grade: " << std::get<>(student0) << ", "
<< "name: " << std::get<>(student0) << '\n';
double gpa1;
char grade1;
std::string name1;
std::tie(gpa1, grade1, name1) = get_student();
std::cout << "ID: 1, "
<< "GPA: " << gpa1 << ", "
<< "grade: " << grade1 << ", "
<< "name: " << name1 << '\n';
// C++17 结构化绑定, 不用定义变量，也不用使用tie函数
auto [ gpa2, grade2, name2 ] = get_student();
std::cout << "ID: 2, "
<< "GPA: " << gpa2 << ", "
<< "grade: " << grade2 << ", "
<< "name: " << name2 << '\n';
}【LeetCode #37】解数独（Hard）
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
答案被标成红色。
Note: 给定的数独序列只包含数字 1-9 和字符 '.' 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的
解题思路：
官方的解答已经很好很清晰了，希望大家可以去看一下，主要思想为约束编程和回溯！ 约束编程意思是当我们向未知位置填数时，就需要排除其所在行或者所在列以及所在子方格对该数字的使用！在程序中我们分别使用col_, row_, block_三个二维数组记录数字是否被使用，即如果数字使用了，所对应的位置为true。
回溯法意思是我们需要对每个未知位置进行递归求解，使用数字1-9依次进行尝试，如果在col_, row_, block_用到了该数字，则直接continue，否则我们从这个数字开始递归求解，如果不满足条件，则回溯，并初始化相应的状态，换另外一个数字进行递归！
我突然发现这个题目和某大厂的秋招题目很类似，那是一个扫雷问题，貌似是根据已知数字要找出几种放置雷的方式！不知大家有没有印象了！类似的题目还有洛谷P2327！
C++代码（带注解）
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
for (auto i = ; i < ; ++i) {
for (auto j = ; j < ; ++j) {
auto ch = board[i][j];
if (ch == '.') {
spaces_.emplace_back(i, j); // space_用于储存未知位置的行和列
} else {
const auto b = * (i / ) + (j / );
ch -= '1';
// 如果数独中有对应数字，则其所在的行，列，block均标记为true，即不可以再使用
row_[i][ch] = true;
col_[j][ch] = true;
block_[b][ch] = true;
}
}
}
solve(board, );
}
bool solve(vector<vector<char>>& board, const int pos) {
if (pos < spaces_.size()) {
//int x_, y_;
//std::tie (x_, y_) = spaces_.at(pos);
const auto& [x_, y_] = spaces_.at(pos);
const auto b = * (x_ / ) + (y_ / );
for (auto i = ; i < ; ++i) {
if (row_[x_][i] || col_[y_][i] || block_[b][i])
continue; // 如果数字使用过了，直接返回，否则使用该数字进行递归
board[x_][y_] = '1' + i;
row_[x_][i] = true;
col_[y_][i] = true;
block_[b][i] = true; // 使用i，并进行标记
if (solve(board, pos + )) { // 递归到下一个未知位置
return true;
}
board[x_][y_] = '.'; // 如果不满足条件，则回溯，恢复为原来的状态
row_[x_][i] = false;
col_[y_][i] = false;
block_[b][i] = false;
}
return false;
}
return true;
}
private:
bool row_[][] = {};
bool col_[][] = {};
bool block_[][] = {};
vector<tuple<int, int>> spaces_ = {};
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sudoku-solver
完