另一个数独难题求解器Using AWK

照片提供：jimray

我们已经在之前 awk简介文章 从小型的单行代码到一些有趣的应用程序，awk都是有效的工具。如果情况需要，当然可以使用更复杂的语言。我想到了perl和python。需要网络支持，数据库访问，用户界面，二进制数据或更广泛的库支持和复杂性的应用程序最好留给其他语言在这些领域提供更好的支持。

不过， awk是一种用于测试算法和应用程序的精湛语言，具有一定的复杂性，尤其是可以将问题分解为大块并作为管道一部分进行流式传输的地方。它’是一个无处不在的用于增强Shell编程功能的理想工具；在几乎所有Unix / 3d捕鱼达人 / BSD系统上都可以找到。可以轻松解决许多与文本，日志行或符号表有关的问题，或者至少可以使用awk以及在Unix / 3d捕鱼达人系统上找到的其他工具来原型化。

虽然awk可以很好地一次处理一条输入线，然后处理然后为每条线发送一些输出，但是它也可以用在更传统的批处理式应用程序中，在该应用程序中，它读取所有输入，进行处理，然后发送处理后的输出。

另一个数独难题求解器– YASPS for Awk

我选择用作示例的应用程序是“另一个数独谜题求解器”。首先，我必须承认，我从来没有坐过自己解决这些难题中的一个，而是在几天的时间里勾勒出这个草图，同时乘火车上下班，看着其他人在工作。我认为这比实际解决任何难题都有趣。

下载适用于Awk的YASPS程序： 解决.awk

输入格式我’我们选择了一种易于在awk中解析并且在Unix环境中相当传统的工具。空行和以井号（＃）开头的行将被忽略，从而易于插入注释。列之间可能会使用多余的空格以提高可读性。下图显示了一个示例：

-------------------------------------------------------------------------------
# I forget where I got this..
# this is 上 e of the hardest 上 es I've found for this algorithm, although
# after transposing the matrix it can be solved in a fraction of the time

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
-------------------------------------------------------------------------------

该程序几乎没有错误检查，但是可以很容易地在前面或作为包装脚本的一部分添加。一世’将其留给读者练习。

This program uses a very simple depth-first recursive backtracking algorithm with up-front and 上 going elimination of invalid entries. Awk may not have the expressive power for representing complex data that perl or other languages have, but with care, many moderate sized problems and data sets can be used. This algorithm may not be the best 上 e around, but it is certainly 足够快 for most problems and is easy to implement.

遇到任何问题，有效地表示数据将使设计程序的任务变得更加容易。我用一个矩阵表示了拼图的完整状态“master”。除了保留关于什么地方的记录并进行最终输出外，几乎没有什么用。

主要的主要变量是其他三个数组。直观地，我们从递归试验和错误方法中知道’我们选择了我们需要经常检查试验编号的有效性。为了加快该过程，我们维护了关联数组，用于存储行，列和每个区域的当前状态（尽管在技术上不正确，但我们’ll call a “quadrant”）。这些是数组R，C和Q。（请注意，awk区分大小写。）

有时，当尝试从嵌套的for循环或递归函数调用中排除常用计算到经常使用的值时，它会有所帮助。我曾经尝试过“regmap” matrix which would store a 象限 number given the row, column values but I found the time savings in this case to be ambiguous. I’ve已将其注释掉，但您的里程可能会有所不同，该技术通常非常有用。

递归算法通常是最佳设计，因此以自顶向下的方式进行描述。该程序中的最高功能称为“search()”并从“END”将问题数据读入数组后的模式。

在较高的层次上，search（）从提供的行和列参数开始，并寻找下一个要检查的空白空间。如果有’任何情况下，问题均已解决，并且随解决方案一起返回。如果有一个空格（用零表示），它将通过使用mark（）将数字插入数组并调用来测试可用数字（使用inuse（）函数，用于该行，列或象限中未使用的数字）本身是递归的。如果递归search（）函数返回零，则表示它已失败，因此再次调用mark（）函数以取消标记试用编号。然后，它循环播放，直到可能性用尽或search（）调用返回成功。

许多递归算法的优点在于解决方案固有的优雅和简单性。尽管它们有时不是最快的算法，但它们通常是“fast enough”而且更容易设计。该程序可在不到几秒钟的时间内解决大多数难题。在不同的难题上尝试该程序时，我注意到的一件事是，如果问题需要较长的时间才能解决（数十秒），则简单地对矩阵进行转置通常会在不到一秒钟的时间内给出相同的解决方案。与今天’s多核CPU，这表明有可能提高它的速度：编写包装器脚本，该脚本以矩阵的不同转置形式启动程序的多个实例。示例显示了上面显示的上一个难题，下图显示了转置版本，其中转置问题的求解速度提高了四倍。

-------------------------------------------------------------------------------
marion:~/sudoku$ time awk -f 解决.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 解决.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语言，但在数据索引上却产生了有趣的变化。此版本的执行速度可能快几个数量级，这在很大程度上是由于数据的表示方式所致。大概我们’ll release “另一个数独难题求解器使用C”稍后再发表。

我相信awk应该在每个人中都占有一席之地’的工具包。与其他语言相比，它的简单性可能被视为一个弱点，但我认为它是其优势之一。可以在下午学习该语言，而无需借助参考书来解决许多日常问题。我会定期从命令行直接使用它，直到实现诸如DSL（领域特定语言）的编译器之类的东西。

推荐的Awk书籍

• AWK编程语言 由Alfred V. Aho，Brian W. Kernighan和Peter J. Weinberger撰写。该语言作者的原始书中有一些出色的例子，说明了一些相当复杂的程序，但仍然是我最喜欢的awk书。由Addison-Wesley出版，1988年。ISBN020107981X。
• 更多编程珍珠：编码人员的自白 乔恩·本特利（AT）&新泽西州默里希尔市的T贝尔实验室。在More Pearls中可以找到另一本使用awk作为算法原型工具的书。读物出色。出版年：1988. ISBN：0201118890

如果您喜欢这篇文章，您可能还会喜欢..