Packages
inplace
0.7.12
0.7.12
0.7.11
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.8
0.6.7
0.6.6
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.4
0.4.3
0.4.2
0.4.1
0.4.0
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.2.0
0.1.9
0.1.8
0.1.7
0.1.6
0.1.5
0.1.4
0.1.3
0.1.2
0.1.1
0.1.0
Mutable data structures
Current section
Files
Jump to
Current section
Files
lib/examples/knight_tour_functional.ex
defmodule KnightTour.Functional do
@board_size 7
@all_moves [
{-2, -1}, {-1, -2}, {1, -2}, {2, -1},
{2, 1}, {1, 2}, {-1, 2}, {-2, 1}
]
def solve(start \\ {0, 0}) do
board = MapSet.new()
tour = [start]
case backtrack(tour, board, 1) do
{:ok, path} -> Enum.reverse(path)
:no_solution -> :no_solution
end
end
defp backtrack([{x, y} | _rest] = tour, board, step) when step == @board_size * @board_size do
if MapSet.member?(board, {x, y}) do
{:ok, tour}
else
{:ok, [{x, y} | tour]}
end
end
defp backtrack([{x, y} | _rest] = tour, board, step) do
next_moves = valid_moves({x, y}, board)
Enum.find_value(next_moves, :no_solution, fn next ->
new_board = MapSet.put(board, {x, y})
new_tour = [next | tour]
case backtrack(new_tour, new_board, step + 1) do
{:ok, path} -> {:ok, path}
:no_solution -> nil
end
end)
end
defp valid_moves({x, y}, board) do
for {dx, dy} <- @all_moves do
{x + dx, y + dy}
end
|> Enum.filter(&(in_bounds(&1) and not MapSet.member?(board, &1)))
end
defp in_bounds({x, y}) do
x in 0..(@board_size - 1) and y in 0..(@board_size - 1)
end
end