Solve a Hidato puzzle: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: changed/added comments and whitespace, changed indentations.) |
(Added Elixir) |
||
Line 25: | Line 25: | ||
* [[Solve a Holy Knight's tour]] |
* [[Solve a Holy Knight's tour]] |
||
* [[Solve a Numbrix puzzle]] |
* [[Solve a Numbrix puzzle]] |
||
* [[Solve the no connection puzzle]] |
|||
* [[Knight's tour]] |
* [[Knight's tour]] |
||
<br><br> |
<br><br> |
||
Line 1,063: | Line 1,064: | ||
. . 4 . 7 . 10 . 13 . 16 . 19 . 22 . 25 . 28 . 31 . 34 . 37 . 40 . 43 . 46 . 49 . 52 . 55 . 58 . 61 . 64 . 67 . 70 . 73 . |
. . 4 . 7 . 10 . 13 . 16 . 19 . 22 . 25 . 28 . 31 . 34 . 37 . 40 . 43 . 46 . 49 . 52 . 55 . 58 . 61 . 64 . 67 . 70 . 73 . |
||
. . . 5 6 . . 11 12 . . 17 18 . . 23 24 . . 29 30 . . 35 36 . . 41 42 . . 47 48 . . 53 54 . . 59 60 . . 65 66 . . 71 72 .</pre> |
. . . 5 6 . . 11 12 . . 17 18 . . 23 24 . . 29 30 . . 35 36 . . 41 42 . . 47 48 . . 53 54 . . 59 60 . . 65 66 . . 71 72 .</pre> |
||
=={{header|Elixir}}== |
|||
{{trans|Ruby}} |
|||
<lang elixir># Solve a Hidato Like Puzzle with Warnsdorff like logic applied |
|||
# |
|||
defmodule HLPsolver do |
|||
defmodule Cell do |
|||
defstruct value: -1, used: false, adj: [] |
|||
end |
|||
def solve(str, adjacent, print_out\\true) do |
|||
board = setup(str) |
|||
if print_out, do: print(board, "Problem:") |
|||
{start, _} = Enum.find(board, fn {_,cell} -> cell.value==1 end) |
|||
board = set_adj(board, adjacent) |
|||
zbl = for %Cell{value: n} <- Map.values(board), into: %{}, do: {n, true} |
|||
try do |
|||
solve(board, start, 1, zbl, map_size(board)) |
|||
IO.puts "No solution" |
|||
catch |
|||
{:ok, result} -> if print_out, do: print(result, "Solution:"), |
|||
else: result |
|||
end |
|||
end |
|||
defp solve(board, position, seq_num, zbl, goal) do |
|||
value = board[position].value |
|||
cond do |
|||
value > 0 and value != seq_num -> nil |
|||
value == 0 and zbl[seq_num] -> nil |
|||
true -> |
|||
cell = %Cell{board[position] | value: seq_num, used: true} |
|||
board = %{board | position => cell} |
|||
if seq_num == goal, do: throw({:ok, board}) |
|||
Enum.each(wdof(board, cell.adj), fn pos -> |
|||
solve(board, pos, seq_num+1, zbl, goal) |
|||
end) |
|||
end |
|||
end |
|||
defp setup(str) do |
|||
lines = String.strip(str) |> String.split(~r/(\n|\r\n|\r)/) |> Enum.with_index |
|||
for {line,i} <- lines, {char,j} <- Enum.with_index(String.split(line)), |
|||
:error != Integer.parse(char), into: %{} do |
|||
{n,_} = Integer.parse(char) |
|||
{{i,j}, %Cell{value: n}} |
|||
end |
|||
end |
|||
defp set_adj(board, adjacent) do |
|||
Enum.reduce(Map.keys(board), board, fn {x,y},map -> |
|||
adj = Enum.map(adjacent, fn {i,j} -> {x+i, y+j} end) |
|||
|> Enum.reduce([], fn pos,acc -> if board[pos], do: [pos | acc], else: acc end) |
|||
Map.update!(map, {x,y}, fn cell -> %Cell{cell | adj: adj} end) |
|||
end) |
|||
end |
|||
defp wdof(board, adj) do # Warnsdorf's rule |
|||
Enum.reject(adj, fn pos -> board[pos].used end) |
|||
|> Enum.sort_by(fn pos -> |
|||
Enum.count(board[pos].adj, fn p -> not board[p].used end) |
|||
end) |
|||
end |
|||
def print(board, title) do |
|||
IO.puts "\n#{title}" |
|||
{xmin, xmax} = Map.keys(board) |> Enum.map(fn {x,_} -> x end) |> Enum.min_max |
|||
{ymin, ymax} = Map.keys(board) |> Enum.map(fn {_,y} -> y end) |> Enum.min_max |
|||
len = map_size(board) |> to_char_list |> length |
|||
space = String.duplicate(" ", len) |
|||
Enum.each(xmin..xmax, fn x -> |
|||
Enum.map_join(ymin..ymax, " ", fn y -> |
|||
case Map.get(board, {x,y}) do |
|||
nil -> space |
|||
cell -> to_string(cell.value) |> String.rjust(len) |
|||
end |
|||
end) |
|||
|> IO.puts |
|||
end) |
|||
end |
|||
end</lang> |
|||
'''Test:''' |
|||
<lang elixir>adjacent = [{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}] |
|||
""" |
|||
. 4 |
|||
0 7 0 |
|||
1 0 0 |
|||
""" |
|||
|> HLPsolver.solve(adjacent) |
|||
""" |
|||
0 33 35 0 0 |
|||
0 0 24 22 0 |
|||
0 0 0 21 0 0 |
|||
0 26 0 13 40 11 |
|||
27 0 0 0 9 0 1 |
|||
. . 0 0 18 0 0 |
|||
. . . . 0 7 0 0 |
|||
. . . . . . 5 0 |
|||
""" |
|||
|> HLPsolver.solve(adjacent) |
|||
""" |
|||
1 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 |
|||
. . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 |
|||
. . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 |
|||
""" |
|||
|> HLPsolver.solve(adjacent)</lang> |
|||
{{out}} |
|||
<pre> |
|||
Problem: |
|||
4 |
|||
0 7 0 |
|||
1 0 0 |
|||
Solution: |
|||
4 |
|||
3 7 5 |
|||
1 2 6 |
|||
Problem: |
|||
0 33 35 0 0 |
|||
0 0 24 22 0 |
|||
0 0 0 21 0 0 |
|||
0 26 0 13 40 11 |
|||
27 0 0 0 9 0 1 |
|||
0 0 18 0 0 |
|||
0 7 0 0 |
|||
5 0 |
|||
Solution: |
|||
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 |
|||
Problem: |
|||
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
|||
0 0 0 0 0 0 0 0 0 0 0 0 0 |
|||
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
|||
Solution: |
|||
1 2 3 9 10 11 17 18 19 25 26 27 33 34 35 41 42 43 49 50 51 |
|||
4 8 12 16 20 24 28 32 36 40 44 48 52 |
|||
5 6 7 13 14 15 21 22 23 29 30 31 37 38 39 45 46 47 53 |
|||
</pre> |
|||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
Line 1,196: | Line 1,350: | ||
5 4 |
5 4 |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 2,063: | Line 2,218: | ||
17 7 6 3 |
17 7 6 3 |
||
5 4 |
5 4 |
||
=={{header|Perl 6}}== |
=={{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. Rather than recalculating degree over and over, we maintain an array of known degrees for each node. |
This uses a Warnsdorff solver, which cuts down the number of tries by more than a factor of six over the brute force approach. Rather than recalculating degree over and over, we maintain an array of known degrees for each node. |