⍝ 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.
        r←∊(⍵≠0)>(⊂⍳n)∊¨⍵   ⍝ already placed rows.
        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

⍝∇ X

Back to: code

Back to: Workspaces