64 lines
1.8 KiB
Text
64 lines
1.8 KiB
Text
defmodule Board do
|
|
import Integer, only: [is_odd: 1]
|
|
|
|
defmodule Cell do
|
|
defstruct [:value, :adj]
|
|
end
|
|
|
|
@adjacent [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]
|
|
|
|
defp initialize(rows, cols) do
|
|
board = for i <- 1..rows, j <- 1..cols, into: %{}, do: {{i,j}, true}
|
|
for i <- 1..rows, j <- 1..cols, into: %{} do
|
|
adj = for [di,dj] <- @adjacent, board[{i+di, j+dj}], do: {i+di, j+dj}
|
|
{{i,j}, %Cell{value: 0, adj: adj}}
|
|
end
|
|
end
|
|
|
|
defp solve(board, ij, num, goal) do
|
|
board = Map.update!(board, ij, fn cell -> %{cell | value: num} end)
|
|
if num == goal do
|
|
throw({:ok, board})
|
|
else
|
|
wdof(board, ij)
|
|
|> Enum.each(fn k -> solve(board, k, num+1, goal) end)
|
|
end
|
|
end
|
|
|
|
defp wdof(board, ij) do # Warnsdorf's rule
|
|
board[ij].adj
|
|
|> Enum.filter(fn k -> board[k].value == 0 end)
|
|
|> Enum.sort_by(fn k ->
|
|
Enum.count(board[k].adj, fn x -> board[x].value == 0 end)
|
|
end)
|
|
end
|
|
|
|
defp to_string(board, rows, cols) do
|
|
width = to_string(rows * cols) |> String.length
|
|
format = String.duplicate("~#{width}w ", cols)
|
|
Enum.map_join(1..rows, "\n", fn i ->
|
|
:io_lib.fwrite format, (for j <- 1..cols, do: board[{i,j}].value)
|
|
end)
|
|
end
|
|
|
|
def knight_tour(rows, cols, sx, sy) do
|
|
IO.puts "\nBoard (#{rows} x #{cols}), Start: [#{sx}, #{sy}]"
|
|
if is_odd(rows*cols) and is_odd(sx+sy) do
|
|
IO.puts "No solution"
|
|
else
|
|
try do
|
|
initialize(rows, cols)
|
|
|> solve({sx,sy}, 1, rows*cols)
|
|
IO.puts "No solution"
|
|
catch
|
|
{:ok, board} -> IO.puts to_string(board, rows, cols)
|
|
end
|
|
end
|
|
end
|
|
end
|
|
|
|
Board.knight_tour(8,8,4,2)
|
|
Board.knight_tour(5,5,3,3)
|
|
Board.knight_tour(4,9,1,1)
|
|
Board.knight_tour(5,5,1,2)
|
|
Board.knight_tour(12,12,2,2)
|