8数码问题

简介

8数码问题是一种在19世纪70年代由Noyes Palmer Chapman发明并普及的拼图游戏。它在一个3x3的网格上进行，其中有8个标有1到8的方块和一个空白方块。您的目标是重新排列方块，使它们按顺序排列。您允许将方块水平或垂直滑动到空白方块中。以下是从初始棋盘位置（左侧）到目标位置（右侧）的合法移动序列。

   1  3        1     3        1  2  3        1  2  3        1  2  3
4  2  5   =>   4  2  5   =>   4     5   =>   4  5      =>   4  5  6
7  8  6        7  8  6        7  8  6        7  8  6        7  8
initial                                                      goal

该程序的文档可以在此处找到 - https://docs.rs/crate/project_1_itcs_6156/0.1.3

如何安装和运行

首先从这里安装 rustup。 rustup 是一种名为 rust 的语言的工具链，该项目是用它编写的。安装它将允许您运行我的程序。

如果您不想安装它，我还包括了一个可以在没有任何依赖项的情况下运行的Windows可执行文件。在根目录中查找 project_1.exe。

安装 rustup 后，执行以下命令以运行代码 -

git clone https://github.com/DhruvDh/project_1_itcs_6150.git
cd project_1_itcs_6156 && cargo run

如果您想使用初始和目标状态的定制值运行程序，请在 src/main.rs 中找到 fn main() 并将此行更改为反映您想要的初始和目标状态的值 -

let mut problem_1 = Problem::new(
        vec![1, 2, 3, 7, 4, 5, 6, 8, 0], // initial state array
        vec![1, 2, 3, 8, 6, 4, 7, 5, 0], // goal state array
    );

通过更改 solve 函数调用中的参数来更改成本函数。

problem_1.solve("Manhattan"); // any value other than manhattan will use hamming distance as cost function.

问题表述

• 目标：碎片最终落在由目标状态描述的位置。
• 状态：所有可能的拼图排列。
• 动作：向上、向下、向左或向右移动空白方块。
• 性能度量：解决方案中的总移动次数，如果存在解决方案。

问题结构

程序由3个主要部分组成。2个结构 Problem 和 State，以及一个 main 方法。问题状态公开了一个 solve 方法，这是找到解决方案所需的所有内容。更详细的信息可以通过点击页面下方的相应结构名称获得。

全局变量

本实现中没有全局变量。有关更多信息，请参阅（文档）https://docs.rs/crate/project_1_itcs_6156/0.1.3。

结构体

状态

一个封装状态信息的结构体。

属性

• is：一个整数向量，用于存储拼图中数字的位置。
• cost：此状态的成本（g() + h()）
• g：从根节点到达这里所需的成本。
• h：估计到达目标状态的成本。
• kind：要执行以达到此状态的动作类型。

其他细节

我正在使用二叉堆作为优先队列来选择下一个要移动的状态。这里的优先级是“成本”的逆序。为了实现这一点，我需要实现状态排序特质。这通过实现4个特质来完成 - Ord、PartialOrd、Eq（或相等）、PartialEq。排序特质被实现为，具有较低成本的State被认为比具有较高成本的State更大。

问题

一个封装当前问题信息的结构体。

属性

• state：一个指向结构体State实例的智能指针。
• goal_state：定义目标状态的一组整数。
• visited：一个HashSet，存储所有已经访问过的状态。
• under_consideration：一个BinaryHeap，跟踪我们将从其中选择下一个状态的集合。
• no_generated：一个计数器，用于跟踪生成的节点数量。
• no_expanded：一个计数器，用于跟踪展开的节点数量。
• heuristic：描述当前使用的启发式算法的字符串。

示例

情况1

Current State:             Goal State:
-------------             -------------
| 1 | 2 | 3 |             | 1 | 2 | 3 |
| 7 | 4 | 5 |             | 8 | 6 | 4 |
| 6 | 8 | 0 |             | 7 | 5 | 0 |
-------------             -------------
Solving using Manhattan distance...
Expanded 19 nodes.
Generated 33 nodes.
Solution is ["Up", "Left", "Down", "Left", "Up", "Right", "Down", "Right"]

Current State:             Goal State:
-------------             -------------
| 1 | 2 | 3 |             | 1 | 2 | 3 |
| 7 | 4 | 5 |             | 8 | 6 | 4 |
| 6 | 8 | 0 |             | 7 | 5 | 0 |
-------------             -------------
Solving using Hamming distance...
Expanded 38 nodes.
Generated 63 nodes.
Solution is ["Up", "Left", "Down", "Left", "Up", "Right", "Down", "Right"]

情况2

Current State:             Goal State:
-------------             -------------
| 2 | 8 | 1 |             | 3 | 2 | 1 |
| 3 | 4 | 6 |             | 8 | 0 | 4 |
| 7 | 5 | 0 |             | 7 | 5 | 6 |
-------------             -------------
Solving using Manhattan distance...
Expanded 14 nodes.
Generated 26 nodes.
Solution is ["Up", "Left", "Up", "Left", "Down", "Right"]

Current State:             Goal State:
-------------             -------------
| 2 | 8 | 1 |             | 3 | 2 | 1 |
| 3 | 4 | 6 |             | 8 | 0 | 4 |
| 7 | 5 | 0 |             | 7 | 5 | 6 |
-------------             -------------
Solving using Hamming distance...
Expanded 16 nodes.
Generated 28 nodes.
Solution is ["Up", "Left", "Up", "Left", "Down", "Right"]

情况3

Current State:             Goal State:
-------------             -------------
| 0 | 1 | 3 |             | 1 | 2 | 3 |
| 4 | 2 | 5 |             | 4 | 5 | 6 |
| 7 | 8 | 6 |             | 7 | 8 | 0 |
-------------             -------------
Solving using Manhattan distance...
Expanded 9 nodes.
Generated 19 nodes.
Solution is ["Right", "Down", "Right", "Down"]

Current State:             Goal State:
-------------             -------------
| 0 | 1 | 3 |             | 1 | 2 | 3 |
| 4 | 2 | 5 |             | 4 | 5 | 6 |
| 7 | 8 | 6 |             | 7 | 8 | 0 |
-------------             -------------
Solving using Hamming distance...
Expanded 11 nodes.
Generated 20 nodes.
Solution is ["Right", "Down", "Right", "Down"]

情况4：（无解）

Current State:             Goal State:
-------------             -------------
| 0 | 3 | 1 |             | 1 | 2 | 3 |
| 4 | 2 | 5 |             | 4 | 5 | 6 |
| 7 | 8 | 6 |             | 7 | 8 | 0 |
-------------             -------------
Solving using Manhattan distance...
thread 'main' panicked at 'Reached a dead end.', src\libcore\option.rs:1038:5
note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.
error: process didn't exit successfully: `target\debug\project_1.exe` (exit code: 101)