求解Flow Free Game的算法 [英] Algorithm for solving Flow Free Game

问题描述

我最近开始玩

使用现代 SAT 求解器来解决问题

利润

复杂性

问题显然出在 NP 中:如果你猜出一个棋盘星座，很容易(poly-time)检查它是否解决了问题.

它是否是 NP-hard(意味着与 NP 中的所有其他问题一样难，例如 SAT)尚不清楚.无论如何，现代 SAT 求解器肯定不会关心和解决大型实例(我猜高达 100x100).

关于数字链接的文献

在这里，我只是将核子的评论复制到 OP:

<块引用>

搜索数字链接的SAT公式"；和数字链接的 NP 完整性"导致几个参考.不出所料，最有趣的两个是日语.first 是 NP 完备性的实际纸质证明.second 描述了如何使用 SAT 求解器求解 NumberLink，糖.——

降低 SAT 的提示

对问题进行编码有多种可能性.我会给一个我可以快速弥补的.

备注

j_random_hacker 指出不允许独立循环.以下编码确实允许它们.这个问题使 SAT 编码的吸引力降低了一些.我能想到的禁止独立循环的最简单方法是引入 O(n^2) 新变量，其中 n 是板上的瓷砖数量(计算每个瓷砖与下一个水槽的距离) 除非为此使用日志编码，这会将其降低到 O(n*log n)，可能使求解器更难解决问题.

变量

每块瓷砖、块类型和颜色一个变量.例如，如果某个变量 X-Y-T-C 为真，它会编码位置 X/Y 的图块类型为 T 并且颜色为 C.您不需要空磁贴类型，因为这不会在解决方案中发生.

设置初始变量

设置接收器/源的变量，并说没有其他图块可以是接收器/源.

限制条件

1. 对于每个位置，只有一种颜色/件组合为真(基数约束).
2. 对于每个变量(位置、类型、颜色)，四个相邻的图块必须兼容(如果颜色匹配).

我可能错过了一些东西.但它应该很容易修复.

I recently started playing Flow Free Game.

Connect matching colors with pipe to create a flow. Pair all colors, and cover the entire board to solve each puzzle in Flow Free. But watch out, pipes will break if they cross or overlap!

I realized it is just path finding game between given pair of points with conditions that no two paths overlap. I was interested in writing a solution for the game but don't know where to start. I thought of using backtracking but for very large board sizes it will have high time complexity.

Is there any suitable algorithm to solve the game efficiently. Can using heuristics to solve the problem help? Just give me a hint on where to start, I will take it from there.

I observed in most of the boards that usually

1. For furthest points, you need to follow path along edge.
2. For point nearest to each other, follow direct path if there is one.

Is this correct observation and can it be used to solve it efficiently?

解决方案

Reduction to SAT

Basic idea

1. Reduce the problem to SAT
2. Use a modern SAT solver to solve the problem
3. Profit

Complexity

The problem is obviously in NP: If you guess a board constellation, it is easy (poly-time) to check whether it solves the problem.

Whether it is NP-hard (meaning as hard as every other problem in NP, e.g. SAT), is not clear. Surely modern SAT solvers will not care and solve large instances in a breeze anyway (I guess up to 100x100).

Literature on Number Link

Here I just copy Nuclearman's comment to the OP:

Searching for "SAT formulation of numberlink" and "NP-completeness of numberlink" leads to a couple references. Unsurprisingly, the two most interesting ones are in Japanese. The first is the actual paper proof of NP-completeness. The second describes how to solve NumberLink using the SAT solver, Sugar. –

Hint for reduction to SAT

There are several possibilities to encode the problem. I'll give one that I could make up quickly.

Remark

j_random_hacker noted that free-standing cycles are not allowed. The following encoding does allow them. This problem makes the SAT encoding a bit less attractive. The simplest method I could think of to forbid free-standing loops would introduce O(n^2) new variables, where n is the number of tiles on the board (count distance from next sink for each tile) unless one uses log encoding for this, which would bring it down to O(n*log n), possible making the problem harder for the solver.

Variables

One variable per tile, piece type and color. Example if some variable X-Y-T-C is true it encodes that the tile at position X/Y is of type T and has color C. You don't need the empty tile type since this cannot happen in a solution.

Set initial variables

Set the variables for the sink/sources and say no other tile can be sink/source.

Constraints

1. For every position, exactly one color/piece combination is true (cardinality constraint).
2. For every variable (position, type, color), the four adjacent tiles have to be compatible (if the color matches).

I might have missed something. But it should be easily fixed.

这篇关于求解Flow Free Game的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！