⍝ The N-queens Chess problem:

    3 4⍴queens 8
┌───────────────┬───────────────┬───────────────┬───────────────┐
│⍟ · · · · · · ·│⍟ · · · · · · ·│· ⍟ · · · · · ·│· ⍟ · · · · · ·│
│· · · · ⍟ · · ·│· · · · · ⍟ · ·│· · · ⍟ · · · ·│· · · · ⍟ · · ·│
│· · · · · · · ⍟│· · · · · · · ⍟│· · · · · ⍟ · ·│· · · · · · ⍟ ·│
│· · · · · ⍟ · ·│· · ⍟ · · · · ·│· · · · · · · ⍟│⍟ · · · · · · ·│
│· · ⍟ · · · · ·│· · · · · · ⍟ ·│· · ⍟ · · · · ·│· · ⍟ · · · · ·│
│· · · · · · ⍟ ·│· · · ⍟ · · · ·│⍟ · · · · · · ·│· · · · · · · ⍟│
│· ⍟ · · · · · ·│· ⍟ · · · · · ·│· · · · · · ⍟ ·│· · · · · ⍟ · ·│
│· · · ⍟ · · · ·│· · · · ⍟ · · ·│· · · · ⍟ · · ·│· · · ⍟ · · · ·│
├───────────────┼───────────────┼───────────────┼───────────────┤
│· ⍟ · · · · · ·│· ⍟ · · · · · ·│· ⍟ · · · · · ·│· ⍟ · · · · · ·│
│· · · · ⍟ · · ·│· · · · · ⍟ · ·│· · · · · ⍟ · ·│· · · · · · ⍟ ·│
│· · · · · · ⍟ ·│⍟ · · · · · · ·│· · · · · · · ⍟│· · ⍟ · · · · ·│
│· · · ⍟ · · · ·│· · · · · · ⍟ ·│· · ⍟ · · · · ·│· · · · · ⍟ · ·│
│⍟ · · · · · · ·│· · · ⍟ · · · ·│⍟ · · · · · · ·│· · · · · · · ⍟│
│· · · · · · · ⍟│· · · · · · · ⍟│· · · ⍟ · · · ·│· · · · ⍟ · · ·│
│· · · · · ⍟ · ·│· · ⍟ · · · · ·│· · · · · · ⍟ ·│⍟ · · · · · · ·│
│· · ⍟ · · · · ·│· · · · ⍟ · · ·│· · · · ⍟ · · ·│· · · ⍟ · · · ·│
├───────────────┼───────────────┼───────────────┼───────────────┤
│· ⍟ · · · · · ·│· · ⍟ · · · · ·│· · ⍟ · · · · ·│· · ⍟ · · · · ·│
│· · · · · · ⍟ ·│· · · · ⍟ · · ·│· · · · ⍟ · · ·│· · · · · ⍟ · ·│
│· · · · ⍟ · · ·│· ⍟ · · · · · ·│· · · · · · · ⍟│· ⍟ · · · · · ·│
│· · · · · · · ⍟│· · · · · · · ⍟│· · · ⍟ · · · ·│· · · · ⍟ · · ·│
│⍟ · · · · · · ·│⍟ · · · · · · ·│⍟ · · · · · · ·│· · · · · · · ⍟│
│· · · ⍟ · · · ·│· · · · · · ⍟ ·│· · · · · · ⍟ ·│⍟ · · · · · · ·│
│· · · · · ⍟ · ·│· · · ⍟ · · · ·│· ⍟ · · · · · ·│· · · · · · ⍟ ·│
│· · ⍟ · · · · ·│· · · · · ⍟ · ·│· · · · · ⍟ · ·│· · · ⍟ · · · ·│
└───────────────┴───────────────┴───────────────┴───────────────┘

    1 disp queens¨0 1 2 3 4
┌→──┬───┬─────┬───────┬─────────┐
│┌⊖┐│┌→┐│┌⊖──┐│┌⊖────┐│┌→──────┐│
││ ⌽││⍟↓││   ⌽││     ⌽││· ⍟ · ·││
│└⊖┘│└→┘│└──→┘│└────→┘││· · · ⍟││
│   │   │     │       ││⍟ · · ·││
│   │   │     │       ││· · ⍟ ·↓│
│   │   │     │       │└──────→┘│
└──⊖┴──→┴────⊖┴──────⊖┴────────→┘

⍝ Alternative codings:

    ⍝ One-liner for 5-queens:

    ⎕io←0

    {⍵{↑¨↓↓(2|1↓⍳2×⍺)\((↑⍵)∘.=⍳⍺)⊃¨⊂'·⍟'}∪{{(⊃⍋↑⍵)⊃⍵},↑⍵}¨{{⍋⍵}\2/⊂⍵}¨∘{{⍒⍵}\4/⊂⍵}¨⍵{(⍺=,↑⍴¨⍵)/⍵},¨↑⍬{↑(⍺⍺,⍺)∇∇(1↓⍵⍵~¨⍺+(1+⍳⍴⍵⍵)×⊂¯1 0 1)/((⊃⍵⍵)~⍺+¯1 0 1),⊂⍵,⊂⍺⍺,⍺}(1↓⍵⍴⊂⌽⍳⍵)/(⌽⍳⌈⍵÷2),⊂0⍴⊂⍬}5
┌─────────┬─────────┐
│⍟ · · · ·│· ⍟ · · ·│
│· · ⍟ · ·│· · · · ⍟│
│· · · · ⍟│· · ⍟ · ·│
│· ⍟ · · ·│⍟ · · · ·│
│· · · ⍟ ·│· · · ⍟ ·│
└─────────┴─────────┘

    ⍝ Roger Hui's one-liner for 5-queens:

    ⎕io←0

    {⍵{((+/b)⌿⍵),⍺|(,b)/⍳×/⍴b←~↑(⊂⍳⍺)∊¨(↓⍵)+[0]¨⊂(c-⍳c←1↓⍴⍵)∘.ׯ1 0 1}⍣⍵⍳1 0}5
0 2 4 1 3
0 3 1 4 2
1 3 0 2 4
1 4 2 0 3
2 0 3 1 4
2 4 1 3 0
3 0 2 4 1
3 1 4 2 0
4 1 3 0 2
4 2 0 3 1

    ⍝ Alternative coding, which uses the →trav← DFS operator:

    qtrav←{                             ⍝ N-queens using →trav← operator.
        subs←{(⊂⍵),¨(⍳⍴⊃⍺)~atk ⍵}       ⍝ sub-trees of tree-node ⍵.
        accm←{⍺,((⍴⍵)=⍴⊃⍺)/⊂⍵}          ⍝ accumlation of N-placement.
        atk←{↑(⊂⍵)+¯1 0 1×⊂⌽⍳⍴⍵}        ⍝ columns under attack in row 1+⍵.
        fmt←{⍵∘.=⍳⍴⍵}                   ⍝ formatted as bool matrix.
        fmt¨(↓0 ⍵⍴0)accm trav subs ⍬    ⍝ formatted solutions.
    }

    ⎕io←1

    2 5⍴ qtrav 5
┌─────────┬─────────┬─────────┬─────────┬─────────┐
│1 0 0 0 0│1 0 0 0 0│0 1 0 0 0│0 1 0 0 0│0 0 1 0 0│
│0 0 1 0 0│0 0 0 1 0│0 0 0 1 0│0 0 0 0 1│1 0 0 0 0│
│0 0 0 0 1│0 1 0 0 0│1 0 0 0 0│0 0 1 0 0│0 0 0 1 0│
│0 1 0 0 0│0 0 0 0 1│0 0 1 0 0│1 0 0 0 0│0 1 0 0 0│
│0 0 0 1 0│0 0 1 0 0│0 0 0 0 1│0 0 0 1 0│0 0 0 0 1│
├─────────┼─────────┼─────────┼─────────┼─────────┤
│0 0 1 0 0│0 0 0 1 0│0 0 0 1 0│0 0 0 0 1│0 0 0 0 1│
│0 0 0 0 1│1 0 0 0 0│0 1 0 0 0│0 1 0 0 0│0 0 1 0 0│
│0 1 0 0 0│0 0 1 0 0│0 0 0 0 1│0 0 0 1 0│1 0 0 0 0│
│0 0 0 1 0│0 0 0 0 1│0 0 1 0 0│1 0 0 0 0│0 0 0 1 0│
│1 0 0 0 0│0 1 0 0 0│1 0 0 0 0│0 0 1 0 0│0 1 0 0 0│
└─────────┴─────────┴─────────┴─────────┴─────────┘

⍝∇ queens trav

Back to: code

Back to: Workspaces