```⍝ Knuth's Algorithm X:

M←⍉⍪ 1 0 0 1 0 0 1      ⍝ http://en.wikipedia.org/wiki/Algorithm_X
M ⍪← 1 0 0 1 0 0 0
M ⍪← 0 0 0 1 1 0 1
M ⍪← 0 0 1 0 1 1 0
M ⍪← 0 1 1 0 0 1 1
M ⍪← 0 1 0 0 0 0 1

X M                     ⍝ Rows that form exact cover.
0 1 0 1 0 1

(X M)⌿M                 ⍝ covering rows
1 0 0 1 0 0 0
0 0 1 0 1 1 0
0 1 0 0 0 0 1

1∧.=+⌿(X M)⌿M           ⍝ condition for exact cover.
1

M←⍉⍪ 0 0 1 0 1 1 0
M ⍪← 1 0 0 1 0 0 1
M ⍪← 0 1 1 0 0 1 0
M ⍪← 1 0 0 1 0 0 0
M ⍪← 0 1 0 0 0 0 1
M ⍪← 0 0 0 1 1 0 1

X M
1 0 0 1 1 0

(X M)⌿M                 ⍝ exact cover
0 0 1 0 1 1 0
1 0 0 1 0 0 0
0 1 0 0 0 0 1

1∧.=+⌿(X M)⌿M           ⍝ condition for exact cover.
1
1 disp X¨((⍳2 2)-⍳1)⍴¨1 ⍝ edge cases.
┌→┬─┐
↓0│0│
├⊖┼⊖┤
│0│1│
└→┴→┘

X 3 4↑=/¨⍳3 3           ⍝ too wide: uncovered columns.
0
X 4 3↑=/¨⍳3 3           ⍝ too tall: not all rows needed.
1 1 1 0

X=/¨⍳3 3                ⍝ identity: just right.
1 1 1

⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝ Exact cover Sudoku solver:

smat←{                              ⍝ Matrix for ⍵ ⍵-Sudoku puzzle.
z←,[⍳6],[6+⍳4]⍳10⍴⍵*÷2          ⍝ cell coordinate properties.
row←↓1 1 0 0 1 1 1 1 1 1/↑z     ⍝ each row must contain each number.
col←↓0 0 1 1 1 1 1 1 1 1/↑z     ⍝   .. col  ..  ..  ..  ..  ..  ..
box←↓1 0 1 0 1 1 1 1 1 1/↑z     ⍝   .. box  ..  ..  ..  ..  ..  ..
all←↓1 1 1 1 0 0 1 1 1 1/↑z     ⍝ each cell must contain a number.
same←≡/∘(1 0 0 0 1 0 0 0∘⊂)     ⍝ matching pairs.
same¨row,col,box,all            ⍝ constraints matrix for ⍵ ⍵-puzzle.
}

sudokuX←{⎕IO←1          ⍝ Exact cover Sudoku solver.
n n←⍴⍵              ⍝ n×n puzzle.
⍺←smat n            ⍝ generic ⍵×⍵ constraint matrix.
m←(~r)⌿⍺            ⍝ reduced matrix.
f←X m               ⍝ exact cover.
z←(~r)\f            ⍝ merge of placements.
n n⍴z/(⍴z)⍴⍳n       ⍝ solution matrix.
}

s44 ← 4 4⍴ 0 0 0 0, 0 0 2 1, 3 0 0 4, 0 0 0 0

s44                     ⍝ puzzle.
0 0 0 0
0 0 2 1
3 0 0 4
0 0 0 0

sudokuX s44             ⍝ solution.
2 1 4 3
4 3 2 1
3 2 1 4
1 4 3 2

⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝ Exact cover N-Queens:

queensX←{               ⍝ Exact cover N-Queens.
m←⍳3/⍵              ⍝ cell coordinate properties.
r←=/¨1 0 1∘/¨m      ⍝ each rank must contain one queen.
f←=/¨0 1 1∘/¨m      ⍝  ..  file  ..     ..      ..

dm←-/¨⍳2/⍵          ⍝ diagonals.
du←{⍵[⍋⍵]}∪,dm      ⍝ unique diagnonals.
x←dm∘.=du           ⍝ left diagonals.
y←(⊖dm)∘.=du        ⍝ right diagonals.

m←,[⍳2]x,y,r,f      ⍝ constraints matrix.
d←~(⍳1↓⍴m)∊⍳2×⍴du   ⍝ mask of required cols.
⍵ ⍵⍴d X m           ⍝ exact cover - matrix of queens.
}

queensX¨ 0 to 8
┌┬─┬───┬─────┬───────┬─────────┬───────────┬─────────────┬───────────────┐
││1│0 0│0 0 0│0 1 0 0│0 0 0 0 1│0 0 0 0 1 0│0 0 0 0 0 0 1│0 0 0 0 0 0 0 1│
││ │0 0│0 0 0│0 0 0 1│0 1 0 0 0│0 0 1 0 0 0│0 0 0 0 1 0 0│0 0 0 1 0 0 0 0│
││ │   │0 0 0│1 0 0 0│0 0 0 1 0│1 0 0 0 0 0│0 0 1 0 0 0 0│1 0 0 0 0 0 0 0│
││ │   │     │0 0 1 0│1 0 0 0 0│0 0 0 0 0 1│1 0 0 0 0 0 0│0 0 1 0 0 0 0 0│
││ │   │     │       │0 0 1 0 0│0 0 0 1 0 0│0 0 0 0 0 1 0│0 0 0 0 0 1 0 0│
││ │   │     │       │         │0 1 0 0 0 0│0 0 0 1 0 0 0│0 1 0 0 0 0 0 0│
││ │   │     │       │         │           │0 1 0 0 0 0 0│0 0 0 0 0 0 1 0│
││ │   │     │       │         │           │             │0 0 0 0 1 0 0 0│
└┴─┴───┴─────┴───────┴─────────┴───────────┴─────────────┴───────────────┘

Alpha ##.test'pentominos'   ⍝ pentomino-tiling tutorial

PX←{⍵{⍉(⍵⍴2)⊤{⍵/⍳⍴⍵}1∧.=(⍉⍺)+.∧(⍵⍴2)⊤⍳2*⍵}⍬⍴⍴⍵}     ⍝ Phil's coding

1∧.=+⌿(,PX M)⌿M             ⍝ condition for exact cover.
1

Back to: code

Back to: Workspaces
```