一份菜单

另一个数独难题求解器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

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

  1. 50个3d捕鱼达人 Sysadmin教程
  2. 50个最常用的3d捕鱼达人命令(包括示例)
  3. 排名前25位的最佳3d捕鱼达人性能监视和调试工具
  4. 妈妈,我找到了! 15个实用的3d捕鱼达人 Find命令示例
  5. 3d捕鱼达人 101 Hacks第二版电子书 3d捕鱼达人 101黑客手册

Bash 101 Hacks书 Sed和Awk 101黑客手册 Nagios Core 3书 Vim 101黑客手册

{ 11 评论… 加一 }

  • 普热梅克 2010年1月13日,上午3:36

    好文章!

  • 匿名 2010年1月15日,上午8:56

    谢谢这个–这激发了我对学习更多有关awk的兴趣。写得很好。保持’em coming!

  • 比尔·邓肯 2010年1月16日,上午11:42

    感谢您的反馈!欣赏评论。

    干杯。

  • 吉姆·林克 2010年1月16日,晚上10:03

    Awk非常适合举报,但我还没有’试图用它计算任何算法!有趣的文章。

  • CRB 2010年1月17日,上午7:32

    很棒的文章… it’使用awk可以在短期内完成的操作令人惊讶。它’看到awk文章令人耳目一新,该文章结合了awk的文本处理能力及其计算算法的能力。太多的awk文章仅关注文本文件操作,干得好!

  • 比尔·邓肯 2010年1月17日,下午4:45

    感谢大家的意见!

    我在文章中提出了一个预告片,提出了一种更好/更快的方法来索引C中的数据。有人对此有任何想法吗?

  • 米洛斯 2010年1月20日,下午7:03

    从以下位置交换原始脚本的第100行:
    返回1
    对此:
    倾倒()
    返回0
    并将原始脚本的第143行更改为:
    倾倒()
    对此
    #dump()

    瞧,您将获得所有解决方案,而不仅仅是第一个。
    您可以对此进行测试:

    #多种解决方案
    3 0 8 6 0 9 0 1 4
    1 0 4 3 0 8 0 6 9
    6 0 9 4 0 1 0 3 8

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

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

    祝你有个愉快的夜晚

  • eMancu 2010年1月24日,下午12:40

    我不敢相信Awk的力量…我被拒绝将我的grep更改为awk,但是现在… I’ll try awk!

  • 比尔·邓肯 2010年1月24日,下午2:23

    谢谢你们的评论。还有更多有趣的awk应用程序,敬请期待!

  • 阿尔弗雷多·里西奥蒂 2010年2月6日,上午6:27

    感谢您的文章,这是激发awk兴趣的好方法。

  • 比尔·邓肯 2010年2月6日,下午5:05

    谢谢阿尔弗雷多,
    我想,任务已经完成;那’s我正在尝试做的事。
    请继续关注,因为会有一些后续文章。

发表评论