Sudoku with exact cover

Mix.install(
  [
    :inplace,
    :kino
  ]
)


Logger.configure(level: :notice)

defmodule RenderHTML do
  use Kino.JS

  def new(html) when is_binary(html) do
    Kino.JS.new(__MODULE__, html)
  end

  asset "main.js" do
    """
    export function init(ctx, html) {
      ctx.root.innerHTML = html;
    }
    """
  end

  ## Sudoku rendering
  ## Grid is NxN array
  def render_sudoku(grid) when is_list(hd(grid)) do
    header = """
    
    """

    body = Enum.reduce(grid, "", fn row, acc -> acc <> row_to_string(row) end)

    footer = """
    
    """

    ## Render
    new(header <> body <> footer)
  end

  def render_sudoku(str) when is_binary(str) do
    for <> do
      case cell - 48 do
        n when n in 1..9 -> n
          _n -> 0  
      end
    end
    |> render_sudoku()
  end
  
  def render_sudoku(array1d) when is_list(array1d) do
    dim = floor(:math.sqrt(length(array1d)))    
    Enum.chunk_every(array1d, dim)
    |> render_sudoku()
  end

  defp row_to_string(row) do
    "\n" <> Enum.map_join(row, "\n", fn cell -> sudoku_cell(cell) end) <> "\n"
  end

  defp sudoku_cell(value) do
    """
    
    """
  end
end

Puzzle

alias InPlace.Examples.Sudoku

puzzle =
  #"48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5...."
  #"000500301400020000000000000260001000000300900004000080090700000000080040600000000"
  ## slow :list, fast :heap
  #"000800004010020000092000000300600087000000050000090000000400200700005000000000100"
  #"760040000000000801000500000000100200040000050030000000108600000000090030200000000"
  #"200000700000000010000400000500600200980000000000300000010080040030001000000090500"
  #"030070000000000102000000600000005040600000030100600000050210000007000800004000000"
  #"000307000060000020100500000305000400000080060000000000020006000000400500000010300"
  #"400000601020800000000000000001250000600000900000008030030500080700090000000000000"
  #"400000210000800007000600000680000500000020040730000000001040000000700006000000000",
  #"000060040023000000010000000600000100900400000008500000700000950000003001000020000"
  #"000000608900002000000000300500060070000800000000030000020007500038100000000000040",
  #"041000000000007600000080000060000043800020000000000051200300900000104000000000000"
  #"070840500200000000000000000100300006604000020000000000000016000030000400050900000"
  #"008006100030500000000900000200014000570000030000000000000730050900000400000000000"
  #"670500300052000000000000010083200000400000090000800000100090000000040000000000200"
  #"000000608900002000000000300500060070000800000000030000020007500038100000000000040"
  #"700000030600020000000005100020040500000700040010000000300600008000300000000000200"
  #"090200800000000060000000000250000040000190000400080000000900208600003000000000100"
  #"020400000007000300000060000000200080060700000500000010100050000000003200000000704"  
  #"054001000000070080000000000600020004800000500000000901700000030000105000000900000"
  #"070500000012000000000040800000200460000700000300000000000000071600003000400080000"
  #"700800000000000021000000000060050003010020000000000400206003000000400810500000000"
  #"700000400000600050080000000206000030503000000000010000000502000000300800040000100"
  #"700000800000600050090000000506000030203000000000010000000502000000300900040000100"
  "680000100000250000000000000000081000005000003020070000000000820300600000009400000"
  
RenderHTML.render_sudoku(puzzle)

Solution

{tc, solution} = :timer.tc(fn -> Sudoku.solve(puzzle, 
  checker: true,
  choose_item_fun: fn _, data -> InPlace.ExactCover.min_options_item(data) end,
  solution_handler: fn s -> send(self(), s) end) end)

solution = receive do
  msg -> msg
end

if Sudoku.check_solution(solution) do
  IO.puts("Solution is correct, solved in #{div(tc, 1000)} ms")
else
  IO.puts("Solution is incorrect")  
end

RenderHTML.render_sudoku(solution)

Benchmark

puzzle_file = 
  "data/sudoku/clue17"
  #"data/sudoku/top95"
  #"data/sudoku/misc"
  #"data/sudoku/hardest"
  #"data/sudoku/puzzles5_forum_hardest_1905_11+"
  #"data/sudoku/quasi_uniform_834"
num_instances = 100_000
puzzles = File.read!(Path.join("/Users/bokner/projects/cpsolver", puzzle_file)) 
  |> String.split("\n") |> Enum.map(fn puzzle -> String.slice(puzzle, 0..80) end)
  |> Enum.take(num_instances)

res = Enum.map(Enum.with_index(puzzles, 1), fn {p, idx} -> 
  {tc, _} = 
  :timer.tc(fn -> Sudoku.solve(p, checker: false,
    # choose_item_fun: fn _, data -> 
    #   InPlace.ExactCover.min_options_item(data)
    #end,
    solution_handler: fn _ -> :ok end) end)
  |> tap(fn {tc, _idx} -> IO.puts("#{idx} : #{round(tc/1000)} ms") end)

  {tc, idx}
  end)

times = Enum.map(res, fn {time, _idx} -> time end) |> Enum.sort()
stats = %{shortest: Enum.min(times), 
  longest: Enum.max(times), 
  average: Enum.sum(times) / length(times), 
  total: Enum.sum(times),
  sorted: Enum.sort(times),
  median: Enum.at(times, div(length(times), 2))
}

Slowest instance

{duration, idx} = Enum.max_by(res, fn {time, _idx} -> time end)
longest = Enum.at(puzzles, idx - 1)
{duration, longest}