Fundamental Solutions to Eight Queens Problem

8queens.pl

use v6;

constant size := 8;
my @corners = map { $_[0] * size + $_[1] }, ((0, size-1) X (0, size-1));

our class Square is Int {
    has Int $!piece;

    method new (|) {
        Metamodel::Primitives.rebless(
            callsame,
            self);
    }
    method x {
        self % size;
    }
    method y {
        self div size;
    }
    method place (Int $piece where * > 0) {
        $!piece = $piece;
    }
    method threaten {
        $!piece = 0;
    }
    method is-safe ( --> Bool ) {
        ! defined $!piece;
    }
    method attacked_by (Square $opponent --> Bool) {
        return True if self.x == $opponent.x or self.y == $opponent.y;
        return True if abs(self.x - $opponent.x) == abs(self.y - $opponent.y);
        return False;
    }
    method occupied {
        defined $!piece and $!piece > 0;
    }
    method symbol {
        my $background = (self.x + self.y) %% 2 ?? '   ' !! '///';
        return $background if self.is-safe;
        my $mark = 'x';
        $mark = $!piece.Str if $!piece;
        return $background.substr(0,1) ~ $mark ~ $background.substr(2,1);
    }
    #clockwise rotation
    method rot {
        my List $rotmat = (( 0, 1, 0 ), (-1, 0, size-1 ));
        my $coord = (((self.x, self.y, 1) xx 2) ZZ* $rotmat.list).List.map({ [+] $_ });
        self.new( $coord[0] + $coord[1] * size );
    }
}

class Board is Array {
    has Pair $!signature;

    method new (|) {
        Metamodel::Primitives.rebless(
            callwith( flat map { Square.new($_) }, ^(size * size) ),
            self);
    }
    method clone (|) {
        $!signature = Nil;
        my $c = callsame;
        for |$c <-> $s {
            next if ! $s.is-safe;
            $s = Square.new($s.Int);
        }
        Metamodel::Primitives.rebless(
            $c,
            self);
    }
    method show () {
        sub border {
            say |flat '+', '---+' xx size;
        }

        sub line (Int $r) {
            say |flat '|', map {
                self[$r * size + $_].symbol, '|',
            }, ^size;
        }
        border;
        for ^size -> $row {
            line($row);
            border;
        }
    }
    method place_queen (Int $count, Int :$square ) {
        $!signature = Nil;
        self[$square].place($count);
        for self.grep({ .is-safe }) -> $safe_square {
            if $safe_square.attacked_by(self[$square]) {
                $safe_square.threaten;
            }
        }
    }
    method _signature (--> Pair) {
        $!signature //=
        (   gather
                for @corners.map({self[$_]}) -> Square $corner {
                    take $corner => self
                        .grep({ .occupied })
                        .map({ abs(.x - $corner.x) + abs(.y - $corner.y) })
                        .sort.List;
                }
        ).min( { .value } );
    }
    method signature {
        self._signature.value;
    }
    method coords (--> List) {
        my $corner = self._signature.key;
        self.grep({ .occupied })
            .map({ ( $corner.x ?? $corner.x - .x !! .x,
                     $corner.y ?? $corner.y - .y !! .y ) })
            .List
    }
    method flip (--> List) {
        my $corner = self._signature.key;
        self.grep({ .occupied })
            .map({ ( $corner.y ?? $corner.y - .y !! .y,
                     $corner.x ?? $corner.x - .x !! .x ) })
            .List
    }
    method rot (--> List) {
        my $corner = self._signature.key.rot;
        self.grep({ .occupied })
            .map({ ( $corner.x ?? $corner.x - .x !! .x,
                     $corner.y ?? $corner.y - .y !! .y ) })
            .List
    }
}

multi sub infix:<eqv> (Board $l, Board $r) {
    $l.signature eqv $r.signature
    && ( $l.coords.sort eqv $r.coords.sort
        || $l.flip.sort eqv $r.coords.sort
        || $l.coords.sort eqv $r.rot.sort
        || $l.flip.sort eqv $r.rot.sort )
}

sub solve ( Board $b, Int $level = 0 ) {
    if ($level == size) {
        take $b; # include solution if we placed all queens
        return;
    }
    for $b.grep({       # for all unthreatened squares on board $b
        .y == $level    #   row-by-row
        && .is-safe
        # Only half of the first row need be checked (symmetry)
        && ( $level || .x < (size+1) div 2 )    # Only half of the first row need be checked
    }) {
        my $board = $b.clone;
        # place a queen
        $board.place_queen( $level + 1, square => .Int );
        # recurse for the next level (row)
        &?ROUTINE($board, $level + 1);
    }
}

# get all the unique (by symmetry) solutions and show them
for (gather solve(Board.new)).List.unique( :with(&[eqv]) ) {
    .show;
    .signature.say;
    ''.say;
}

results.txt

+---+---+---+---+---+---+---+---+
| 1 |/x/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/2/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| x |/3/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| 4 |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| 5 |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/6/| x |
+---+---+---+---+---+---+---+---+
| x |/7/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| 8 |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
(0 5 6 7 8 9 10 11)

+---+---+---+---+---+---+---+---+
| 1 |/x/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| 2 |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| x |/3/|
+---+---+---+---+---+---+---+---+
|/x/| x |/4/| x |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| 5 |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| 6 |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/7/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/8/| x |/x/| x |
+---+---+---+---+---+---+---+---+
(0 5 6 7 8 9 10 11)

+---+---+---+---+---+---+---+---+
| x |/1/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| 2 |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/3/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/x/| 4 |
+---+---+---+---+---+---+---+---+
| x |/x/| 5 |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/6/| x |/x/| x |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| 7 |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/8/| x |/x/| x |
+---+---+---+---+---+---+---+---+
(1 4 5 6 7 10 11 12)

+---+---+---+---+---+---+---+---+
| x |/1/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/2/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| 3 |/x/|
+---+---+---+---+---+---+---+---+
|/4/| x |/x/| x |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| 5 |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/x/| 6 |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/7/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| 8 |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
(1 3 5 6 8 10 11 12)

+---+---+---+---+---+---+---+---+
| x |/1/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/2/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| 3 |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| 4 |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| 5 |/x/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/x/| 6 |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/7/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/8/| x |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
(1 4 5 6 8 9 11 12)

+---+---+---+---+---+---+---+---+
| x |/1/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| 2 |/x/| x |
+---+---+---+---+---+---+---+---+
| 3 |/x/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/4/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/5/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/x/| 6 |
+---+---+---+---+---+---+---+---+
| x |/x/| 7 |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/8/| x |/x/| x |
+---+---+---+---+---+---+---+---+
(1 2 6 7 8 9 11 12)

+---+---+---+---+---+---+---+---+
| x |/1/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| 2 |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| x |/3/|
+---+---+---+---+---+---+---+---+
|/x/| x |/4/| x |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| 5 |/x/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| 6 |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| 7 |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/8/| x |/x/| x |
+---+---+---+---+---+---+---+---+
(1 4 5 6 8 9 11 12)

+---+---+---+---+---+---+---+---+
| x |/1/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/2/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| 3 |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| 4 |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| x |/5/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/6/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| 7 |/x/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| 8 |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
(1 3 6 7 8 9 10 12)

+---+---+---+---+---+---+---+---+
| x |/1/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/2/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| 3 |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/x/| 4 |
+---+---+---+---+---+---+---+---+
| 5 |/x/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| 6 |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/7/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/8/| x |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
(1 4 6 7 8 9 10 11)

+---+---+---+---+---+---+---+---+
| x |/x/| 1 |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/2/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/3/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/x/| 4 |
+---+---+---+---+---+---+---+---+
| 5 |/x/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/6/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/7/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| 8 |/x/| x |
+---+---+---+---+---+---+---+---+
(2 3 4 5 9 10 11 12)

+---+---+---+---+---+---+---+---+
| x |/x/| 1 |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/2/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| x |/3/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| 4 |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| 5 |/x/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| x |/6/| x |
+---+---+---+---+---+---+---+---+
| x |/7/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| 8 |/x/| x |
+---+---+---+---+---+---+---+---+
(2 3 5 7 8 9 10 12)

+---+---+---+---+---+---+---+---+
| x |/x/| 1 |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/x/| 2 |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/3/| x |/x/| x |/x/| x |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| x |/4/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| x |/5/|
+---+---+---+---+---+---+---+---+
|/6/| x |/x/| x |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
| x |/x/| x |/x/| x |/x/| 7 |/x/|
+---+---+---+---+---+---+---+---+
|/x/| x |/x/| 8 |/x/| x |/x/| x |
+---+---+---+---+---+---+---+---+
(2 3 4 7 8 9 11 12)