Porting APL Sudoku solver(s)

[shnarazk]

• https://tryapl.org/
• https://dfns.dyalog.com/n_sudoku_bfs.htm
• https://www.youtube.com/watch?v=DmT80OseAGs

Sudoku←{                                        ⍝ Solution vector for square Sudoku puzzle ⍵.
    BoxNos  ← {⍵⌿⍵/⍵ ⍵⍴⍳⍵*2}                    ⍝ box numbers for a puzzle of size ⍵*2
    RowColBoxNos  ← {(⍳⍵),¨BoxNos⊃⍵*0.5}        ⍝ row/column/box numbers
    ContentionMap ← {⊂[⍳2] 1∊¨⍵∘.=⍵}            ⍝ contention map for puzzle ⍵
    CMAP ← ContentionMap RowColBoxNos ⍴⍵        ⍝ fixed contention map for current puzzle

    Available  ← {(⍳⊃⍴⍵)~⍵×⊃⍺⌷CMAP}             ⍝ list of available numbers at position ⍺ for puzzle ⍵
    EmptyCells ← {(,⍵=0)/,⍳⍴⍵}                  ⍝ row & column indices of empty cells
    Placements ← {(⍺ Available ⍵)⊣@(⊂⍺)¨⊂⍵}     ⍝ puzzle ⍵ with all available numbers at position ⍺
    AllPlacements ← {⊃,/⍺∘Placements¨⍵}         ⍝ all possible Placements at ⍺ based on partial solutions ⍵
    Solutions ← {⊃AllPlacements/(EmptyCells ⍵),⊂⊂⍵}  ⍝ solution vector

    Solutions ⍵
}

[shnarazk]

Converting one by one

Box ← {>𝕩/<˘𝕩‿∘⥊𝕩/1+↕𝕩⋆2}
# (1+↕4‿4) ∾¨ Box 2
Rcb ← {(1+↕𝕩)∾¨Box ⊑0.5⋆˜𝕩}
# Rcb 4‿4
Cmap ← {<˘˘1 (⊑∊)¨ =⌜˜𝕩}
Cmap Rcb 4‿4

Avl ← {(1+↕⊑≢𝕩)(¬∘∊/⊣)(0⊸≠)⊸/⥊𝕩×𝕨⊑Cmap Rcb ≢𝕩}

Why does not Avl respect the initial value???

Avl ← {0≠𝕨⊑𝕩? ⋈𝕨⊑𝕩; (1+↕⊑≢𝕩)(¬∘∊/⊣)(0⊸≠)⊸/⥊𝕩×𝕨⊑Cmap RCB ≢𝕩}

Nxt  ← {w F x:(𝕨 Avl 𝕩) {𝕨˙⌾(w⊸⊑)𝕩}¨ <𝕩}
Nxtv ← {∾𝕨⊸Nxt¨𝕩}        # use like (<s44)Nxtv´⟨0‿0,0‿1,1‿0⟩

Wait.
Why does not Avl respect the initial value???

Avl ← {0≠𝕨⊑𝕩? ⋈𝕨⊑𝕩; (1+↕⊑≢𝕩)(¬∘∊/⊣)(0⊸≠)⊸/⥊𝕩×𝕨⊑Cmap RCB ≢𝕩}

Now we can do:

(<s44)Nxtv´⥊↕≢s44

[shnarazk]

https://www.youtube.com/watch?v=YnJ1Yy6gpmA

• ⍺ nxt ⍵ means 'AssignTheFirstHole of ⍺ to ⍵'
• ∇ is recursion.

Sol ← {
    terminated? answer;    # Is there a way to 'break'?
    𝕊¨ nextstates          # This is depth-first search.
}

TIL

• depth-frist search: {𝕊∘N¨𝕩}
• width-frist search: {𝕊 N¨𝕩}

What a beautiful world!