defmodule KnightTour.Functional do
  @board_size 8
  @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