(C++回溯算法)微信小程序“开局托儿所”游戏

问题描述

给定一个矩阵$\mathbf{A}=(a_{ij}{)}_{m\times n}$，其中 a i j ∈ { 1 , 2 , ⋯   , 9 } a_{ij}\in\{1,2,\cdots,9\} aij​∈{1,2,⋯,9}，且满足$\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}$被10整除。玩家每次操作需要选择$\mathbf{A}$中某个所有非空元素之和为10的子矩阵，并将其中所有的元素都标记为空。求按何种顺序消除能将$\mathbf{A}$中所有的元素都标记为空，若存在则返回该解决方案，否则返回空列表。

固定顺序求解

代码

nursery_game.h

#ifndef NURSERY_GAME
#define NURSERY_GAME
#include <vector>
#include <stdint.h>
struct Operate {
	uint8_t x1, y1, x2, y2;
	Operate() {}
	Operate(uint8_t i1, uint8_t j1, uint8_t i2, uint8_t j2):x1(i1), y1(j1), x2(i2), y2(j2) {}
};
// 顺序求解，从左上角开始寻找解决方案
// A: 矩阵A数据，逐行排列
// m: 矩阵A行数
// n: 矩阵A列数
// 注意: m * n < 256
std::vector<Operate> sequentialSolve(int8_t *A, uint8_t m, uint8_t n);
// 逆序求解，从右下角开始寻找解决方案
// A: 矩阵A数据，逐行排列
// m: 矩阵A行数
// n: 矩阵A列数
// 注意: m * n < 256
std::vector<Operate> inverseSolve(int8_t *A, uint8_t m, uint8_t n);
#endif

nursery_game.cpp

#include "nursery_game.h"
#include <utility>
using std::vector;
using std::move;

// #define RECOVER_DATA // 若希望不改变A的值请解开本行注释

#define handle(x1,y1,x2_start,tag) for(uint8_t x2=x2_start;x2<m;){uint8_t ie=x2*n;for(uint8_t y2=y1;y2<n;y2++){uint8_t sum=0;for(uint8_t i=is;i<=ie;i+=n)for(uint8_t j=i+y1,e=i+y2;j<=e;j++){int8_t t=A[j];if(t>0&&(sum+=t)>10)goto tag;}if(sum!=10)continue;vector<uint8_t> set;for(uint8_t i=is;i<=ie;i+=n)for(uint8_t j=i+y1,e=i+y2;j<=e;j++){int8_t t=A[j];if(t>0){A[j]=-t;set.push_back(j);}}R.emplace_back(x1,y1,x2,y2);unRemoveCount-=set.size();posSet.push_back(move(set));goto F_push;}tag:x2++;}

vector<Operate> sequentialSolve(int8_t *A, uint8_t m, uint8_t n) {
	vector<Operate> R;
	vector<vector<uint8_t>> posSet;
	Operate op;
	uint8_t unRemoveCount = m * n, is;
F_push:
	if (!unRemoveCount) {
#ifdef RECOVER_DATA
		int8_t *p = A + m * n;
		do {
			--p;
			*p = -*p;
		} while (p != A);
#endif
		return move(R);
	}
	is = 0;
	for (uint8_t x1 = 0; x1 < m; x1++, is += n)
		for (uint8_t y1 = 0; y1 < n; y1++)
			handle(x1, y1, x1, F1)
F_pop:
	if (R.empty()) return {};
	op = R.back();
	R.pop_back();
	unRemoveCount += posSet.back().size();
	for (auto pos : posSet.back()) A[pos] = -A[pos];
	posSet.pop_back();
	is = op.x1 * n;
	handle(op.x1, op.y1, op.x2 + 1, F2)
	for (uint8_t y1 = op.y1 + 1; y1 < n; y1++) handle(op.x1, y1, op.x1, F3)
	for (uint8_t x1 = op.x1 + 1; x1 < m; x1++) {
		is += n;
		for (uint8_t y1 = 0; y1 < n; y1++) handle(x1, y1, x1, F4)
	}
	goto F_pop;
}

vector<Operate> inverseSolve(int8_t *A, uint8_t m, uint8_t n) {
	vector<Operate> R;
	vector<vector<uint8_t>> posSet;
	Operate op;
	uint8_t unRemoveCount = m * n, is, m1 = m - 1, n1 = n - 1;
F_push:
	if (!unRemoveCount) {
#ifdef RECOVER_DATA
		int8_t *p = A + m * n;
		do {
			p--;
			*p = -*p;
		} while (p != A);
#endif
		return move(R);
	}
	is = m * n;
	for (uint8_t x1 = m1; x1 >= 0; x1--) {
		is -= n;
		for (uint8_t y1 = n1; y1 >= 0; y1--) handle(x1, y1, x1, F1)
	}
F_pop:
	if (R.empty()) return {};
	op = R.back();
	R.pop_back();
	unRemoveCount += posSet.back().size();
	for (auto pos : posSet.back()) A[pos] = -A[pos];
	posSet.pop_back();
	is = op.x1 * n;
	handle(op.x1, op.y1, op.x2 - 1, F2)
	for (uint8_t y1 = op.y1 - 1; y1 >= 0; y1--) handle(op.x1, y1, op.x1, F3)
	for (uint8_t x1 = op.x1 - 1; x1 >= 0; x1--) {
		is -= n;
		for (uint8_t y1 = n1; y1 >= 0; y1--) handle(x1, y1, x1, F4)
	}
	goto F_pop;
}

#undef handle

test.cpp

#include "nursery_game.h"
#include <stdio.h>
using namespace std;

int main() {
	int8_t data[] = { 4,7,3,3,6,5,4,4,2,1,8,4,2,2,2,6,1,2,3,2,3,2,7,1,2,8,1,3,1,6,4,5,4,5,1,4,2,2,2,3,8,3,3,1,9,2,3,3,1,1,4,4,1,9,3,7,1,3,2,5,3,1,1,5 };
	vector<Operate> r(sequentialSolve(data, 8, 8));
	for (auto op : r) printf("(%d,%d) (%d,%d)\n", op.x1, op.y1, op.x2, op.y2);
	return 0;
}

测试结果

(0,1) (0,2)
(0,0) (2,1)
(0,0) (3,1)
(0,7) (1,7)
(1,3) (1,6)
(0,4) (3,4)
(1,3) (5,3)
(0,3) (2,5)
(0,3) (4,5)
(0,4) (6,4)
(2,0) (2,6)
(0,2) (4,2)
(0,2) (4,6)
(5,0) (7,0)
(5,7) (6,7)
(6,0) (7,2)
(5,0) (6,3)
(0,1) (5,6)
(0,5) (7,5)
(4,0) (6,7)
(3,7) (7,7)
(0,0) (7,7)

操作过程：

按数字大小求解

仔细观察该游戏，我们容易发现往往大数更难以消除，因此我们可以优先消除大数，这样相对来说更容易找到解决方案。

代码

nursery_game.h

#ifndef NURSERY_GAME
#define NURSERY_GAME

// ……
// 固定顺序代码

// 按数字大小的顺序求解
// A: 矩阵A数据，逐行排列
// m: 矩阵A行数
// n: 矩阵A列数
// 注意: m, n < 17
std::vector<Operate> solve(int8_t *A, uint8_t m, uint8_t n);
#endif

nursery_game.cpp

// ……
// 固定顺序代码

#include <unordered_set>
using std::unordered_set;

struct PosNode {
	uint8_t pos, i, j;
	PosNode *next, *pre;
	PosNode():next(nullptr), pre(nullptr) {}
	PosNode(uint8_t p, uint8_t x, uint8_t y, PosNode *parent):pos(p), i(x), j(y), next(nullptr), pre(parent) {}
};

#define Handle(nodeStart,num,tag) for(PosNode*node1=nodeStart;node1;){uint8_t i1,i2,j1,j2;if(i>node1->i){i1=node1->i;i2=i;}else{i1=i;i2=node1->i;}if(j>node1->j){j1=node1->j;j2=j;}else{j1=j;j2=node1->j;}uint16_t key=i1<<12|j1<<8|i2<<4|j2;if(calculated.find(key)==calculated.end()&&pushed->find(key)==pushed->end()){calculated.insert(key);vector<uint8_t>posSet;uint8_t k=0;for(uint8_t i=i1*n,ie=i2*n;i<=ie;i+=n)for(uint8_t j=i+j1,e=i+j2;j<=e;j++){int8_t a=A[j];if(a>0){if((k+=a)>10)goto tag;posSet.push_back(j);}}if(k<10)continue;R.emplace_back(i1,j1,i2,j2);for(auto pos:posSet){A[pos]=-A[pos];node=posToNode[pos];if(!(node->pre->next=node->next))posesEnd[pos]=node->pre;}count-=posSet.size();history.push_back(move(posSet));pushed->insert(key);historyPushed.push_back(pushed);pushed=new unordered_set<uint16_t>;goto F_push;}tag:node1=node1->next;}
#define handle(num,tag) Handle(poses[num]->next,num,tag)
#define handleSame(num,tag) Handle(node->next,num,tag)

vector<Operate> solve(int8_t *A, uint8_t m, uint8_t n) {
	uint8_t N = m * n, count = N;
	PosNode *poses[10], *posesEnd[10], **posToNode = new PosNode * [N];
	for (uint8_t i = 1; i < 10; i++) poses[i] = posesEnd[i] = new PosNode;
	// 在这里遍历的时候还可以判断所有数字的总和是否被10整除，若不然可直接返回。
	// 因为在游戏中不存在不整除的情况，所以没加上这个判断条件。
	for (uint8_t i = 0, p = 0; i < m; i++)
		for (uint8_t j = 0; j < n; j++, p++) {
			PosNode *&node = posesEnd[A[p]];
			posToNode[p] = node = node->next = new PosNode(p, i, j, node);
		}
	vector<Operate> R;
	vector<vector<uint8_t>> history;
	unordered_set<uint16_t> calculated;
	vector<unordered_set<uint16_t> *> historyPushed;
	unordered_set<uint16_t> *pushed = new unordered_set<uint16_t>;
F_push:
	if (!count) {
		PosNode **p = posToNode + N;
		do delete *--p; while (p != posToNode);
		delete[] posToNode;
		p = poses + 9;
		do delete *p; while (--p != poses);
		delete pushed;
		for (auto p : historyPushed) delete p;
#ifdef RECOVER_DATA
		int8_t *q = A + N;
		do {
			q--;
			*q = -*q;
		} while (q != A);
#endif
		return move(R);
	}
	calculated.clear();
	for (PosNode *node = poses[9]->next; node; node = node->next) {
		uint8_t i = node->i, j = node->j;
		handle(1, F1)
	}
	for (PosNode *node = poses[8]->next; node; node = node->next) {
		uint8_t i = node->i, j = node->j;
		handle(2, F2)
		handle(1, F3)
	}
	for (PosNode *node = poses[7]->next; node; node = node->next) {
		uint8_t i = node->i, j = node->j;
		handle(3, F4)
		handle(2, F5)
		handle(1, F6)
	}
	for (PosNode *node = poses[6]->next; node; node = node->next) {
		uint8_t i = node->i, j = node->j;
		handle(4, F7)
		handle(3, F8)
		handle(2, F9)
		handle(1, F10)
	}
	for (PosNode *node = poses[5]->next; node; node = node->next) {
		uint8_t i = node->i, j = node->j;
		handleSame(5, F11)
		handle(4, F12)
		handle(3, F13)
		handle(2, F14)
		handle(1, F15)
	}
	for (PosNode *node = poses[4]->next; node; node = node->next) {
		uint8_t i = node->i, j = node->j;
		handleSame(4, F16)
		handle(3, F17)
		handle(2, F18)
		handle(1, F19)
	}
	for (PosNode *node = poses[3]->next; node; node = node->next) {
		uint8_t i = node->i, j = node->j;
		handleSame(3, F20)
		handle(2, F21)
		handle(1, F22)
	}
	for (PosNode *node = poses[2]->next; node; node = node->next) {
		uint8_t i = node->i, j = node->j;
		handleSame(2, F23)
		handle(1, F24)
	}
	for (PosNode *node = poses[1]->next; node; node = node->next) {
		uint8_t i = node->i, j = node->j;
		handleSame(1, F25)
	}
	if (R.empty()) {
		PosNode **p = posToNode + N;
		do delete *--p; while (p != posToNode);
		delete[] posToNode;
		p = poses + 9;
		do delete *p; while (--p != poses);
		delete pushed;
		for (auto p : historyPushed) delete p;
		return {};
	}
	R.pop_back();
	count += history.back().size();
	for (auto pos : history.back()) {
		PosNode *node = posToNode[pos], *&nodeEnd = posesEnd[A[pos] = -A[pos]];
		node->next = nullptr;
		node->pre = nodeEnd;
		nodeEnd = nodeEnd->next = node;
	}
	history.pop_back();
	delete pushed;
	pushed = historyPushed.back();
	historyPushed.pop_back();
	goto F_push;
}

test.cpp

#include "nursery_game.h"
#include <stdio.h>
using namespace std;

int main() {
	int8_t data[] = { 1,2,1,6,5,7,5,1,7,2,6,1,1,8,2,1,9,1,1,4,4,2,4,1,2,3,7,3,3,4,2,1,2,9,1,7,4,4,2,2,4,2,4,8,4,7,1,1,2,1,1,1,1,4,4,1,4,4,1,1,7,1,7,1 };
	vector<Operate> r(solve(data, 8, 8));
	for (auto op : r) printf("(%d,%d) (%d,%d)\n", op.x1, op.y1, op.x2, op.y2);
	return 0;
}

测试结果

(2,0) (2,1)
(4,1) (4,2)
(1,5) (1,6)
(5,3) (7,3)
(3,1) (3,2)
(3,3) (4,3)
(4,3) (4,6)
(6,2) (7,4)
(0,0) (0,3)
(0,4) (2,4)
(2,3) (2,6)
(1,1) (4,3)
(2,5) (4,7)
(0,3) (3,5)
(1,0) (3,7)
(0,6) (6,6)
(4,6) (7,7)
(6,1) (7,6)
(4,1) (6,4)
(5,0) (7,0)
(0,0) (7,7)

操作过程：

而经过测试，无论是顺序遍历还是逆序遍历在此案例中均耗时较长，但按元素大小遍历并非最优求解算法，如：

$$\mathbf{A}=\left(\begin{array}{cccccccc}2& 3& 2& 3& 2& 1& 7& 1\\ 6& 2& 2& 4& 1& 2& 3& 9\\ 4& 2& 1& 3& 3& 2& 3& 2\\ 1& 7& 7& 3& 4& 2& 2& 2\\ 2& 1& 7& 2& 1& 8& 1& 1\\ 2& 5& 5& 3& 4& 3& 6& 3\\ 8& 9& 1& 4& 2& 4& 6& 2\\ 2& 3& 4& 1& 8& 1& 1& 2\end{array}\right)$$

此时，顺序遍历比按大小遍历耗时更短。因此选择求解方法时需要根据具体案例选择不同的方法，具体而言可通过多线程等方式实现最优的求解时间。