Solve a Hidato puzzle: Difference between revisions
Content added Content deleted
m (→{{header|Tailspin}}: syntax update) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 458: | Line 458: | ||
17 7 6 3 |
17 7 6 3 |
||
5 4</pre> |
5 4</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/> |
|||
The puzzle can be made circular (the end cell must connect to the start cell). In that case, no start cell needs to be given. |
|||
<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 |
|||
hidatoMoves = {(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)}; |
|||
private (int dx, int dy)[] moves; |
|||
public static void Main() |
|||
{ |
|||
Print(new Solver(hidatoMoves).Solve(false, new [,] { |
|||
{ 0, 33, 35, 0, 0, -1, -1, -1 }, |
|||
{ 0, 0, 24, 22, 0, -1, -1, -1 }, |
|||
{ 0, 0, 0, 21, 0, 0, -1, -1 }, |
|||
{ 0, 26, 0, 13, 40, 11, -1, -1 }, |
|||
{ 27, 0, 0, 0, 9, 0, 1, -1 }, |
|||
{ -1, -1, 0, 0, 18, 0, 0, -1 }, |
|||
{ -1, -1, -1, -1, 0, 7, 0, 0 }, |
|||
{ -1, -1, -1, -1, -1, -1, 5, 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> |
|||
32 33 35 36 37 -- -- -- |
|||
31 34 24 22 38 -- -- -- |
|||
30 25 23 21 12 39 -- -- |
|||
29 26 20 13 40 11 -- -- |
|||
27 28 14 19 9 10 1 -- |
|||
-- -- 15 16 18 8 2 -- |
|||
-- -- -- -- 17 7 6 3 |
|||
-- -- -- -- -- -- 5 4 |
|||
</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
Line 634: | Line 780: | ||
02 16 19 22 23 27 37 36 32 |
02 16 19 22 23 27 37 36 32 |
||
01 20 21 24 25 26 35 34 33 |
01 20 21 24 25 26 35 34 33 |
||
</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/> |
|||
The puzzle can be made circular (the end cell must connect to the start cell). In that case, no start cell needs to be given. |
|||
<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 |
|||
hidatoMoves = {(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)}; |
|||
private (int dx, int dy)[] moves; |
|||
public static void Main() |
|||
{ |
|||
Print(new Solver(hidatoMoves).Solve(false, new [,] { |
|||
{ 0, 33, 35, 0, 0, -1, -1, -1 }, |
|||
{ 0, 0, 24, 22, 0, -1, -1, -1 }, |
|||
{ 0, 0, 0, 21, 0, 0, -1, -1 }, |
|||
{ 0, 26, 0, 13, 40, 11, -1, -1 }, |
|||
{ 27, 0, 0, 0, 9, 0, 1, -1 }, |
|||
{ -1, -1, 0, 0, 18, 0, 0, -1 }, |
|||
{ -1, -1, -1, -1, 0, 7, 0, 0 }, |
|||
{ -1, -1, -1, -1, -1, -1, 5, 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> |
|||
32 33 35 36 37 -- -- -- |
|||
31 34 24 22 38 -- -- -- |
|||
30 25 23 21 12 39 -- -- |
|||
29 26 20 13 40 11 -- -- |
|||
27 28 14 19 9 10 1 -- |
|||
-- -- 15 16 18 8 2 -- |
|||
-- -- -- -- 17 7 6 3 |
|||
-- -- -- -- -- -- 5 4 |
|||
</pre> |
</pre> |
||
Line 2,757: | Line 2,757: | ||
17 7 6 3 |
17 7 6 3 |
||
5 4 |
5 4 |
||
=={{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, -1], [-1, 0], [-1, 1], |
|||
[ 0, -1], [ 0, 1], |
|||
[ 1, -1], [ 1, 0], [ 1, 1]; |
|||
solveboard q:to/END/; |
|||
__ 33 35 __ __ .. .. .. |
|||
__ __ 24 22 __ .. .. .. |
|||
__ __ __ 21 __ __ .. .. |
|||
__ 26 __ 13 40 11 .. .. |
|||
27 __ __ __ 9 __ 1 .. |
|||
.. .. __ __ 18 __ __ .. |
|||
.. .. .. .. __ 7 __ __ |
|||
.. .. .. .. .. .. 5 __ |
|||
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> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 3,495: | Line 3,387: | ||
_ _ _ _ 17 7 6 3 |
_ _ _ _ 17 7 6 3 |
||
_ _ _ _ _ _ 5 4</pre> |
_ _ _ _ _ _ 5 4</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 = [-1, -1], [-1, 0], [-1, 1], |
|||
[ 0, -1], [ 0, 1], |
|||
[ 1, -1], [ 1, 0], [ 1, 1]; |
|||
solveboard q:to/END/; |
|||
__ 33 35 __ __ .. .. .. |
|||
__ __ 24 22 __ .. .. .. |
|||
__ __ __ 21 __ __ .. .. |
|||
__ 26 __ 13 40 11 .. .. |
|||
27 __ __ __ 9 __ 1 .. |
|||
.. .. __ __ 18 __ __ .. |
|||
.. .. .. .. __ 7 __ __ |
|||
.. .. .. .. .. .. 5 __ |
|||
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> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |