Anonymous user
Solve a Hidato puzzle: Difference between revisions
Added Elixir
m (→{{header|REXX}}: changed/added comments and whitespace, changed indentations.) |
(Added Elixir) |
||
Line 25:
* [[Solve a Holy Knight's tour]]
* [[Solve a Numbrix puzzle]]
* [[Solve the no connection puzzle]]
* [[Knight's tour]]
<br><br>
Line 1,063 ⟶ 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 .
. . . 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}}==
Line 1,196 ⟶ 1,350:
5 4
</pre>
=={{header|Haskell}}==
Line 2,063 ⟶ 2,218:
17 7 6 3
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. Rather than recalculating degree over and over, we maintain an array of known degrees for each node.
| |||