Skip to content

Instantly share code, notes, and snippets.

@dmaestro

dmaestro/8queens.pl

Created October 12, 2017 23:28
Show Gist options
  • Save dmaestro/3e0e8c31f20f9288296754d4585deb4c to your computer and use it in GitHub Desktop.
Save dmaestro/3e0e8c31f20f9288296754d4585deb4c to your computer and use it in GitHub Desktop.
Download ZIP
Fundamental Solutions to Eight Queens Problem
Raw
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;
}
Raw
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment