Solve a Numbrix puzzle: Difference between revisions
m
→{{header|Perl 6}}: Include referenced routine to make runnable file, combine files for ease of testing
(Added Kotlin) |
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Include referenced routine to make runnable file, combine files for ease of testing) |
||
Line 1,066:
=={{header|Perl 6}}==
This uses a Warnsdorff solver, which cuts down the number of tries by more than a factor of six over the brute force approach. This same solver is used in:
* [[Solve a Hidato puzzle#Perl_6|Solve a Hidato puzzle]]
* [[Solve a Hopido puzzle#Perl_6|Solve a Hopido puzzle]]
* [[Solve a Holy Knight's tour#Perl_6|Solve a Holy Knight's tour]]
* [[Solve a Numbrix puzzle#Perl_6|Solve a Numbrix puzzle]]
* [[Solve the no connection puzzle#Perl_6|Solve the no connection puzzle]]
<lang perl6>my @adjacent = [-1, 0],
[ 0, -1], [ 0, 1],
Line 1,081 ⟶ 1,088:
__ __ 24 21 __ 1 2 __ __
__ __ __ __ __ __ __ __ __
END
# And
say '';
0 0 0 0 0 0 0 0 0
0 11 12 15 18 21 62 61 0
Line 1,106 ⟶ 1,103:
0 43 44 47 48 51 76 77 0
0 0 0 0 0 0 0 0 0
END
sub solveboard($board) {
my $max = +$board.comb(/\w+/);
my $width = $max.chars;
my @grid;
my @known;
my @neigh;
my @degree;
@grid = $board.lines.map: -> $line {
[ $line.words.map: { /^_/ ?? 0 !! /^\./ ?? Rat !! $_ } ]
}
sub neighbors($y,$x --> List) {
eager gather for @adjacent {
my $y1 = $y + .[0];
my $x1 = $x + .[1];
take [$y1,$x1] if defined @grid[$y1][$x1];
}
}
for ^@grid -> $y {
for ^@grid[$y] -> $x {
if @grid[$y][$x] -> $v {
@known[$v] = [$y,$x];
}
if @grid[$y][$x].defined {
@neigh[$y][$x] = neighbors($y,$x);
@degree[$y][$x] = +@neigh[$y][$x];
}
}
}
print "\e[0H\e[0J";
my $tries = 0;
try_fill 1, @known[1];
sub try_fill($v, $coord [$y,$x] --> Bool) {
return True if $v > $max;
$tries++;
my $old = @grid[$y][$x];
return False if $old and $old != $v;
return False if @known[$v] and @known[$v] !eqv $coord;
@grid[$y][$x] = $v; # conjecture grid value
print "\e[0H"; # show conjectured board
for @grid -> $r {
say do for @$r {
when Rat { ' ' x $width }
when 0 { '_' x $width }
default { .fmt("%{$width}d") }
}
}
my @neighbors = @neigh[$y][$x][];
my @degrees;
for @neighbors -> \n [$yy,$xx] {
my $d = --@degree[$yy][$xx]; # conjecture new degrees
push @degrees[$d], n; # and categorize by degree
}
for @degrees.grep(*.defined) -> @ties {
for @ties.reverse { # reverse works better for this hidato anyway
return True if try_fill $v + 1, $_;
}
}
for @neighbors -> [$yy,$xx] {
++@degree[$yy][$xx]; # undo degree conjectures
}
@grid[$y][$x] = $old; # undo grid value conjecture
return False;
}
say "$tries tries";
}</lang>
{{out}}
<pre>49
48 47 46 45 44 55 74 77 80
37 38 39 40 43 56 73 78 79
36 35 34 41 42 57 72 71 70
31 32 33 14 13 58 59 68 69
30 17 16 15 12 61 60 67 66
29 18 19 20 11 62 63 64 65
28 25 24 21 10 1 2 3 4
27 26 23 22 9 8 7 6 5
1275 tries
9 10 13 14 19 20 63 64 65
8 11 12 15 18 21 62 61 66
7 6 5 16 17 22 59 60 67
| |||