Linux ： 使用 AWK 的数独解谜器

awk 是一种极好的语言，用于测试具有一定复杂性的算法和应用程序，尤其是在问题可以分解成可以作为管道的一部分流式传输的块的情况下。它无处不在，是增强 shell 编程功能的理想工具；在几乎所有 Unix/Linux/BSD 系统上都以某种形式出现。处理文本、日志行或符号表的许多问题都可以轻松解决，或者至少可以使用 awk 以及 Linux 系统上的其他工具进行原型设计。

虽然 awk 很适合一次对一行输入进行操作，处理然后为每行发送一些输出，但它也可以用于更传统的批处理式应用程序中，它读取所有输入，处理然后发送处理后的输出。

又一个数独解谜器——Awk 的 YASPS

我选择用作示例的应用程序是“又一个数独解谜器”。首先我必须承认，我自己从来没有坐下来解决这些难题，而是在几天内在火车上通勤并看着其他人解决这些难题时勾勒出来的。我认为这比实际做任何谜题要有趣得多。

下载 Awk 的 YASPS 程序：solve.awk

我选择的输入格式是一种在 awk 中易于解析并且在 Unix 环境中相当传统的格式。空行和以井号 (#) 字符开头的行将被忽略，以便于插入注释。为了便于阅读，列之间可以使用额外的空格。一个例子如下图所示：

2 0 0  6 7 0  0 0 0
0 0 6  0 0 0  2 0 1
4 0 0  0 0 0  8 0 0

5 0 0  0 0 9  3 0 0
0 3 0  0 0 0  0 5 0
0 0 2  8 0 0  0 0 7

0 0 1  0 0 0  0 0 4
7 0 8  0 0 0  6 0 0
0 0 0  0 5 3  0 0 8
-------------------------------------------------------------------------------

这个程序几乎没有错误检查，但很容易在前面添加或作为包装脚本的一部分。

该程序使用非常简单的深度优先递归回溯算法，预先并持续消除无效条目。awk 可能不具备 perl 或其他语言所具有的表示复杂数据的表达能力，但要小心，可以使用许多中等规模的问题和数据集。这个算法可能不是最好的算法，但它对于大多数问题肯定足够快并且易于实现。

对于任何问题，有效地表示数据会使设计程序的任务变得更加容易。我在一个名为“master”的矩阵中表示了拼图的完整状态。除了记录在哪里以及进行最终输出之外，这几乎没有什么用处。

主要的主力变量是其他三个数组。直觉上，我们从我们选择的递归试错法中知道，我们需要经常检查试验数字的有效性。为了加速这个过程，我们维护关联数组来存储行、列和每个区域的当前状态（虽然技术上不正确，但我们将其称为“象限”）。这些是数组 R、C 和 Q。（请注意，awk 区分大小写。）

有时，在尝试从嵌套 for 循环或递归函数调用中分解出常用计算时，它会有所帮助，以预先计算经常使用的值。我曾尝试使用“regmap”矩阵来存储给定行、列值的象限数，但我发现在这种情况下节省的时间是模棱两可的。我已将其注释掉，但您的里程可能会有所不同，并且该技术通常非常有用。

递归算法通常设计得最好，因此以自上而下的方式描述。该程序中的顶部函数称为“search()”，并在问题数据被读入数组后从“END”模式调用。

在高层次上，search() 从提供的行和列参数开始，并寻找下一个要检查的空白空间。如果没有，则问题已解决，并与解决方案一起返回。如果有一个空白空间（用零表示），它会通过使用 mark() 将一个数字插入到数组中并调用自身递归。如果递归 search() 函数返回零，则表示它已失败，因此再次调用 mark() 函数以取消标记试用号。然后它循环，直到可能性耗尽或 search() 调用返回成功。

许多递归算法的美妙之处在于解决方案固有的优雅和简单。虽然它们有时不是最快的算法，但它们通常“足够快”并且更容易设计。该程序在不到几秒钟的时间内解决了大多数难题。当我在不同的谜题上尝试这个程序时，我注意到的一件事是，如果一个问题需要更长的时间来解决（几十秒），简单地转置矩阵通常会在几分之一秒内给出相同的解决方案。对于今天的多核 CPU，这表明了一种加速它的可能性：编写一个包装脚本，该脚本启动具有不同矩阵转置的程序的多个实例。

-------------------------------------------------------------------------------
marion:~/sudoku$ time awk -f solve.awk THE-HARDEST-SO-FAR.dat 

# Searches=134214

  2 8 3  6 7 1  9 4 5
  9 7 6  5 4 8  2 3 1
  4 1 5  3 9 2  8 7 6

  5 6 7  4 1 9  3 8 2
  8 3 4  2 6 7  1 5 9
  1 9 2  8 3 5  4 6 7

  3 2 1  7 8 6  5 9 4
  7 5 8  9 2 4  6 1 3
  6 4 9  1 5 3  7 2 8

real    0m10.009s
user    0m9.889s
sys     0m0.024s

marion:~/sudoku$ time awk -f solve.awk /tmp/transposed.dat

# Searches=32253

  8 3 4  7 9 2  6 1 5
  2 1 9  6 5 8  7 3 4
  7 6 5  4 1 3  8 2 9

  3 4 6  5 7 9  2 8 1
  5 2 8  3 6 1  9 4 7
  1 9 7  8 2 4  3 5 6

  9 8 1  2 4 7  5 6 3
  4 5 2  9 3 6  1 7 8
  6 7 3  1 8 5  4 9 2

real    0m2.487s
user    0m2.456s
sys     0m0.008s
-------------------------------------------------------------------------------

当需要更快的速度时，通常可以通过将算法翻译成另一种语言来更直接地表示数据集来完成。将这个程序翻译成 C 语言，并在数据索引上做了一个有趣的改动。这个版本的执行速度可能要快几个数量级，主要是由于数据的表示方式。

我相信 awk 应该在每个人的工具包中占有一席之地。它相对于其他语言的简单性可能被视为一个弱点，但我认为它是它的优势之一。该语言可以花一小段时间的学习并使用，而无需借助参考书来解决许多日常问题。