Dyalog Depth-First Operator Slashes 8-Queens Tree to 2,057 Nodes

Depth-first search in APL — Dyalog

Dyalog

Higher-order array reductions eliminate explicit recursion branching by coupling dynamic subtree generation directly into accumulator folds, pruning exponential search spaces to viable solutions.

AI-assisted summary of Depth-first search in APL — original source. Check the original for full context.

Source published:

Key ideas

  • A general two-operand depth-first search operator in APL decouples accumulation logic (left operand) from subtree projection logic (right operand), enabling recursion without explicit base-case checks. (1:30)
  • The tree traversal pattern seamlessly spans concrete nested arrays and just-in-time dynamic state trees generated on the fly, such as in game search spaces. (5:28)
  • Applying DFS to the 8-queens problem cuts the search space from an unconstrained 8^8 (16,777,216) candidate states down to only 2,057 visited nodes. (8:23)
  • Valid N-queens solution counts across board dimensions N = 0 through 10 are computed directly as 1, 1, 0, 0, 2, 10, 4, 40, 92, 352, and 724. (8:23)

Detailed notes

## Background Published by Dyalog on YouTube on July 18, 2014, this video presents a step-by-step development of a general depth-first tree-search operator within an interactive APL session. The show notes highlight that the conceptual material is concentrated and recommend pausing periodically to absorb the code.

## TL;DR The tutorial demonstrates how to design a general, higher-order depth-first search operator in Dyalog APL that folds an accumulator across tree nodes without requiring explicit base-case branching. After demonstrating traversals on static nested arrays to count nodes or extract leaves, the presentation shifts to generating subtrees dynamically just in time. Using the classic N-Queens problem, it calculates diagonal and vertical attack vectors to prune illegal placements on the fly, dramatically cutting the 8-queens search space from over 16 million potential states down to 2,057 visited nodes before formatting the resulting solutions into visual chessboard matrices.

## Atmosphere & style The presentation is quiet, cerebral, and intensely focused, characterized by the deliberate, methodical cadence of a live programming session. It carries an elegant, almost mathematical clarity as dense APL primitives are introduced and composed into expressive higher-order operators. Watching it feels like a sequence of satisfying conceptual reveals, shifting smoothly from abstract operator theory to practical algorithmic problem-solving.

## Bulletin - [01:30](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=90s) A general two-operand depth-first search operator in APL decouples accumulation logic (left operand) from subtree projection logic (right operand), enabling recursion without explicit base-case checks. - [05:28](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=328s) The tree traversal pattern seamlessly spans concrete nested arrays and just-in-time dynamic state trees generated on the fly, such as in game search spaces. - [08:23](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=503s) Applying DFS to the 8-queens problem cuts the search space from an unconstrained 8^8 (16,777,216) candidate states down to only 2,057 visited nodes. - [08:23](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=503s) Valid N-queens solution counts across board dimensions N = 0 through 10 are computed directly as 1, 1, 0, 0, 2, 10, 4, 40, 92, 352, and 724.

## Key takeaways - [00:07](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=7s) Depth-first search visits a root node and recursively traverses each subtree in sequence. - [00:07](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=7s) Dyalog APL distinguishes operands from arguments using double symbols (⍶, ⍹) for operands and single symbols (⍺, ⍵) for array arguments. - [01:30](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=90s) The DFS operator accepts an initial accumulator (left argument) and a tree (right argument), pairing an accumulating function (left operand) with a subtree expansion function (right operand). - [01:30](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=90s) Recursive del (∇) combined with commute (⍨) and right-to-left reduction folds tree state without requiring conditional base-case testing. - [03:38](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=218s) The right operand alone determines the tree's structure and semantics, allowing any arbitrary data representation to be interpreted as a tree. - [03:38](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=218s) Currying the search operator with a static right operand derives specialized single-operand operators for node counting, leaf counting, or leaf extraction. - [05:28](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=328s) Subtrees can be synthesized just in time rather than stored statically, making DFS suitable for combinatorial puzzle solving. - [05:28](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=328s) In N-queens, column attacks across vertical, left diagonal, and right diagonal lines are generated by scaling direction vectors (¯1, 0, 1) against placement depths. - [08:23](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=503s) Pruning illegal queen placements during dynamic subtree generation reduces the 8-queens search space to 2,057 visited nodes versus 8^8 total positions. - [08:23](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=503s) Valid solutions to the N-queens problem correspond precisely to leaf nodes whose placement vectors match board dimension N. - [08:23](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=503s) Placement vectors can be transformed into visual chessboard matrices using outer product equality (∘.=) with row indices.

## Detailed walkthrough ### [00:07](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=7s) Higher-Order Operators and the Mechanics of Depth-First Search

A sample tree is introduced containing 12 vertices (nodes), consisting of a single root and seven leaves. As the narrator explains:

> “A depth first search or traversal visits the root node and then recursively traverses each subtree in turn.”

APL provides higher-order operators that accept function operands in addition to regular array arguments. Standard primitive operators illustrate this capability: - Reduction (fold), such as product reduction (`×/`) - Each (map), such as reversing each vector in a vector of vectors (`⌽¨`) - Commute (switch), which reverses operand order (e.g., `1 2,⍨ 3 4`)

When writing user-defined operators in Dyalog APL, distinct syntax differentiates operands from arguments: `⍶` (double alpha) and `⍹` (double omega) refer to the left and right function operands, respectively, while `⍺` (single alpha) and `⍵` (single omega) designate the left and right array arguments. To demonstrate, an operator is defined that applies its left operand function twice to its right array argument (`⍺⍺ ⍺⍺ ⍵`), demonstrated by applying enclose (`⊂`) twice to a simple character vector.

---

[01:30](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=90s) Designing the Depth-First Search Operator in APL

The video sets out to construct a general two-operand depth-first search operator, using an informal type notation to formalize the design intent:

> “Depth first search will be an operator which takes an initial accumulator value as left argument and a tree as right argument and returns an accumulated value for the whole tree with a left operand function which takes an accumulator value and a tree node and returns a successor value and a right operand function which takes an accumulator value and a tree node and returns a possibly null vector of subtrees.”

In the implementation, the left operand function `⍶` visits the current node `⍵`, producing a successor to the accumulator value `⍺`. This resulting accumulator is enclosed into a single array element and prepended to the vector of subtrees generated by the right operand function `⍹`. Following the node visit, the search proceeds recursively. The del symbol (`∇`) denotes the derived operator bound with its operand functions, applying an accumulating reduction across the value for the node and each of its child subtrees. Because APL's primitive reduction operator folds right-to-left, the argument vector is reversed and the arguments of the recursive call are commuted (`⍨`). Finally, disclose (`⊃`) unpacks the accumulated result.

```mermaid flowchart TD accTitle: Depth-First Search Operator Execution Flow accDescr: Diagram illustrating how the DFS operator processes an accumulator and node, computes subtrees, and folds recursively.

subgraph Step1 ["1. Visit Current Node"] A["Input: Accumulator ⍺ and Node ⍵"] --> B["Compute Subtrees: ⍺ ⍹ ⍵"] A --> C["Compute Successor: ⊂(⍺ ⍶ ⍵)"] end

subgraph Step2 ["2. Combine and Recurse"] C --> D["Prepend Node Value to Subtrees"] B --> D D --> E["Reverse Argument Vector: ⌽"] E --> F["Recursive Del Fold: ∇⍨/"] end

subgraph Step3 ["3. Return Result"] F --> G["Disclose Final Accumulator: ⊃"] end ```

The operator requires no branching or explicit base-case check: > “We don't need an explicit test for the base case of the recursion if the vector of sub trees is empty the reduction is applied to a single item the value for a leaf node which it just returns as result.”

---

[03:38](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=218s) Traversing Static Nested Array Trees

The operator is tested against a concrete nested vector representation containing seven nodes: one root, two intermediate branches, and four leaves. To search this static structure, the right operand function must inspect the current node `⍵` and return a vector of its subtrees: - If the node's array depth is zero (`0 = ≡⍵`), it is a leaf, returning an empty vector. - Otherwise, it drops the first element to expose the child subtrees (`1↓⍵`).

As the narrator highlights:

> “It is the right operand function alone that projects a tree type onto the subject array.”

By currying the search operator with this right operand, a derived one-operand operator is formed that traverses that specific tree layout while accepting arbitrary accumulating functions as its left operand: - **Counting total nodes**: Initializing the accumulator to `0` with an addition function incrementing by 1 at each step (`{⍺+1}`). - **Counting leaves only**: Incrementing only when the array depth is zero (`{⍺ + 0=≡⍵}`). - **Enlisting leaves**: Initializing with an empty vector (`⍬`) and joining leaf items (`{⍺, (0=≡⍵)/⍵}`).

In all of these cases, excluded nodes supply an identity value (`0` for addition, `⍬` for joining). While flattening nested arrays is directly supported by APL's primitive enlist operator (`∊`), this general formulation shows how custom tree traversals emerge naturally from higher-order operators.

---

[05:28](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=328s) Realizing Trees Dynamically: The N-Queens Problem and Attack Vectors

Rather than traversing a pre-existing in-memory array, subtrees can be synthesized on demand during traversal:

> “The tree can be either concrete above or sub trees can be realized just in time by the right operand function for example when tree searching the solution to a problem such as Sudoku or a chess puzzle.”

To illustrate dynamic tree expansion, the classic eight queens problem is introduced, where eight queens must be positioned on a chessboard so that none attacks another. Working row by row, queen placements are represented as vectors of column indices. For example, three queens placed a knight's move apart in the first three rows produce attack vectors into the fourth row along three directions: - **Right diagonals**: Calculated using the reverse indices of the placement vector's shape (`⌽⍳⍴⍵`). - **Left diagonals**: Offset in the opposite direction (where out-of-bounds positions like column 0 fall off the board). - **Straight ahead**: Directly attacking the occupied column indices (`0×...`).

These directions are captured systematically by scaling an index range across direction offsets `¯1`, `0`, and `1`: - Each direction vector scales the row distance (`¯1 0 1 ר ⊂⌽⍳⍴⍵`). - Adding the current queen positions (`+¨ ⊂⍵`) produces all threatened column coordinates. - Flattening (`∊`) and deduplicating (`∪`) these coordinates yields an `attack` function.

The available columns for placing the next queen in row 4 are simply all board columns except those under attack. Appending each valid candidate column to the current placement vector (`⍵,¨...`) yields the valid successor placements. This function serves directly as the right operand `⍹` to generate subtrees just in time.

---

[08:23](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=503s) Solving N-Queens: Node Counts, Leaf Solutions, and Matrix Display

The formulation is generalized from an 8×8 board to arbitrary $N \times N$ boards by using the length of the first item in the accumulator to determine board dimension $N$. Binding DFS with this dynamic subtree generator creates a problem-specific tree search operator.

Searching an 8×8 board from an empty placement vector (`⍬`) and counting visited nodes using a length-8 zero accumulator reveals the size of the pruned search space:

> “Compare this number with the tree size for all possible placements of eight Queens 8 to the power 8.”

The DFS search explores only 2,057 nodes, compared to the unconstrained combinatorial space of $8^8 = 16,777,216$ positions. Valid solutions reside at the leaves of the tree where the placement vector length equals $N$: - Board sizes $N = 0$ through $10$ yield solution counts of: `1, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724`.

To collect the placements rather than just counting them, the accumulator starts as an empty vector and appends matching paths when row count equals $N$. A 4×4 board produces two distinct solutions. To make the output visually recognizable, each placement vector is formatted into a Boolean chessboard matrix via outer product equality with row indices (`∘.=`).

Wrapping these operations together produces a concise `nqueens` function capable of generating and formatting valid board configurations:

> “Let's pause for a moment to contemplate the code before going to experiment at tryapl.org.”

## Notable quotes > [03:38](https://www.youtube.com/watch?v=DsZdfnlh_d0&t=218s) It is the right operand function alone that projects a tree type onto the subject array.

## Mentioned APL, Dyalog, Dyalog APL, tryapl.org, N-Queens problem, Sudoku

## Video description Step-by-step development of a depth-first tree-search operator in an APL session. NB: The concepts in this little video are fairly concentrated; it may help to pause by hitting the SPACE BAR now and again.

--------------------

GET STARTED

Download the latest version of Dyalog: https://www.dyalog.com/downloads

TAKE PART IN OUR APL COMPETITIONS

THE APL CHALLENGE Learn APL and compete for one of three $100 prizes. Open to all experience levels. https://challenge.dyalog.com

THE APL FORGE Got a problem to solve or a library to share? Use Dyalog APL to build something great — and win £2,500 + an expenses-paid trip to present at a Dyalog user meeting. https://forge.dyalog.com

--------------------

[Source](https://www.youtube.com/watch?v=DsZdfnlh_d0)

中文简报

Dyalog 深度优先算子将八皇后搜索树削减至 2,057 个节点 高阶数组归约通过将动态子树生成直接耦合到累加器折叠中，消除了显式递归分支，从而将指数级搜索空间剪枝为可行解。 本教程演示了如何在 Dyalog APL 中设计一个通用的高阶深度优先搜索算子，该算子在树节点上折叠累加器，而无需显式的基准情况分支。在演示了对静态嵌套数组进行遍历以计算节点数或提取叶节点之后，演示转向了即时动态生成子树。教程利用经典的 N 皇后问题，通过计算对角线和垂直攻击向量来实时剪枝非法放置，从而将八皇后问题的搜索空间从超过 1600 万个潜在状态急剧缩减至仅 2,057 个已访问节点，最后将生成的解格式化为直观的棋盘矩阵。 APL 中的通用双操作数深度优先搜索算子将累加逻辑（左操作数）与子树投影逻辑（右操作数）解耦，从而实现了无需显式基准情况检查的递归。 (1:30) 该树遍历模式无缝涵盖了具体的嵌套数组以及即时动态生成的动态状态树（例如游戏搜索空间）。 (5:28) 将 DFS 应用于八皇后问题，将搜索空间从无约束的 8^8（16,777,216）个候选状态削减至仅 2,057 个已访问节点。 (8:23) 棋盘维度 N = 0 到 10 的有效 N 皇后解的数量被直接计算为 1、1、0、0、2、10、4、40、92、352 和 724。 (8:23)

Source quotes

[3:38] It is the right operand function alone that projects a tree type onto the subject array.

Original transcript

[0:07] this tree has 12 vertices or nodes [0:11] including one root and seven [0:14] leaves a depth first search or traversal [0:18] visits the root node and then [0:20] recursively traverses each subtree in [0:28] turn hey pl's high order [0:32] operators take function operand as well [0:35] as array [0:37] arguments primitive operators include [0:40] reduction or fold times [0:44] reduction each or map reverse each a [0:49] vector [0:53] vectors and commute or switch 1 2 join [0:58] switch 3 4 [1:02] when defining an operator double Alpha [1:05] and double Omega refer to its left and [1:07] right [1:09] operands and single Alpha and Omega to [1:12] its argument [1:14] arrays for example this operator applies [1:18] its left operand function twice to its [1:20] right argument [1:22] array enclose applied twice to a [1:26] character [1:28] vector [1:30] we will Define a two operand operator [1:33] for a depth first tree [1:36] search using an informal type notation [1:39] to declare our intent depth first search [1:43] will be an [1:45] operator which takes an initial [1:47] accumulator value as left [1:49] argument and a tree as right argument [1:52] and returns an accumulated value for the [1:55] whole [1:56] tree with a left upper end function [2:00] which takes an accumulator value and a [2:03] tree node and returns a successor [2:07] value and a right operand function which [2:10] takes an accumulator value and a tree [2:13] node and returns a possibly null Vector [2:17] of sub [2:21] trees coding our [2:26] operator left operand function double [2:28] Alpha visits no [2:30] Omega returning a successor to the [2:33] accumulator [2:34] value enclosed to form a single array [2:38] item which is joined to the vector of [2:41] sub trees returned by right operand [2:44] function double [2:46] Omega after visiting the node the search [2:49] is applied [2:51] recursively Dell refers to the operator [2:54] bound with its operand [2:56] functions with an accumulating reduction [2:59] between the value for the node and each [3:02] of its sub [3:04] trees apl's primitive reduction operator [3:07] folds from the right so we must reverse [3:10] its argument vector and switch the [3:13] arguments of the recursive [3:15] call finally we disclose the resulting [3:19] accumulator [3:20] item we don't need an explicit test for [3:23] the base case of the recursion if the [3:26] vector of sub trees is empty the [3:29] reduction is applied to a single item [3:32] the value for a leaf node which it just [3:34] returns as [3:38] result the tree representation of this [3:40] nested Vector has seven nodes a root two [3:44] branches and Four [3:47] Leaves let's search the [3:50] tree given a tree Omega the right [3:53] operand function must return a possibly [3:56] null Vector of sub [3:58] trees Boolean 0 equals the array depth [4:01] of the node the leaf [4:03] case drop of a vector of sub [4:08] trees it is the right operand function [4:11] alone that projects a tree type onto the [4:14] subject [4:15] array carrying the operator with its [4:18] right upper end derives a one oper end [4:21] operator which traverses a particular [4:24] kind of tree applying its left upper end [4:28] function [4:30] experimenting with various accumulating [4:32] functions we can count the nodes of our [4:35] tree starting with an initial value of [4:39] zero counting just the [4:41] leaves where 0 equals the array depth of [4:45] the [4:46] node or to enlist the leaves into a [4:49] vector start with a null Vector as [4:53] accumulator and [4:58] join taking a only Leaf [5:01] items in these examples notice how a [5:05] zero or null identity item is presented [5:09] to the Primitive accumulating functions [5:11] plus and join for excluded [5:16] cases however the enlisting of a nested [5:20] array is such a common requirement that [5:23] APL provides it as [5:26] primitive the tree can be either [5:28] concrete above or sub trees can be [5:31] realized Just In Time by the right [5:34] operand function for example when trees [5:37] searching the solution to a problem such [5:40] as Sudoku or a chess [5:49] puzzle the challenge is to place eight [5:52] Queens on a chess board in such a way [5:55] that no piece is attacking any other [5:58] let's experiment [6:02] given a vector of the column positions [6:04] of Queens placed a Knights move apart in [6:07] the first three [6:08] rows in which columns could we place a [6:12] queen in the fourth [6:15] row the Queens attack these columns in a [6:19] fourth [6:21] row along right [6:28] diagonals [6:34] or in general for any number of [6:36] rows the reverse of the indices of a [6:39] shape Omega [6:42] vector and these columns in a fourth [6:46] row along left [6:49] diagonals the First Column of which is [6:57] offboard and Fin these columns with [7:01] Straight Ahead [7:08] moves combining these three directions [7:11] neg 1 0 and 1 each times the item of [7:14] their ranges and each offset by their [7:18] current placement [7:23] item and listing this Vector of vectors [7:26] into a simple [7:28] vector [7:30] with these unique [7:34] items we could name this function [7:44] attack the column positions still [7:46] available in the fourth row are all [7:49] columns except for those under [7:55] attack so a vector of the possible four [7:59] row placements is the current placement [8:03] item join [8:05] each [8:08] possibility but this is exactly the [8:11] function for the sub trees of a given [8:13] placement we require for the right upper [8:16] end of [8:23] DFS let's generalize our definition to [8:27] square chest Boards of any size [8:30] the N Queen's problem instead of eight [8:34] we'll arrange for the length of the [8:36] first item in the accumulator to [8:38] determine the board [8:40] size Again The Binding of [8:42] DFS with this right upper and defines a [8:46] tree search specific to the N Queen's [8:49] problem starting with a null placement [8:52] Vector how many nodes are [8:55] there in the full search tree for an 8 [8:58] by8 [9:02] board using a single item length 8 [9:05] accumulator of all zeros and displaying [9:09] only the first of the [9:11] mix compare this number with the tree [9:13] size for all possible placements of [9:15] eight Queens 8 to the Power [9:19] 8 Solutions of the end Queens problem [9:23] are the leaves of the tree for n board [9:26] rows where the number of board [9:29] rows equals the number in the first item [9:32] of the [9:35] accumulator here are the numbers of [9:38] solutions for square Boards of size each [9:42] 0 through [9:48] 10 to collect the [9:57] solutions we accumulate [10:04] at taking just n row [10:11] items starting with an empty solution [10:13] Vector for a 4x4 [10:22] chessboard we see two [10:26] solutions these are more appealing if [10:29] formatted as Boolean [10:32] matrices Vector how to product [10:35] comparison with its [10:44] indices format each [10:47] solution and so a [10:52] function for en [10:55] cre is [10:58] this [11:01] the first few solutions for five [11:04] queens and eight [11:07] Queens let's pause for a moment to [11:10] contemplate the [11:18] code before going to experiment at try [11:23] apl.org [11:27] thank you