Sudoku Solver.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's begin by developing a \"contention map\", which shows, for each cell in an `⍵×⍵` Sudoku puzzle, those cells that occupy the same row, column or box:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 2 3\n",
       "4 5 6\n",
       "7 8 9\n",
       "</span>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "                                    ⍝ CONTENTION MAP\n",
    "3 3⍴⍳3×3                            ⍝ matrix of box numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If this expression is not clear, edit and resubmit *part* of it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "APL functions apply to everything to their right, so you can experiment by removing functions from the left of any expression before continuing with the script."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 1 2 2 2 3 3 3\n",
       "4 4 4 5 5 5 6 6 6\n",
       "7 7 7 8 8 8 9 9 9\n",
       "</span>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "3/3 3⍴⍳3×3                          ⍝ 3-replicated (/) along rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 1 2 2 2 3 3 3\n",
       "1 1 1 2 2 2 3 3 3\n",
       "1 1 1 2 2 2 3 3 3\n",
       "4 4 4 5 5 5 6 6 6\n",
       "4 4 4 5 5 5 6 6 6\n",
       "4 4 4 5 5 5 6 6 6\n",
       "7 7 7 8 8 8 9 9 9\n",
       "7 7 7 8 8 8 9 9 9\n",
       "7 7 7 8 8 8 9 9 9\n",
       "</span>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "3⌿3/3 3⍴⍳3×3                        ⍝ 3-replicated (⌿) down columns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on the above, the following function generates this matrix of box numbers for boxes of shape `⍵ ⍵`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 1 2 2 2 3 3 3\n",
       "1 1 1 2 2 2 3 3 3\n",
       "1 1 1 2 2 2 3 3 3\n",
       "4 4 4 5 5 5 6 6 6\n",
       "4 4 4 5 5 5 6 6 6\n",
       "4 4 4 5 5 5 6 6 6\n",
       "7 7 7 8 8 8 9 9 9\n",
       "7 7 7 8 8 8 9 9 9\n",
       "7 7 7 8 8 8 9 9 9\n",
       "</span>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "box ← {⍵⌿⍵/⍵ ⍵⍴⍳⍵×⍵}                ⍝ fn: box numbers\n",
    "box 3                               ⍝ 3×3 boxes for 9×9 puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll start with a smaller, `4×4` Sudoku:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 2 2\n",
       "1 1 2 2\n",
       "3 3 4 4\n",
       "3 3 4 4\n",
       "</span>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "box 2                               ⍝ 2×2 boxes for 4×4 puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Primitive function (`⍳`) generates an `⍵`-array of **indices**. For a matrix, each 2-vector is a row and column number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───┬───┬───┬───┐\n",
       "│1 1│1 2│1 3│1 4│\n",
       "├───┼───┼───┼───┤\n",
       "│2 1│2 2│2 3│2 4│\n",
       "├───┼───┼───┼───┤\n",
       "│3 1│3 2│3 3│3 4│\n",
       "├───┼───┼───┼───┤\n",
       "│4 1│4 2│4 3│4 4│\n",
       "└───┴───┴───┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍳ 4 4                               ⍝ row and column numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Primitive operator **each** (`¨`) applies its operand function between corresponding items of its argument arrays."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Catenating** (`,`) each row-col vector with its box number produces a matrix of row-col-box triples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────┬─────┬─────┬─────┐\n",
       "│1 1 1│1 2 1│1 3 2│1 4 2│\n",
       "├─────┼─────┼─────┼─────┤\n",
       "│2 1 1│2 2 1│2 3 2│2 4 2│\n",
       "├─────┼─────┼─────┼─────┤\n",
       "│3 1 3│3 2 3│3 3 4│3 4 4│\n",
       "├─────┼─────┼─────┼─────┤\n",
       "│4 1 3│4 2 3│4 3 4│4 4 4│\n",
       "└─────┴─────┴─────┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(⍳4 4) ,¨ box 2                     ⍝ row, column and box numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a square Sudoku puzzle, the box size is the square-root of the puzzle size. \n",
    "\n",
    "In APL, the square-root of `⍵` is expressed as `⍵` to the **power** (`*`) one-half (`÷2`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">5 7\n",
       "</span>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "25 49 * ÷2                          ⍝ to the power reciprocal 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... leading to the following function in which `⊃⍵*÷2` means the **first** (`⊃`) item of the square-root of the right argument (`⍵`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────┬─────┬─────┬─────┐\n",
       "│1 1 1│1 2 1│1 3 2│1 4 2│\n",
       "├─────┼─────┼─────┼─────┤\n",
       "│2 1 1│2 2 1│2 3 2│2 4 2│\n",
       "├─────┼─────┼─────┼─────┤\n",
       "│3 1 3│3 2 3│3 3 4│3 4 4│\n",
       "├─────┼─────┼─────┼─────┤\n",
       "│4 1 3│4 2 3│4 3 4│4 4 4│\n",
       "└─────┴─────┴─────┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rcb ← {(⍳⍵),¨box⊃⍵*÷2}              ⍝ fn: row-col-box numbers\n",
    "rcb 4 4                             ⍝ ... for a 4×4 sudoku puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Contention occurs between cells that contain corresponding row, column or box numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are the cells that share a row, column or box with the cell (`⊂`) in the second row, second column:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────┬─────┬─────┬─────┐\n",
       "│0 0 1│0 1 1│0 0 0│0 0 0│\n",
       "├─────┼─────┼─────┼─────┤\n",
       "│1 0 1│1 1 1│1 0 0│1 0 0│\n",
       "├─────┼─────┼─────┼─────┤\n",
       "│0 0 0│0 1 0│0 0 0│0 0 0│\n",
       "├─────┼─────┼─────┼─────┤\n",
       "│0 0 0│0 1 0│0 0 0│0 0 0│\n",
       "└─────┴─────┴─────┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(rcb 4 4) = ⊂2 2 1                  ⍝ cells that share row-col-box with 2 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Each** (`¨`) vector in the above, of which 1 is a **member** (`∊`), represents a row, column or box contention:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 0 0\n",
       "1 1 1 1\n",
       "0 1 0 0\n",
       "0 1 0 0\n",
       "</span>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 ∊¨ (rcb 4 4)=⊂2 2 1               ⍝ cells in contention with cell at 2 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Outer-product** (`∘.`) produces a **rank 4** (`4×4×4×4`) array of all comparisons. As the leading axes of this 256-item array are displayed down the page, it is rather long:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 1 1\n",
       "1 1 0 0\n",
       "1 0 0 0\n",
       "1 0 0 0\n",
       "       \n",
       "1 1 1 1\n",
       "1 1 0 0\n",
       "0 1 0 0\n",
       "0 1 0 0\n",
       "       \n",
       "1 1 1 1\n",
       "0 0 1 1\n",
       "0 0 1 0\n",
       "0 0 1 0\n",
       "       \n",
       "1 1 1 1\n",
       "0 0 1 1\n",
       "0 0 0 1\n",
       "0 0 0 1\n",
       "       \n",
       "       \n",
       "1 1 0 0\n",
       "1 1 1 1\n",
       "1 0 0 0\n",
       "1 0 0 0\n",
       "       \n",
       "1 1 0 0\n",
       "1 1 1 1\n",
       "0 1 0 0\n",
       "0 1 0 0\n",
       "       \n",
       "0 0 1 1\n",
       "1 1 1 1\n",
       "0 0 1 0\n",
       "0 0 1 0\n",
       "       \n",
       "0 0 1 1\n",
       "1 1 1 1\n",
       "0 0 0 1\n",
       "0 0 0 1\n",
       "       \n",
       "       \n",
       "1 0 0 0\n",
       "1 0 0 0\n",
       "1 1 1 1\n",
       "1 1 0 0\n",
       "       \n",
       "0 1 0 0\n",
       "0 1 0 0\n",
       "1 1 1 1\n",
       "1 1 0 0\n",
       "       \n",
       "0 0 1 0\n",
       "0 0 1 0\n",
       "1 1 1 1\n",
       "0 0 1 1\n",
       "       \n",
       "0 0 0 1\n",
       "0 0 0 1\n",
       "1 1 1 1\n",
       "0 0 1 1\n",
       "       \n",
       "       \n",
       "1 0 0 0\n",
       "1 0 0 0\n",
       "1 1 0 0\n",
       "1 1 1 1\n",
       "       \n",
       "0 1 0 0\n",
       "0 1 0 0\n",
       "1 1 0 0\n",
       "1 1 1 1\n",
       "       \n",
       "0 0 1 0\n",
       "0 0 1 0\n",
       "0 0 1 1\n",
       "1 1 1 1\n",
       "       \n",
       "0 0 0 1\n",
       "0 0 0 1\n",
       "0 0 1 1\n",
       "1 1 1 1\n",
       "</span>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 ∊¨ (rcb 4 4) ∘.= rcb 4 4          ⍝ complete contention array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Enclosing** (`⊂`) the first two **axes** `[⍳2]` gives us a `4x4` map of `4×4` contention matrices.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┬───────┐\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "├───────┼───────┼───────┼───────┤\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "├───────┼───────┼───────┼───────┤\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "├───────┼───────┼───────┼───────┤\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "└───────┴───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊂[⍳2] 1 ∊¨ (rcb 4 4) ∘.= rcb 4 4    ⍝ map of contention matrices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Abstracting this as a function of **rcb 4 4**:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┬───────┐\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "├───────┼───────┼───────┼───────┤\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "├───────┼───────┼───────┼───────┤\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "├───────┼───────┼───────┼───────┤\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "└───────┴───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{⊂[⍳2] 1∊¨ ⍵∘.=⍵} rcb 4 4           ⍝ contention map"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and naming the function:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┬───────┐\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "├───────┼───────┼───────┼───────┤\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "├───────┼───────┼───────┼───────┤\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "├───────┼───────┼───────┼───────┤\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 0 0 0│0 1 0 0│0 0 1 0│0 0 0 1│\n",
       "│1 1 0 0│1 1 0 0│0 0 1 1│0 0 1 1│\n",
       "│1 1 1 1│1 1 1 1│1 1 1 1│1 1 1 1│\n",
       "└───────┴───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cmap ← {⊂[⍳2] 1∊¨ ⍵∘.=⍵}            ⍝ fn: contention map for ⍵-puzzle\n",
    "cmap rcb 4 4                        ⍝ contention matrices for 4 4 puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's turn our attention to searching for a solution. We use a **breadth-first search** technique:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "                                    ⍝ Breadth-first search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a small Sudoku puzzle to be solved:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 0 0 0\n",
       "0 0 2 1\n",
       "3 0 0 4\n",
       "0 0 0 0\n",
       "</span>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢s44 ← 4 4⍴ 0 0 0 0  0 0 2 1  3 0 0 4  0 0 0 0      ⍝ 4×4 Sudoku puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **shape** (`⍴`) of **s44** is the vector 4 4:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">4 4\n",
       "</span>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍴ s44                               ⍝ shape of matrix s44"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Primitive **index** function (`⌷`) selects item(s) from an array. Starting (say) at row 1, column 1:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 1 1\n",
       "1 1 0 0\n",
       "1 0 0 0\n",
       "1 0 0 0\n",
       "</span>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃1 1⌷cmap rcb ⍴s44                  ⍝ contention for cell at 1 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **product** (×) of this matrix with the \n",
    "current state shows which numbers may *not* \n",
    "be placed at 1 1:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 0 0 0\n",
       "0 0 0 0\n",
       "3 0 0 0\n",
       "0 0 0 0\n",
       "</span>"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s44 × ⊃1 1⌷cmap rcb ⍴s44            ⍝ number(s) excluded from posn 1 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Excluding** (`~`) these numbers (just the number 3 in this case) \n",
    "from all possible numbers (`⍳4`) reveals which \n",
    "numbers are still available for placing at 1 1:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 2 4\n",
       "</span>"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(⍳4) ~ s44×⊃1 1⌷cmap rcb ⍴s44       ⍝ plays still available at 1 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "with function:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 2 4\n",
       "</span>"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "avl ← {(⍳⊃⍴⍵) ~ ⍵×⊃⍺⌷cmap rcb ⍴⍵}   ⍝ fn: available plays at ⍺ for state ⍵\n",
    "1 1 avl s44                         ⍝ available plays at 1 1 in s44"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need a way to place a given number at a particular position in a given state matrix.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As this operation requires three arguments (number position state), \n",
    "it is convenient to code it as an *operator* with \n",
    "`⍺`-number `⍺⍺`-posn `⍵`-state.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can place the number in a given position with \n",
    "primitive function **take** (`↑`):\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">99 0 0\n",
       " 0 0 0\n",
       "</span>"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 3↑99                              ⍝ 99 extended downwards and rightwards"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 0  0\n",
       "0 0 99\n",
       "</span>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "¯2 ¯3↑99                            ⍝ 99 extended upwards and leftwards"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 0  0 0\n",
       "0 0  0 0\n",
       "0 0 99 0\n",
       "0 0  0 0\n",
       "</span>"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "4 4↑¯3 ¯3↑99                        ⍝ 99 at 3 3 in empty 4 4 grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... and adding the current state:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 0  0 0\n",
       "0 0  2 1\n",
       "3 0 99 4\n",
       "0 0  0 0\n",
       "</span>"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s44 + 4 4↑¯3 ¯3↑99                  ⍝ 99 at 3 3 in s44"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... giving us this \"merge\" operator:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 0  0 0\n",
       "0 0  2 1\n",
       "3 0 99 4\n",
       "0 0  0 0\n",
       "</span>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "at ← {⍵+(⍴⍵)↑(-⍺⍺)↑⍺}               ⍝ op: ⍺ at ⍺⍺ in ⍵\n",
    "99 (3 3 at) s44                     ⍝ 99 at 3 3 in s44"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, merging **each** (`¨`) available state:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┐\n",
       "│1 0 0 0│2 0 0 0│4 0 0 0│\n",
       "│0 0 2 1│0 0 2 1│0 0 2 1│\n",
       "│3 0 0 4│3 0 0 4│3 0 0 4│\n",
       "│0 0 0 0│0 0 0 0│0 0 0 0│\n",
       "└───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 2 4 (1 1 at)¨ ⊂s44                ⍝ next states of s44 at 1 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using our **avl** function to generate the vector of available plays:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┐\n",
       "│1 0 0 0│2 0 0 0│4 0 0 0│\n",
       "│0 0 2 1│0 0 2 1│0 0 2 1│\n",
       "│3 0 0 4│3 0 0 4│3 0 0 4│\n",
       "│0 0 0 0│0 0 0 0│0 0 0 0│\n",
       "└───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(1 1 avl s44) (1 1 at)¨ ⊂s44        ⍝ next states of s44 at 1 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... suggesting this function for a vector of available states:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┐\n",
       "│1 0 0 0│2 0 0 0│4 0 0 0│\n",
       "│0 0 2 1│0 0 2 1│0 0 2 1│\n",
       "│3 0 0 4│3 0 0 4│3 0 0 4│\n",
       "│0 0 0 0│0 0 0 0│0 0 0 0│\n",
       "└───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nxt ← {(⍺ avl ⍵)(⍺ at)¨⊂⍵}          ⍝ fn: next states of ⍵ at ⍺\n",
    "1 1 nxt s44                         ⍝ next states of s44 at 1 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the *following* move, we find *each* possible next state for \n",
    "*each* of these states, choosing a second cell at\n",
    "which to play.\n",
    "\n",
    "In this way, we start to explore the *tree* of possibilities, one level at a time. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's continue from position 1 2. Notice that we bind (`∘`) \n",
    "left argument 1 2 to function **nxt**, so that the *whole* of the vector \n",
    "constitutes the left argument for each (`¨`) application.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────────────────────────┬─────────────────────────┬─────────────────────────┐\n",
       "│┌───────┬───────┬───────┐│┌───────┬───────┬───────┐│┌───────┬───────┬───────┐│\n",
       "││1 2 0 0│1 3 0 0│1 4 0 0│││2 1 0 0│2 3 0 0│2 4 0 0│││4 1 0 0│4 2 0 0│4 3 0 0││\n",
       "││0 0 2 1│0 0 2 1│0 0 2 1│││0 0 2 1│0 0 2 1│0 0 2 1│││0 0 2 1│0 0 2 1│0 0 2 1││\n",
       "││3 0 0 4│3 0 0 4│3 0 0 4│││3 0 0 4│3 0 0 4│3 0 0 4│││3 0 0 4│3 0 0 4│3 0 0 4││\n",
       "││0 0 0 0│0 0 0 0│0 0 0 0│││0 0 0 0│0 0 0 0│0 0 0 0│││0 0 0 0│0 0 0 0│0 0 0 0││\n",
       "│└───────┴───────┴───────┘│└───────┴───────┴───────┘│└───────┴───────┴───────┘│\n",
       "└─────────────────────────┴─────────────────────────┴─────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 2∘nxt¨ 1 1 nxt s44                ⍝ two levels of tree-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The primitive **reduction** operator (`/`), applied to a vector, \n",
    "has the effect of placing its left operand function between each item of its right argument, \n",
    "to produce a scalar result. \n",
    "\n",
    "\n",
    "We can join the sub-vectors with a catenate (`,`) \n",
    "reduction (`/`) of the vector of vectors and disclosing \n",
    "(`⊃`) the resulting scalar:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐\n",
       "│1 2 0 0│1 3 0 0│1 4 0 0│2 1 0 0│2 3 0 0│2 4 0 0│4 1 0 0│4 2 0 0│4 3 0 0│\n",
       "│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│\n",
       "│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│\n",
       "│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│\n",
       "└───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃,/ 1 2∘nxt¨ 1 1 nxt s44            ⍝ two levels of tree-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order that the initial state is not a special case, \n",
    "it helps to *start* with a 1-vector by **ravel**ling (`,`) \n",
    "the **enclose** (`⊂`) of the puzzle matrix:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐\n",
       "│1 2 0 0│1 3 0 0│1 4 0 0│2 1 0 0│2 3 0 0│2 4 0 0│4 1 0 0│4 2 0 0│4 3 0 0│\n",
       "│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│0 0 2 1│\n",
       "│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│\n",
       "│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│\n",
       "└───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃,/1 2∘nxt¨ ⊃,/1 1∘nxt¨ ,⊂s44       ⍝ 2-level search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Continuing from position 2 1:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┬───────┐\n",
       "│1 2 0 0│1 3 0 0│2 1 0 0│2 3 0 0│\n",
       "│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│\n",
       "│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│\n",
       "│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│\n",
       "└───────┴───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃,/2 1∘nxt¨ ⊃,/1 2∘nxt¨ ⊃,/1 1∘nxt¨ ,⊂s44    ⍝ 3-level search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we extract the positions (2 1), (1 2) and (1 1) as left argument (`⍺`) to a containing function:\n",
    "\n",
    "\n",
    "For example: `⊃,/1 2∘nxt¨...`\n",
    "\n",
    "becomes: `1 2{⊃,/⍺∘nxt¨⍵}...`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┬───────┐\n",
       "│1 2 0 0│1 3 0 0│2 1 0 0│2 3 0 0│\n",
       "│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│\n",
       "│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│\n",
       "│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│\n",
       "└───────┴───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nxtv ← {⊃,/⍺∘nxt¨ ⍵}                ⍝ fn: next state vector\n",
    "2 1 nxtv 1 2 nxtv 1 1 nxtv ,⊂s44    ⍝ 3-level search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\"Factoring out\" the `nxtv` function as a **reduction** (`/`), we recode the above 3-level search as:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┬───────┐\n",
       "│1 2 0 0│1 3 0 0│2 1 0 0│2 3 0 0│\n",
       "│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│\n",
       "│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│\n",
       "│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│\n",
       "└───────┴───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃nxtv/ (2 1)(1 2)(1 1)(,⊂s44)       ⍝ 3-level search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Choosing cell (1 3) for our next step:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┬───────┬───────┬───────┐\n",
       "│1 2 3 0│1 2 4 0│1 3 4 0│2 1 3 0│2 1 4 0│2 3 4 0│\n",
       "│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│\n",
       "│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│\n",
       "│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│0 0 0 0│\n",
       "└───────┴───────┴───────┴───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃nxtv/ (1 3)(2 1)(1 2)(1 1)(,⊂s44)  ⍝ 4-level search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The *order* of selecting the cells for the search is unimportant. Let's continue from (4 2):\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐\n",
       "│1 2 3 0│1 2 3 0│1 2 4 0│1 2 4 0│1 3 4 0│1 3 4 0│1 3 4 0│2 1 3 0│2 1 3 0│2 1 4 0│2 1 4 0│2 3 4 0│2 3 4 0│2 3 4 0│\n",
       "│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│\n",
       "│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│3 0 0 4│\n",
       "│0 1 0 0│0 4 0 0│0 1 0 0│0 4 0 0│0 1 0 0│0 2 0 0│0 4 0 0│0 2 0 0│0 4 0 0│0 2 0 0│0 4 0 0│0 1 0 0│0 2 0 0│0 4 0 0│\n",
       "└───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃nxtv/ (4 2)(1 3)(2 1)(1 2)(1 1)(,⊂s44)           ⍝ 5-level search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... (3 2) ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐\n",
       "│1 2 3 0│1 2 4 0│1 3 4 0│1 3 4 0│1 3 4 0│1 3 4 0│2 1 3 0│2 1 4 0│2 3 4 0│2 3 4 0│2 3 4 0│2 3 4 0│\n",
       "│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│4 0 2 1│\n",
       "│3 1 0 4│3 1 0 4│3 2 0 4│3 1 0 4│3 1 0 4│3 2 0 4│3 2 0 4│3 2 0 4│3 2 0 4│3 1 0 4│3 1 0 4│3 2 0 4│\n",
       "│0 4 0 0│0 4 0 0│0 1 0 0│0 2 0 0│0 4 0 0│0 4 0 0│0 4 0 0│0 4 0 0│0 1 0 0│0 2 0 0│0 4 0 0│0 4 0 0│\n",
       "└───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃nxtv/ (3 2)(4 2)(1 3)(2 1)(1 2)(1 1)(,⊂s44)      ⍝ 6-level search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... and (1 4):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┬───────┐\n",
       "│1 2 4 3│2 1 4 3│\n",
       "│4 0 2 1│4 0 2 1│\n",
       "│3 1 0 4│3 2 0 4│\n",
       "│0 4 0 0│0 4 0 0│\n",
       "└───────┴───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃nxtv/ (1 4)(3 2)(4 2)(1 3)(2 1)(1 2)(1 1)(,⊂s44) ⍝ 7-level search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You might like to take a moment to find the complete solution by extending the above list, one item at a time, using the remaining empty cell coordinates: (4 4) (4 3) (2 2) (3 3) (4 1)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a complete search, we just need to supply our reduction with a vector of the positions of *all* empty cells.\n",
    "\n",
    "Here is the matrix of all cell positions:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───┬───┬───┬───┐\n",
       "│1 1│1 2│1 3│1 4│\n",
       "├───┼───┼───┼───┤\n",
       "│2 1│2 2│2 3│2 4│\n",
       "├───┼───┼───┼───┤\n",
       "│3 1│3 2│3 3│3 4│\n",
       "├───┼───┼───┼───┤\n",
       "│4 1│4 2│4 3│4 4│\n",
       "└───┴───┴───┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍳⍴ s44                              ⍝ matrix of positions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "of which, these are the empty ones:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 1 1\n",
       "1 1 0 0\n",
       "0 1 1 0\n",
       "1 1 1 1\n",
       "</span>"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s44=0                               ⍝ 1 → empty cell"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Primitive function **ravel** (`,`) returns a *vector* of the items of its argument array:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐\n",
       "│1 1│1 2│1 3│1 4│2 1│2 2│2 3│2 4│3 1│3 2│3 3│3 4│4 1│4 2│4 3│4 4│\n",
       "└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    ", ⍳⍴ s44                            ⍝ vector of positions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1\n",
       "</span>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    ", s44=0                             ⍝ vector of empties"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Replicate** (`/`) selects empty cells:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐\n",
       "│1 1│1 2│1 3│1 4│2 1│2 2│3 2│3 3│4 1│4 2│4 3│4 4│\n",
       "└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(,s44=0)/,⍳⍴s44                     ⍝ positions of empty cells"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "giving function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐\n",
       "│1 1│1 2│1 3│1 4│2 1│2 2│3 2│3 3│4 1│4 2│4 3│4 4│\n",
       "└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "emt ← {(,⍵=0)/,⍳⍴⍵}                 ⍝ fn: empty cell positions in state ⍵\n",
    "emt s44                             ⍝ empty cell positions in s44"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now find a vector of complete states. In general, there may be many solutions although published Sudoku puzzles typically have only one.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┐\n",
       "│2 1 4 3│\n",
       "│4 3 2 1│\n",
       "│3 2 1 4│\n",
       "│1 4 3 2│\n",
       "└───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃nxtv/(emt s44),⊂,⊂s44              ⍝ vector of all solutions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Abstracting this as a function of the puzzle matrix `s44`:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───────┐\n",
       "│2 1 4 3│\n",
       "│4 3 2 1│\n",
       "│3 2 1 4│\n",
       "│1 4 3 2│\n",
       "└───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "svec ← {⊃nxtv/(emt ⍵),⊂,⊂⍵}         ⍝ fn: solution vector\n",
    "svec s44                            ⍝ solution(s) for s44"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following little function nests the *boxes* of a Sudoku state. A `9×9` puzzle will appear as a `3×3` matrix of `3×3` boxes:\n",
    "\n",
    "(It is left as an \"exercise for the student\" to figure out how this works.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───┬───┐\n",
       "│0 0│0 0│\n",
       "│0 0│2 1│\n",
       "├───┼───┤\n",
       "│3 0│0 4│\n",
       "│0 0│0 0│\n",
       "└───┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sfmt←{⊂[3 4]1 3 2 4⍉(2/(⍴⍵)*÷2)⍴⍵}  ⍝ pleasing format\n",
    "sfmt s44                            ⍝ initial state and"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───┬───┐\n",
       "│2 1│4 3│\n",
       "│4 3│2 1│\n",
       "├───┼───┤\n",
       "│3 2│1 4│\n",
       "│1 4│3 2│\n",
       "└───┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sfmt ⊃svec s44                      ⍝ ... first (⊃) solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The coding of `svec` is rather inefficient because it re-calculates `cmap rcb` at each step:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">{⊃nxtv/(emt ⍵),⊂,⊂⍵}\n",
       "</span>"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "svec                                ⍝ svec calls nxtv for each free cell,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">{⊃,/⍺∘nxt¨⍵}\n",
       "</span>"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nxtv                                ⍝ nxtv calls nxt for each state,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">{(⍺ avl ⍵)(⍺ at)¨⊂⍵}\n",
       "</span>"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nxt                                 ⍝ nxt calls avl and"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">{(⍳⊃⍴⍵)~⍵×⊃⍺⌷cmap rcb⍴⍵}\n",
       "</span>"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "avl                                 ⍝ avl calls cmap rcb ⍴⍵."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can arrange to calculate `(cmap rcb ⍴⍵)` only once and passing it as an additional operand from `svec` to `nxtv` to `nxt` to `avl`.\n",
    "\n",
    "\n",
    "We do this by making `avl`, `nxt` and `nxtv` into *operators*, and receiving additional parameter `(cmap rcb ⍴⍵)` as operand `⍺⍺`. Compare these re-codings with the original versions:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "avl←{(⍳⊃⍴⍵)~⍵×⊃⍺⌷⍺⍺}                ⍝ op avl: receives (cmap rcb ⍴⍵) as ⍺⍺ from\n",
    "nxt←{(⍺(⍺⍺ avl)⍵)(⍺ at)¨⊂⍵}         ⍝ op nxt: receives (cmap rcb ⍴⍵) as ⍺⍺ from\n",
    "nxtv←{⊃,/⍺∘(⍺⍺ nxt)¨⍵}              ⍝ op nxtv: receives (cmap rcb ⍴⍵) as ⍺⍺ from\n",
    "svec←{⊃(⍺⍺ ⍴⍵)nxtv/(emt ⍵),⊂⊂⍵}     ⍝ op svec: receives (cmap∘rcb) as operand ⍺⍺."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bind**ing (`∘`) `cmap` with `rcb` as a function operand to `svec`:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───┬───┐\n",
       "│2 1│4 3│\n",
       "│4 3│2 1│\n",
       "├───┼───┤\n",
       "│3 2│1 4│\n",
       "│1 4│3 2│\n",
       "└───┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sfmt ⊃ cmap∘rcb svec s44            ⍝ ... first (⊃) solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we're in a position to try a larger puzzle.\n",
    "\n",
    "\n",
    "The following sequence specifies each row, starting with a `9×9` matrix of zeros:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "s99 ← 9 9⍴0                         ⍝ input of 9×9 puzzle ...\n",
    "s99[1;] ← 0 0 1 6 9 0 5 0 0         ⍝ 1st row\n",
    "s99[2;] ← 4 0 0 2 7 0 0 0 1         ⍝ 2nd row\n",
    "s99[3;] ← 0 7 0 0 0 0 0 9 0         ⍝ 3rd row\n",
    "s99[4;] ← 0 0 0 0 0 0 0 3 0         ⍝ 4th row\n",
    "s99[5;] ← 0 0 0 4 3 0 0 0 7         ⍝ 5th row\n",
    "s99[6;] ← 0 0 0 7 8 0 6 0 0         ⍝ 6th row\n",
    "s99[7;] ← 0 0 6 0 0 0 8 0 5         ⍝ 7th row\n",
    "s99[8;] ← 0 2 0 1 4 0 0 6 0         ⍝ 8th row\n",
    "s99[9;] ← 0 1 0 3 5 0 0 4 0         ⍝ 9th row"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Display of initial state of `9×9` puzzle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────┬─────┬─────┐\n",
       "│0 0 1│6 9 0│5 0 0│\n",
       "│4 0 0│2 7 0│0 0 1│\n",
       "│0 7 0│0 0 0│0 9 0│\n",
       "├─────┼─────┼─────┤\n",
       "│0 0 0│0 0 0│0 3 0│\n",
       "│0 0 0│4 3 0│0 0 7│\n",
       "│0 0 0│7 8 0│6 0 0│\n",
       "├─────┼─────┼─────┤\n",
       "│0 0 6│0 0 0│8 0 5│\n",
       "│0 2 0│1 4 0│0 6 0│\n",
       "│0 1 0│3 5 0│0 4 0│\n",
       "└─────┴─────┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sfmt s99                            ⍝ 9×9 sudoku puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Naming a function for the format of the first (`⊃`) solution:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───┬───┐\n",
       "│2 1│4 3│\n",
       "│4 3│2 1│\n",
       "├───┼───┤\n",
       "│3 2│1 4│\n",
       "│1 4│3 2│\n",
       "└───┴───┘\n",
       "</span>"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku ← {sfmt⊃cmap∘rcb svec ⍵}     ⍝ Sudoku solver\n",
    "sudoku s44                          ⍝ first solution of smaller puzzle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────┬─────┬─────┐\n",
       "│2 8 1│6 9 3│5 7 4│\n",
       "│4 6 9│2 7 5│3 8 1│\n",
       "│5 7 3│8 1 4│2 9 6│\n",
       "├─────┼─────┼─────┤\n",
       "│7 9 2│5 6 1│4 3 8│\n",
       "│6 5 8│4 3 9│1 2 7│\n",
       "│1 3 4│7 8 2│6 5 9│\n",
       "├─────┼─────┼─────┤\n",
       "│3 4 6│9 2 7│8 1 5│\n",
       "│9 2 5│1 4 8│7 6 3│\n",
       "│8 1 7│3 5 6│9 4 2│\n",
       "└─────┴─────┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku s99                          ⍝ first solution of larger puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A Generalisation\n",
    "\n",
    "APL makes it easy to extend functions to arrays of higher rank.\n",
    "\n",
    "\n",
    "To demonstrate this, let's convert our code to solve a 3D variant of Sudoku.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">0 0 0\n",
       "8 1 0\n",
       "0 0 2\n",
       "     \n",
       "0 6 0\n",
       "0 7 0\n",
       "9 0 4\n",
       "     \n",
       "5 0 0\n",
       "0 0 3\n",
       "0 0 0\n",
       "</span>"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "                                    ⍝ 3D Sudoku\n",
    "s333 ← 3 3 3⍴0                      ⍝ input of 3×3×3 puzzle\n",
    "s333[1;;] ← 3 3 ⍴  0 0 0  8 1 0  0 0 2   ⍝ 1st plane\n",
    "s333[2;;] ← 3 3 ⍴  0 6 0  0 7 0  9 0 4   ⍝ 2nd plane\n",
    "s333[3;;] ← 3 3 ⍴  5 0 0  0 0 3  0 0 0   ⍝ 3rd plane\n",
    "s333                                ⍝ 3D Sudoku puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We choose slightly different contention conditions: \n",
    "there are no \"boxes\" but numbers must not be repeated in any of the nine x, y, or z planes.\n",
    "\n",
    "\n",
    "First, we generalise our `cmap` function: \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">{⊂[⍳2]1∊¨⍵∘.=⍵}\n",
       "</span>"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cmap                                ⍝ 2D-specific cmap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "to **enclose** (`⊂`) an *appropriate* number of **axes** `[`...`]`.\n",
    "\n",
    "\n",
    "This is the rank (`⍴⍴` the shape of the shape) of the argument array: \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "cmap ← {⊂[⍳⍴⍴⍵]1∊¨⍵∘.=⍵}            ⍝ rank-invariant cmap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, using primitive function (`⍳`) in place of the `rcb` function, as there are no boxes:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "sudoku3D ← {⊃cmap∘⍳ svec ⍵}         ⍝ 3D Sudoku solver"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we must generalise `avl` to return available numbers for a *subarray*.\n",
    "\n",
    "For 2D Sudoku this will continue to be the numbers for a row or column vector \n",
    "and for the 3D version it will be those for a whole plane:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\"> ∇avl \n",
       "</span>"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "avl                                 ⍝ 2D-specific avl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2 3 8\n",
       "</span>"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "avl ← {(⍳×/1↓⍴⍵)~⍵×⊃⍺⌷⍺⍺}           ⍝ rank-invariant avl\n",
    "  1 1 ((cmap rcb ⍴s99 )avl)  s99    ⍝ 2D plays at 1 1 for s99"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">3 4 7\n",
       "</span>"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 1 1 ((cmap ⍳   ⍴s333)avl) s333    ⍝ 3D plays at 1 1 1 for s333"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our 2D Sudoku solver continues to work as before:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────┬─────┬─────┐\n",
       "│2 8 1│6 9 3│5 7 4│\n",
       "│4 6 9│2 7 5│3 8 1│\n",
       "│5 7 3│8 1 4│2 9 6│\n",
       "├─────┼─────┼─────┤\n",
       "│7 9 2│5 6 1│4 3 8│\n",
       "│6 5 8│4 3 9│1 2 7│\n",
       "│1 3 4│7 8 2│6 5 9│\n",
       "├─────┼─────┼─────┤\n",
       "│3 4 6│9 2 7│8 1 5│\n",
       "│9 2 5│1 4 8│7 6 3│\n",
       "│8 1 7│3 5 6│9 4 2│\n",
       "└─────┴─────┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku s99                          ⍝ 2D solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and our 3D solver solves the 3D puzzle s333:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">3 4 9\n",
       "8 1 6\n",
       "7 5 2\n",
       "     \n",
       "1 6 8\n",
       "2 7 5\n",
       "9 3 4\n",
       "     \n",
       "5 2 7\n",
       "4 9 3\n",
       "6 8 1\n",
       "</span>"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku3D s333                       ⍝ 3D solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice how few changes were needed to generalise our program for a higher dimensional puzzle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "\n",
    "There are many ways to solve Sudoku. The method used here illustrates a *Pure Functional Programming* approach.\n",
    "\n",
    "\n",
    "The code we have developed consists only of the application of functions and operators to their arguments and operands. In particular, it contains:\n",
    "\n",
    "\n",
    "No explicit representation of state (no variables).\n",
    "\n",
    "No explicit control structures (no conditionals, loops, etc)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">sudoku ← {sfmt⊃cmap∘rcb svec ⍵}       \n",
       "  sfmt ← {⊂[3 4]1 3 2 4⍉(2/(⍴⍵)*÷2)⍴⍵}\n",
       "  cmap ← {⊂[⍳⍴⍴⍵]1∊¨⍵∘.=⍵}            \n",
       "  rcb ← {(⍳⍵),¨box⊃⍵*÷2}              \n",
       "    box ← {⍵⌿⍵/⍵ ⍵⍴⍳⍵×⍵}              \n",
       "  svec ← {⊃(⍺⍺⍴⍵)nxtv/(emt ⍵),⊂⊂⍵}    \n",
       "    nxtv ← {⊃,/⍺∘(⍺⍺ nxt)¨⍵}          \n",
       "      nxt ← {(⍺(⍺⍺ avl)⍵)(⍺ at)¨⊂⍵}   \n",
       "        avl ← {(⍳×/1↓⍴⍵)~⍵×⊃⍺⌷⍺⍺}     \n",
       "        at ← {⍵+(⍴⍵)↑(-⍺⍺)↑⍺}         \n",
       "    emt ← {(,⍵=0)/,⍳⍴⍵}               \n",
       "</span>"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "]defs sudoku -t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For alternative codings of Sudoku in APL, see \n",
    "[dfns.dyalog.com/n_sudoku.htm](http://dfns.dyalog.com/n_sudoku.htm).\n",
    "\n",
    "## Credits\n",
    "Algorithm:   [Arthur Whitney](http://www.kparc.com/examples/game.k)\n",
    "Inspiration: [Roger Hui](http://www.jsoftware.com/papers/nqueens.htm)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Dyalog APL",
   "language": "apl",
   "name": "dyalog-kernel"
  },
  "language_info": {
   "file_extension": ".apl",
   "mimetype": "text/apl",
   "name": "APL"
  },
  "tryapl": {
   "category": "Interesting Explorations",
   "description": "Developing a Sudoku Solver",
   "name": "Sudoku Solver"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}