README

一个通用的谜题解决包，能够解决各种各样的问题。

示例

它可以解决的一些谜题示例

动机

人们一直让我实现这个谜题或那个谜题的解决器。这次，我决定不再只解决一个谜题，而是创建一个通用的谜题解决器，它可以一次性解决所有这些谜题以及未来的所有谜题。此外，这样还可以使算法在不同的用途中得到重用，例如用于视频游戏的AI或解决某些现实问题的解决器。谁知道未来会带来什么呢！

基本用法

使用此包有两种方式：通用解决器，一种信息丰富的瑞士军刀方法，或者暴力解决器……名字中有什么。

通用解决器

通用解决器就像是一个瑞士军刀，为谜题解决器。

给它提供一些关于你想要什么的信息，它会为你提供一个解决你谜题的工具。所有以示例形式实现的谜题，以及许多没有示例实现的谜题，都可以使用这种方法提供有效的解决器。

5-皇后问题与通用解决器

解决5-皇后问题

<?php
use Stratadox\PuzzleSolver\Find;
use Stratadox\PuzzleSolver\Puzzle\NQueens\NQueensPuzzle;
use Stratadox\PuzzleSolver\UniversalSolver;

$solver = UniversalSolver::forAPuzzle()
    ->withGoalTo(Find::allBestSolutions())
    ->whereMovesEventuallyRunOut()
    ->select();


$solutions = $solver->solve(NQueensPuzzle::forQueens(5));

assert(count($solutions) === 10);

滑动拼图与通用解决器

解决滑动拼图

<?php
use Stratadox\PuzzleSolver\Find;
use Stratadox\PuzzleSolver\Puzzle\SlidingPuzzle\LevenshteinHeuristic;
use Stratadox\PuzzleSolver\Puzzle\SlidingPuzzle\SlidingPuzzle;
use Stratadox\PuzzleSolver\UniversalSolver;

$solver = UniversalSolver::aimingTo(Find::aBestSolution())
    ->withHeuristic(new LevenshteinHeuristic())
    ->select();

$puzzle = SlidingPuzzle::withPieces(
    [2, 4, 1],
    [8, 5, 7],
    [3, 0, 6]
);

$solution = $solver->solve($puzzle)[0];

assert(count($solution->moves()) === 25);

暴力解决器

在待办事项列表中。

可用算法

而不是提供固定数量的算法，此包提供了一种可组合的算法。

解决器本身可以是两种风格中的一种，具有三种基本搜索策略，这些策略可以进一步通过许多装饰器来细化。

风格

基本解决器有两种风格：急切或懒惰。

急切

急切谜题解决器会寻找第一个有效解。急切解决器在找到单个解决方案后会停止，这使得它们非常适合只有一个可能解决方案或只需要一个解决方案的谜题。

懒惰

懒惰谜题解决器会继续寻找解决方案，直到找到所有有效解决方案。懒惰解决器可以用于需要多个解决方案的谜题。

搜索策略

提供了三种主要的搜索策略：深度优先、广度优先和最佳优先。

深度优先

深度优先搜索持续跟踪第一个选项，直到发现该分支不会导致解决方案，然后它回溯到第一个下一个可用的选项。

广度优先

广度优先搜索持续探索所有可用的选项，然后进入那些选项之后的可用的选项。

最佳优先

最佳优先搜索按照质量顺序将新遇到的节点入队。首先考虑最有可能导致期望结果的操作。为了确定操作的质量，最佳优先策略可以配备一个启发式方法。

装饰器

为了优化搜索，并/或避免陷入无限循环，搜索策略通常会被至少一个装饰器包装。

已访问节点跳过器

已访问节点跳过器会记录在搜索过程中已遇到的谜题状态，以跳过即将第二次考虑的候选节点。

已访问节点成本检查器

已访问节点成本检查器会记录到达每个考虑的候选节点的成本。当遇到一个已经记录成本的候选节点时，与之前记录的成本比较新发现的路径的成本。如果成本低于之前，则更新记录并考虑新的候选节点。如果成本等于或高于之前到达同一目标路径的成本，则丢弃该候选节点。

最差解决方案跳过器

最差解决方案跳过器会跟踪在搜索过程中找到的解决方案中的最低成本。每次遇到路径成本超过已找到的最低成本解决方案成本的节点时，就会跳过该节点。

重复节点跳过器

重复节点跳过器可以防止路径进入循环。在考虑新的候选节点之前，会将所有之前的谜题状态与新的状态进行比较。如果新的谜题状态已经在当前路径上达到，则将候选节点视为循环并拒绝。

迭代限制器

迭代限制器会在考虑的候选节点数量超过设定的限制时中止搜索。

调试记录器

调试记录器是谜题求解器的可视化工具。每次考虑新的候选节点时，调试记录器都会将其记录到输出流中。

待办事项

“蛮力求解器”：给定一个迭代限制，尝试所有可能的求解器配置。
- 从懒惰搜索开始，然后转向积极搜索。
- 尝试一个求解器，捕获OutOfIterations异常并尝试下一个。
(*) 可能不是所有，但很多合理的配置。
一个 neat（并且可扩展）的控制台应用程序，用于解决谜题。当前的 samples 目录有些原始。
- 谜题工厂接口和每个谜题的工厂，以简化加载谜题输入并增强可扩展性。
- 解决方案渲染器
- Symfony控制台应用程序？（需要决定：是否希望在实用仓库中包含该依赖项）
网站版本（或者，指向未来仓库的链接）
- 添加新谜题的简单方法？（可以这样做吗？）

stratadox / puzzle-solver

维护者

详细信息