Solve a Hopido puzzle: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
(Added Prolog) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 135:
12 3 6
27</pre>
=={{header|C sharp}}==
The same solver can solve Hidato, Holy Knight's Tour, Hopido and Numbrix puzzles.<br/>
The input can be an array of strings if each cell is one character. The length of the first row must be the number of columns in the puzzle.<br/>
Any non-numeric value indicates a no-go.<br/>
If there are cells that require more characters, then a 2-dimensional array of ints must be used. Any number < 0 indicates a no-go.<br/>
<lang csharp>using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
using static System.Linq.Enumerable;
public class Solver
{
private static readonly (int dx, int dy)[]
//other puzzle types elided
hopidoMoves = {(-3,0),(0,-3),(0,3),(3,0),(-2,-2),(-2,2),(2,-2),(2,2)},
private (int dx, int dy)[] moves;
public static void Main()
{
Print(new Solver(hopidoMoves).Solve(false,
".00.00.",
"0000000",
"0000000",
".00000.",
"..000..",
"...0..."
));
}
public Solver(params (int dx, int dy)[] moves) => this.moves = moves;
public int[,] Solve(bool circular, params string[] puzzle)
{
var (board, given, count) = Parse(puzzle);
return Solve(board, given, count, circular);
}
public int[,] Solve(bool circular, int[,] puzzle)
{
var (board, given, count) = Parse(puzzle);
return Solve(board, given, count, circular);
}
private int[,] Solve(int[,] board, BitArray given, int count, bool circular)
{
var (height, width) = (board.GetLength(0), board.GetLength(1));
bool solved = false;
for (int x = 0; x < height && !solved; x++) {
solved = Range(0, width).Any(y => Solve(board, given, circular, (height, width), (x, y), count, (x, y), 1));
if (solved) return board;
}
return null;
}
private bool Solve(int[,] board, BitArray given, bool circular,
(int h, int w) size, (int x, int y) start, int last, (int x, int y) current, int n)
{
var (x, y) = current;
if (x < 0 || x >= size.h || y < 0 || y >= size.w) return false;
if (board[x, y] < 0) return false;
if (given[n - 1]) {
if (board[x, y] != n) return false;
} else if (board[x, y] > 0) return false;
board[x, y] = n;
if (n == last) {
if (!circular || AreNeighbors(start, current)) return true;
}
for (int i = 0; i < moves.Length; i++) {
var move = moves[i];
if (Solve(board, given, circular, size, start, last, (x + move.dx, y + move.dy), n + 1)) return true;
}
if (!given[n - 1]) board[x, y] = 0;
return false;
bool AreNeighbors((int x, int y) p1, (int x, int y) p2) => moves.Any(m => (p2.x + m.dx, p2.y + m.dy).Equals(p1));
}
private static (int[,] board, BitArray given, int count) Parse(string[] input)
{
(int height, int width) = (input.Length, input[0].Length);
int[,] board = new int[height, width];
int count = 0;
for (int x = 0; x < height; x++) {
string line = input[x];
for (int y = 0; y < width; y++) {
board[x, y] = y < line.Length && char.IsDigit(line[y]) ? line[y] - '0' : -1;
if (board[x, y] >= 0) count++;
}
}
BitArray given = Scan(board, count, height, width);
return (board, given, count);
}
private static (int[,] board, BitArray given, int count) Parse(int[,] input)
{
(int height, int width) = (input.GetLength(0), input.GetLength(1));
int[,] board = new int[height, width];
int count = 0;
for (int x = 0; x < height; x++)
for (int y = 0; y < width; y++)
if ((board[x, y] = input[x, y]) >= 0) count++;
BitArray given = Scan(board, count, height, width);
return (board, given, count);
}
private static BitArray Scan(int[,] board, int count, int height, int width)
{
var given = new BitArray(count + 1);
for (int x = 0; x < height; x++)
for (int y = 0; y < width; y++)
if (board[x, y] > 0) given[board[x, y] - 1] = true;
return given;
}
private static void Print(int[,] board)
{
if (board == null) {
WriteLine("No solution");
} else {
int w = board.Cast<int>().Where(i => i > 0).Max(i => (int?)Ceiling(Log10(i+1))) ?? 1;
string e = new string('-', w);
foreach (int x in Range(0, board.GetLength(0)))
WriteLine(string.Join(" ", Range(0, board.GetLength(1))
.Select(y => board[x, y] < 0 ? e : board[x, y].ToString().PadLeft(w, ' '))));
}
WriteLine();
}
}</lang>
{{out}}
<pre style="height:30ex;overflow:scroll">
-- 1 8 -- 2 7 --
25 22 19 26 23 20 27
9 16 13 10 17 14 11
-- 4 24 21 3 6 --
-- -- 18 15 12 -- --
-- -- -- 5 -- -- --
</pre>
=={{header|C++}}==
Line 280 ⟶ 421:
06 09 14
24
</pre>
Line 1,165:
.. .. .. 27 .. .. ..
</pre>
=={{header|Phix}}==
Line 1,362 ⟶ 1,246:
solution found in 67702 tries (0.09s)
</pre>
=={{header|Prolog}}==
Line 1,548 ⟶ 1,431:
_ _ 14 23 26 _ _
_ _ _ 17 _ _ _</pre>
=={{header|Raku}}==
(formerly 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 = [3, 0],
[2, -2], [2, 2],
[0, -3], [0, 3],
[-2, -2], [-2, 2],
[-3, 0];
solveboard q:to/END/;
. _ _ . _ _ .
_ _ _ _ _ _ _
_ _ _ _ _ _ _
. _ _ _ _ _ .
. . _ _ _ . .
. . . 1 . . .
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> 21 4 20 3
26 12 15 25 11 14 24
17 6 9 18 5 8 19
22 27 13 23 2
16 7 10
1
59 tries</pre>
=={{header|REXX}}==
| |||