Futoshiki Puzzle

Futoshiki Puzzle

文章目录

• • 1 简介
  • 2 Forward Checking 算法
  • • 2.1 简介
    • 2.2 Pseudo-Code
  • 3 GAC 算法
  • • 3.1 简介
    • 3.2 Pseudo-Code
  • 4 MRV启发函数
  • 5 Futoshiki 的限制分析
  • 6 附录
  • • 6.1 FC Algorithm
    • 6.2 GAC Algorithm

1 简介

Futoshiki Puzzle 的游戏目标是将数字横竖都不重复地填入框中，且遵循大小于号不等式指示。

游戏形式与常见的数独游戏（关于数独游戏可以参考文章数独自动计算工具）十分相似，不同之处只有：无需遵循九宫格限制，添加了相邻格子之间的不等号限制。

参考示例及它的解：

示例网站：Futoshiki - Online

Futoshiki游戏和Sudoku数独游戏一样，是典型的Constraint satisfaction problem (CSP) 问题，本文旨在通过该游戏介绍其解法基于Forward Checking算法以及GAC(Generalized Arc Consistency)算法的实现。

同时，两个算法将基于MRV(Minimum Remaining Values)启发式函数实现，后文同样会对MRV进行介绍。

本文假设读者已经了解回溯求解CSP问题的一般方法，基于此进行下面的介绍。

2 Forward Checking 算法

2.1 简介

Forward checking，我斗胆将其翻译为向前检测算法，下称FC算法。

按照伯克利大学人工智能课程的定义：

1. Forward checking is an extension of backtracking search that employs a “modest” amount of propagation (look ahead).
2. When a variable is instantiated we check all constraints that have only one uninstantiated variable remaining.
3. For that uninstantiated variable, we check all of its values, pruning those values that violate the constraint.

英语好的朋友可以自行进行翻译理解，在这里我仅将个人理解分享如下：

1. FC算法是回溯搜索的扩展，旨在使用适中次数的传播以优化回溯搜索。
2. 当一个变量被实例化时（该变量在循环中被访问到，亦可理解为assigned），对所有包含该变量的限制条件（constraints）进行检查，并且找到只剩一个未确定的变量的限制条件。
3. 对于2中提到的未确定的变量，检查他的所有可能取值，将所有会违反当前限制的值剪枝（prune）。

2.2 Pseudo-Code

FC(Level) /*Forward Checking Algorithm */If all variables are assignedPRINT Value of each VariableRETURN or EXIT (RETURN for more solutions) (EXIT for only one solution)V := PickAnUnassignedVariable()Assigned[V] := TRUEfor d := each member of CurDom(V)Value[V] := dDWOoccured:= Falsefor each constraint C over V such that\C has only one unassigned variable X in its scopeif(FCCheck(C,X) == DWO) /* X domain becomes empty*/DWOoccurred:= Truebreak /* stop checking constraints */if(not DWOoccured) /*all constraints were ok*/FC(Level+1)RestoreAllValuesPrunedByFCCheck()Assigned[V] := FALSE //undo since we have tried all of V’s values return;

FCCheck(C,x) // C is a constraint with all its variables already// assigned, except for variable x.for d := each member of CurDom[x]IF making x = d together with previous assignments to variables in scope C falsifies CTHEN remove d from CurDom[x]IF CurDom[x] = {} then return DWO (Domain Wipe Out)ELSE return ok

伪代码部分解析：

1. DWO: Domain Wipe Out，表示该节点（变量）的值域Domain已经为空，不可能满足棋盘的要求，因此需要回溯。在CSP问题里，DWO的出现表示上一次的实例化取值是失败的。

2. Assigned[V] := True：相当于定义中提到的实例化，表示在后续的检查中当前节点已经赋值了。

3. Assigned[V] := False：本次实例化出现DWO，表示在后续的检查中当前节点已经赋值了。

4. RestoreAllValuesPrunedByFCCheck()：显然，DWO发生后我们需要回溯，但是在本次尝试时已经有很多值被修改了（如剪枝减去的某些变量的可能取值），需要将这些值恢复到修改之前。

5. FCCheck(C, x)：实现了定义中第三条的内容，是FC算法剪枝功能的体现。

至此FC算法的介绍告一段落，关于FC算法对于Futoshiki问题的实现会在附录处提到，读者也可以访问Futoshiki-FC算法求解获取对应练习资源以及参考解答。

3 GAC 算法

3.1 简介

在伯克利大学人工智能课程中，对于FC算法过渡到GAC算法的理由，该课程提供了一个经验性的解释：

1. FC often is about 100 times faster than BT.
2. FC with MRV (minimal remaining values) often 10000 times faster.
3. But on some problems the speed up can be much greater.
   • Converts problems that are not solvable to problems that are solvable.
4. Still FC is not that powerful.
5. Other more powerful forms of constraint propagation are used in practice.

这个所谓的 more powerful form 就是接下来要介绍GAC算法。

Generalized Arc Consistence， 同样的，我译为广义边一致算法， 下称GAC算法。

在对其定义进行分析之前，对边一致这一概念做个通俗解释：

Arc consistency eliminates values from domain of variable that can never be part of a consistent solution.

即，边一致将检查某一限制条件的所有变量，将其中绝不可能是一组可行解的值删去。

举例：

C(v1, v2, v3): v1 > v2 > v3，Dom[vi] = {1, 2, 3, 4}；

当v1被赋值为3，此时v2与v3显然不能取4，由边一致的要求，我们将在v1被赋值为3后立即检测并从v2, v3的值域中删去4，而不是像FC算法一样在之后先赋值v2, v3，再检测冲突。

依然参考伯克利大学的定义：iff -> if and only if, 当且仅当; wrt. -> with respect to.

1. C(X,Y) is consistent iff for every value of X there is some value of Y that satisfies C.
2. C(V1, V2, V3, . . . , Vn) is GAC wrt. Vi iff for every value of Vi, there are values of V1, . . . , Vi−1, Vi+1, . . . , Vn that satisfy C.
3. A constraint is GAC iff it is GAC wrt. every variable in its scope.
4. A CSP is GAC iff all of its constraints are GAC.

简单且不严谨地说，对一个CSP问题，只有它的所有限制条件都是满足GAC的时候，这个问题才是满足GAC的。

3.2 Pseudo-Code

GAC(Level) /*Maintain GAC Algorithm */If all variables are assignedPRINT Value of each VariableRETURN or EXIT (RETURN for more solutions) (EXIT for only one solution)V := PickAnUnassignedVariable()Assigned[V] := TRUEfor d := each member of CurDom(V)Value[V] := dPrune all values of V ≠ d from CurDom[V]for each constraint C whose scope contains V Put C on GACQueueif(GAC_Enforce() != DWO)GAC(Level+1) /*all constraints were ok*/RestoreAllValuesPrunedFromCurDoms()Assigned[V] := FALSEreturn; 

GAC_Enforce() // GAC-Queue contains all constraints one of whose variables has // had its domain reduced. At the root of the search tree // first we run GAC_Enforce with all constraints on GAC-Queuewhile GACQueue not emptyC = GACQueue.extract()for V := each member of scope(C)for d := CurDom[V]Find an assignment A for all othervariables in scope(C) such that C(A + V = d) = Trueif Anot foundCurDom[V] = CurDom[V] – dif CurDom[V] = EMPTYempty GACQueuereturn DWO //return immediatelyelsepush all constraints C’ such thatV belongs to scope(C’) and C’ not belongs tp GACQueueon to GACQueuereturn TRUE //while loop exited without DWO

通过FC算法的介绍，相信这两段伪代码阅读难度已经很小了。

整个过程重点在于理解GAC_Enforce()，并且将问题按照GAC的形式定义清楚。

至此GAC算法的介绍告一段落，关于GAC算法对于Futoshiki问题的实现会在附录处提到，读者也可以访问Futoshiki-GAC算法求解获取对应练习资源以及参考解答。

4 MRV启发函数

Minimum Remaining Values Heuristics, 最少剩余值数量启发式函数。

同样引用伯克利大学的介绍：

1. Always branch on a variable with the smallest remaining values (smallest CurDom).
2. If a variable has only one value left, that value is forced, so we should propagate its consequences immediately.
3. This heuristic tends to produce skinny trees at the top.
4. This means that more variables can be instantiated with fewer nodes searched, and thus more constraint propagation/DWO failures occur when the tree starts to branch out.
5. We can find an inconsistency much faster.

显然，MRV要求：

1. 每次都在剩余值最少（值集最小）的变量处扩展。
2. 若一个变量只剩下一个可取值，那么立刻扩展该变量。

5 Futoshiki 的限制分析

考虑Futoshiki的特性，限制可以简单理解为以下三点：

对于一个 N x N 的Futoshiki棋盘：

1. 行约束：每一行有N个数，分别是1~N，各不重复。

2. 列约束：每一列有N个数，分别是1~N，各不重复。

3. 邻接约束：输入时会对某两个邻接位置进行不等式约束，

   如 1 1 > 1 2：表示位置(1, 1)的值 > 位置(1, 2)的值。

针对以上三个约束设计了对应算法。

6 附录

6.1 FC Algorithm

bool FC(futoshiki* board, int level) {nodes++;if (Goal(board)) {// Return when all cells are assigned.cout << "Goal!" << endl;display(board);return true;}Do* v = heuristicpick(board); // Pick with MRVv->assigned = true;bool dwo = false;int pos = 0;for (int i = 0;i<SIZE;i++) if (!v->curdom[i]) {futoshiki boardcopy;Copyboard(&boardcopy, board);v->val = i+1;propagate(board, v);dwo = false;// row constraintif (!dwo && CheckCons(board, 0, v)) {for (int i = 0;i<SIZE;i++) if (!board->board[v->row][i].assigned) {dwo = !FCCheck(board, 0, &board->board[v->row][i]);}}// col constraintif (!dwo && CheckCons(board, 1, v)) {for (int i = 0;i<SIZE;i++) if (!board->board[i][v->col].assigned) {dwo = !FCCheck(board, 1, &board->board[i][v->col]);}}// neighbour constraintif (!dwo && CheckCons(board, 2, v)) {if (v->row && board->board[v->row - 1][v->col].assigned) {dwo = !FCCheck(board, 2, &board->board[v->row - 1][v->col]);}else if (v->row!=SIZE-1 && board->board[v->row + 1][v->col].assigned) {dwo = !FCCheck(board, 2, &board->board[v->row + 1][v->col]);}else if (v->col && board->board[v->row][v->col - 1].assigned) {dwo = !FCCheck(board, 2, &board->board[v->row][v->col - 1]);}else if (v->col!=SIZE-1 && board->board[v->row][v->col + 1].assigned) {dwo = !FCCheck(board, 2, &board->board[v->row][v->col + 1]);}}if(!dwo && FC(board, level + 1)) return true;Copyboard(board, &boardcopy);}v->assigned = false;return false;
}

bool FCCheck(futoshiki* board, int c, Do* m) {// c == 0 >>> rowif (c == 0) for (int i = 0;i<SIZE;i++) {if (!m->curdom[i]) {m->curdom[i] = 1;if(RowCheck(board, m)) m->curdom[i] = 0; // No falsification}}// c == 1 >>> colelse if (c == 1) for (int i = 0;i<SIZE;i++) {if (!m->curdom[i]) {m->curdom[i] = 1;if(ColCheck(board, m)) m->curdom[i] = 0; // No falsification}}// c == 2 >>> neighbourelse if (c == 2) for (int i = 0;i<SIZE;i++) {if (!m->curdom[i]) {m->curdom[i] = 1;if(NeiCheck(board, m)) m->curdom[i] = 0; // No falsification}}if (CDcount(m) == SIZE) return false;else return true;
}

6.2 GAC Algorithm

void GAC(futoshiki* FTSK) {nodes++;if (Goal(FTSK)) {// Return when all cells are assigned.auto _end = std::chrono::system_clock::now();std::chrono::duration<double> elapsed_seconds = _end - _start;cout << ">>> Goal!" << endl;display(FTSK);cout << "=========================================" << endl;cout << "GAC has been called for " << nodes << " times." << endl;cout << "Solution generated in " << elapsed_seconds.count() << " s." << endl;cout << "=========================================" << endl;system("pause");exit(0);}Do* v = heuristicpick(FTSK); // Pick an {UN-ALL-ASSIGNED} node with MRVv->assigned = true;for (int i = 1;i<=SIZE;i++) if (!v->curdom[i]) {v->val = i;futoshiki boardcopy;    // Store the chessboard, in case of DWO.Copyboard(&boardcopy, FTSK);// Prune all other values (GAC's feature)for (int j = 1;j<=SIZE;j++) if (j != i && !v->curdom[j]) { v->curdom[j] = 1;v->curdom[0] = CDcount(v);}if (GAC_Enforce(FTSK, v) != DWO) {GAC(FTSK);}Copyboard(FTSK, &boardcopy); // DWO occured, Restore from copy.}v->assigned = false;
}

bool GAC_Enforce(futoshiki* FTSK, Do* v) {bool flag_row = 0, flag_col = 0, flag_compare = 0;flag_row = RowCheck(FTSK, v);                   // {FALSE} if DWO occured.flag_col = ColCheck(FTSK, v);                   // {FALSE} if DWO occured.flag_compare = NeiCheck(FTSK);                  // {FALSE} if DWO occured.return (flag_row && flag_col && flag_compare);  // Return the LOGIC-AND of each flag.
}

---

完整代码以及对应练习可以参考AI实验集中Exp4以及Proj2的内容。

若有任何错漏，望斧正。

2019/10 Karl