APL中的数独求解器

A Sudoku Solver in APL

频道:Dyalog · 时长:9:43 · 发布:2012-10-27 · 播放:47334

在 YouTube 观看

简介

Dyalog演示了用APL开发数独求解器,使用了Arthur Whitney的算法和John Scholes的性能优化。叙述逐步介绍了面向数组的解决方案。

HN 为什么推荐

强烈推荐,因为它美丽地展示了APL可以被阅读并逐步推理。

我一直喜欢这个视频,其中一位Dyalog开发者轻松地用APL编写了一个数独求解器 — HN, 2022

函数式编程 · 算法与数据结构

中文字幕节选

三元素向量的索引,一个用于 Omega 索引的函数,Omega 的平方 其中 Omega 是三行三列的 reshape,由 数字组成,三行项复制和三列 项 复制,box 表示一个函数,用于 Box 数字 一个 9x9 数独谜题,我们将从一个更小的 4x4 谜题开始,行和列的索引 4x4 数组,每个单元格与其 box 编号的连接,其中 box 取 Omega 的第一项,Omega 的幂为二分之一 每个单元格的行列 box 编号,行列 box 编号,对于一个 4x4 谜题,逐项与一个单元格比较 包含 334,存在冲突,其中 1 是 每个单元格的成员 外积比较与所有 单元格,是一个秩为四的数组,包围前 两个轴,形状的 形状产生一个 4x4 的 4x4 冲突 矩阵的映射,C map 表示一个函数,用于冲突 映射,这里是一个 4x4 谜题的冲突映射 谜题,这里是一个 4x4 数独谜题,零表示 空白方格,谜题的形状,一个 谜题的冲突映射,第三行第二列 左参数单元格选择,单元格 项是冲突掩码, 谜题再次,与单元格冲突的数字 在 32 所有数字 1 到 4,除去 冲突数字 可用于单元格 1,1 的数字 在谜题中 s44 左和右函数参数 我们可以有一个左内部操作数 32,由双 Alpha 寻址 Alpha 的负 32 取 88 谜题的形状取 加上谜题值,表示 一个操作符,用于 Alpha 在 alpha alpha 在 Omega 99 在 1 1 在 s44 可用于 1 1 的数字 在 s44 每个数字在单元格 1 1 在 单元格 s44 一个放置向量,用于单元格 1 1 在 s44,这里是一个 22 绑定放置,对于每个,连接 放置,放置用于 单元格 2 1 合理化最右边的段,连接一个 1 绑定与 pvec 应用于每个项 单元格 s44 抽象为 一个放置的 向量,我们可以重写上述表达式 或表示为三元素向量的归约 的 单元格与一个单元格项连接,单元格 S4 四个,还包括一个额外的空格 这是题目 s44,它是 形状为行列索引矩阵,一个由 索引组成的向量 在 s44 中为空的单元格,一个由 空格组成的向量,索引的 Z1 复制 向量,即 s44 中空单元格的向量 s44 使用所有空 单元格,我们得到了一个解 向量,用于题目 s44 然而这种编码 效率低下,svec 在空 单元格上折叠 PX,PX 对每个 放置应用 PVE,pvec 对每个可用数字应用 AVL 而 AVL 对 cmap RCB 计算相同的值 每次 我们只在 svec 中计算一次 cmap RCB row Omega, 并将其作为内层上操作数和 alpha alpha 传递给 pvec,作为内层操作数 alpha alpha 传递给 AVL,并在 AVL 中将其接收为 alpha alpha 所以效果相同。现在这里是一个 9 乘 9 的

HN 上的讨论

我一直很喜欢这个视频,其中一位 Dyalog 开发者毫不费力地用 APL 编写了一个数独求解器:[VIDEO] — lizardactivist, 2022-03
> 我的观点是,通用编程通常看起来更像编写排序算法,而不是简单地调用它。因此,我更感兴趣的是看到J的特性如何让你更简洁或以其他方式更好地编写算法的真实例子。啊——我明白了。这里[1]是J中的快速排序。John Scholes的视频非常出色且极具说明性,尽管它们涉及的是APL而不是J;康威生命游戏[2]和数独[3]。> 文章展示了J如何用内置函数或其内置修饰符解决一些数学问题。但在通用编程中,你不会找到一个完全符合你需求的函数,也许加上一个小副词。你通常必须自己编写那个函数,用一些已有的函数来描述它的工作原理。对。这是真的,但在J中你通常比其他语言更接近内置函数。> 注意你的第二个例子可以表达为类似 > x.OrderBy(y => y[1]) > 在C#中,假设x是int[N][M]。我理解J的版本可以处理许多其他形状的X,但如果不看例子,很难体会到这在编写其他(希望是众所周知的)算法时… — moonchild, 2020-08
那个1975年的APL演示很可爱。Dyalog和GNU APL中保留了很多——看到核心APL函数是多么永恒,非常有趣。我非常喜欢已故的John Scholes的一些视频,他逐步讲解APL解决方案,包括著名的APL中康威生命游戏的演示(0)。他关于深度优先搜索(1)和解决数独(2)的视频也很精彩。(0)[LINK] (1)[LINK] (2)[VIDEO] — paliilap, 2019-08
APL很棒。如果你还没看过,已故的John Scholes做了一些绝对优美的APL编程演示[1]、[2]、[3]。[1]: [LINK] [2]: [VIDEO] [3]: [LINK] — geocar, 2019-07
我非常相信简洁的表示法(比我共事过的大多数人都更相信),但拥有一个可以明确说出的名字的优势足够大,超过了小的常数因子。我不认为这经得起推敲。APL作为一种语言就是为了被说出来的,而且它似乎在这方面取得了成功。Alan Perlis在一篇伟大的论文中简要提到了这一点,[1] 几乎所有与这门语言及其衍生语言打过交道的人都同意你的说法不成立。认为APL及其衍生语言不能被“阅读和谈论”的想法,坦率地说,无论怎么想象都是在无视现实。例如,这里[2][3][4]有一些视频反驳了你的说法,前两个是APL,最后一个是k本身。额外加分项,看看Aaron Hsu的演讲[5];随便挑一个,它们都相当不错,而且大多数都有一段解释为什么那种观点是错误的。[1] [LINK] [2] [LINK] [3] [VIDEO] [4] [LINK] [5] [LINK] — kick, 2020-03

相关视频