为解决流量免费游戏算法 [英] Algorithm for solving Flow Free Game

问题描述

我最近开始玩流量免费游戏。

  

     

连接配色与管道创建一个流程。对所有颜色，并覆盖整个板来解决流动自由每个难题。但要小心，管道将打破，如果他们交叉或重叠！

我意识到，这只是路径给出点对有条件的，没有两条路径之间的重叠寻找游戏。我感兴趣的是书面的游戏解决方案，但不知道从哪里开始。我想用回溯但对于非常大的电路板尺寸，将具有很高的时间复杂度。

有没有合适的算法能够有效地解决游戏。可以用试探法来解决此问题的帮助？只要给我，从哪里开始的提示，我会把它从那里。

我在大部分主板的观察，通常是

1. 对于最远点，你需要跟随边缘的路径。
2. 对于点最接近对方，请直接路径（如果有）。

这是正确的观察，并可以将其用来有效地解决呢？

解决方案

还原到SAT

基本思路

1. 问题缩小到 SAT
2. 使用现代化的SAT求解器来解决这个问题
3. 利润

复杂性

的问题是显然的NP：如果猜测板星座，很容易（聚时间），以检查它是否解决了问题

无论是NP难（意思是一样努力在NP所有其他问题，如SAT），目前尚不清楚。当然，现代的SAT求解器不会在意，解决一件轻而易举的事反正（我估计高达100×100）。

大对象

文学数链接

在这里，我只是Nuclearman的评论复制到OP：

  

搜索SAT制剂numberlink的和numberlink的NP完全导致了几个参考文献。不出所料，这两个最有趣的是日语。该第一是实际的纸证明NP完全性。该第二介绍如何使用NumberLink国家税务总局解算器来解决，糖。 -

提示减少到SAT

有几种可能性EN code中的问题。我给一个，我可以迅速弥补。

备注

j_random_hacker指出，自支撑的周期是不允许的。下面的编码确实允许他们。这个问题使SAT编码少了几分吸引力。我能想到的最简单的方法来禁止独立的回路将引入为O（n ^ 2）新的变量，其中 N 是瓷砖板上的数字（数距离从明年沉每个tile）除非使用日志编码本，这将使其下降到 O（N * log n）的，可能使问题更难求解器

变量

每瓦，片式和颜色的一个变量。例如，如果一些变量 XYTC 是真的，那恩codeS的图块位置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.

这篇关于为解决流量免费游戏算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！