X←{ ⍝ Exact cover: Knuth's Algorithm X. ⍺←1∨.∨⍵ ⍝ all cols required by default. x←⍳⍴⍺ ⍝ column indices. d←(x~⍺/x)∘.=x ⍝ dummy rows for optional columns. z←{ ⍝ cover vector. r c←⍴⍵ ⍝ number of rows and columns. c=0:r⍴0 ⍝ empty matrix: success. n←+⌿⍵ ⍝ number of covers per column. f←(<\n=⌊/n)/⍵ ⍝ first column with fewest 1s. ⍵ ∇{ ⍝ ⍺ is constraint matrix. ~1∊⍵:0 ⍝ no rows: failure. f←<\⍵ ⍝ first row selector. c←,f⌿⍺ ⍝ cols selected by first row. r←∨/c/⍺ ⍝ rows covered by selected cols. s←⍺⍺(~c)/(~r)⌿⍺ ⍝ sub-matrix covers. s≡0:⍺ ∇ f<⍵ ⍝ failure: try a different row. f∨(~r)\s ⍝ success: row f included. },f ⍝ ⍵ is vector of marked rows. }⍵⍪d ⍝ exact cover. z≡0:0 ⍝ failure: 0 (-+/~⍺)↓z ⍝ without dummy rows. } code_colours test script Back to: notes Back to: Workspaces