Elixirでナンプレを解くコードを書いてみた

はじめに

この記事は、fukuoka.ex Elixir／Phoenix Advent Calendar 2020 の 第17日目の記事です。
昨日は@masatam81さんの動的計画法を使う問題をElixirで関数型っぽく解いてみる
でした。

概要

ナンプレを解くコードをElixirで書いてみました。
残念ながらまだ全てを解くことはできませんが、ある程度のところまでは解くことができます。プログラミングElixir書籍の前半分くらい知識だけですが、Elixirらしくifを使わずに書きました。
Elixir: ver.1.10.3

実行例

Sudoku.main/1関数で実行します。
入力は列ごとの文字列のリストとしています。
今はコードの中に埋め込んでいます。
解けるところまで行ったら結果を表示して、完全に解けたかを表示します。

iex> c "lib/sudoku.ex"
iex> Sudoku.main(Sudoku.data1)
207 480 900
304 002 071
000 100 028
040 870 160
060 320 000
000 019 004
028 060 700
001 000 040
650 700 082

217 486 935
384 952 671
596 137 428
942 875 163
165 324 897
873 619 254
428 563 719
731 298 546
659 741 382

succeeded in solving.
:ok
iex>

上が元パズル、下が解いた結果です。
0は空白箇所を示しています。

コードの説明

パズル上のマスの空白部にどの数字が選択肢になりえるかを計算して、パズル上の空白部の数字を限定して行きます。
主な変数は
- board: パズル上のマスの数字 / list
- option: マスごとの選択肢 / map
- flag: マスの数字を変更したか(パズルがもう解けないか)どうか / int
です。
マスの数字の決定方法は現在2種類の関数があります。
- fix_board1関数 : optionの数が1個のみのマスの数字を決定する。
- fix_board2関数 : 行(row), 列(column), 3x3マス(square)のそれぞれで、全マスのoptionの中で1個しかない数字を決定する。
マスの数字を決定したら、popout_option関数にてrow/column/squareにあるマスの選択肢からその数字を削除します。

Elixirでの疑問

今回書いていて思った疑問です。

ループ

cなどでforを使うようなループはElixirでは名前付き関数の再帰で書くのが普通かと思いましたが、もっと簡単に書けるでしょうか。
Enum.each/2などを使うのか。ネストするようならば、やはり再帰を使うのでしょうか。

名前付き関数を引数として渡す方法

関数を引数で渡す場合、無名関数での定義になると思いますが、名前付き関数で渡せないですかね。
各関数の返り値をタプルにしてるのが悪いのか。

# ソースコード内のloop関数内のコード
apply = fn {a, b, c}, func -> func(a, b, c) end  #と書きたいが、func未定義と怒られる。
# こんな風に書けると思ったが
# {option, board, 0}
#   |> apply.(fix_board1())
#   |> apply.(fix_board2())
#   |> apply.(loop())

apply = fn {a, b, c}, func -> func.(a, b, c) end  #funcを無名関数で定義すればエラーなし。
{option, board, 0}
  |> apply.(&fix_board1/3) # こんな書き方になってしまうけど、まいいっか。
  |> apply.(&fix_board2/3)
  |> apply.(&loop/3)

ソースコード

defmodule Sudoku do
  def data1 do
    ["207 480 900",
     "304 002 071",
     "000 100 028",
     "040 870 160",
     "060 320 000",
     "000 019 004",
     "028 060 700",
     "001 000 040",
     "650 700 082"]
  end
  #
  def main(str) do
    board = str
      |> Enum.into("")
      |> String.replace(" ", "")
      |> String.graphemes()
      |> Enum.map(&String.to_integer()/1)
    option = initialize_option(board)
    display_result(board) |> IO.puts()

    board_final = loop(option, board, 1)
    display_result(board_final) |> IO.puts()
    result = fn
      0 -> "succeeded in solving."
      _ -> "could not solve completely."
    end
    IO.puts (result.(Enum.count(board_final, fn x -> x == 0 end)))
  end
  #
  def loop(     _, board, 0), do: board
  def loop(option, board, 1) do
    apply = fn {a, b, c}, func -> func.(a, b, c) end
    {option, board, 0}
      |> apply.(&fix_board1/3)
      |> apply.(&fix_board2/3)
      |> apply.(      &loop/3)
  end
  #
  def makekey(y, x) do
    str = fn intg -> intg |> Integer.to_string() end
    str.(y) <> str.(x)
  end
  #
  def fix_board1(option, board, flag), do: _fix_board1(option, board, flag, 0)
  defp _fix_board1(option, board, flag, 81), do: {option, board, flag}
  defp _fix_board1(option, board, flag,  n) do
    operate = fn
      1 ->
        key = makekey(div(n, 9), rem(n, 9))
        num = hd(Map.get(option, key))
        board_new = List.replace_at(board, n, num)
        option
          |> Map.put(key, [])
          |> popout_option(board_new, n, num)
          |> _fix_board1(board_new, 1, n+1)
      _ -> _fix_board1(option, board, flag, n+1)
    end
    key = makekey(div(n, 9), rem(n, 9))
    operate.(length(Map.get(option, key)))
  end
  #
  def fix_board2(option, board, flag), do: _fix_board2(option, board, flag, "row", 1, 0)
  defp _fix_board2(option, board, flag, "square",   9, 9), do: {option, board, flag}
  defp _fix_board2(option, board, flag, "square", num, 9), do: _fix_board2(option, board, flag,    "row", num+1, 0)
  defp _fix_board2(option, board, flag, "column", num, 9), do: _fix_board2(option, board, flag, "square",   num, 0)
  defp _fix_board2(option, board, flag,    "row", num, 9), do: _fix_board2(option, board, flag, "column",   num, 0)
  defp _fix_board2(option, board, flag,     type, num, n) do
    getpos = fn
         "row", n, index -> {    n, index}
      "column", n, index -> {index,     n}
      "square", n, index -> {n-rem(n,3)+div(index,3), 3*rem(n,3)+rem(index,3)}
    end
    operate = fn
      sum_option, 1 ->
        index = Enum.find_index(sum_option, fn x -> num in x end)
        {y,x} = getpos.(type, n, index)
        pos = y*9 + x
        key = makekey(y, x)
        board_new = List.replace_at(board, pos, num)
        option
          |> Map.put(key, [])
          |> popout_option(board_new, pos, num)
          |> _fix_board2(board_new, 1, type, num, n+1)
      _, _ -> _fix_board2(option, board, flag, type, num, n+1)
    end
    collect_options = fn
      option,    "row", n -> for j<-0..8,          do: Map.get(option, makekey(n, j))
      option, "column", n -> for j<-0..8,          do: Map.get(option, makekey(j, n))
      option, "square", n -> for j<-0..2, i<-0..2, do: Map.get(option, makekey(n-rem(n,3)+j, 3*rem(n,3)+i))
    end
    sum_option = collect_options.(option, type, n)
    operate.(sum_option, Enum.count(List.flatten(sum_option), fn x -> x == num end))
  end
  #
  defp getkey(board, n) do
    {y, x} = {div(n, 9), rem(n, 9)}
    check = fn
       y,  x, 0 -> makekey(y, x)
      _y, _x, _ -> "no"
    end
    check2 = fn board, y, x -> check.(y, x, Enum.at(board, y*9+x)) end
    keys = (for j <- 0..8, do: check2.(board, j, x)) ++
           (for j <- 0..8, do: check2.(board, y, j)) ++
           (for j <- 0..2, i <- 0..2, do: check2.(board, y-rem(y,3)+j, x-rem(x,3)+i))
    keys
      |> Enum.filter(fn x -> x != "no" end)
      |> Enum.uniq()
  end
  def popout_option(option, board, n, intg) do
    getkey(board, n)
      |> Enum.reduce(option, fn x, acc -> Map.update!(acc, x, fn value -> value -- [intg] end) end)
  end
  #
  def initialize_option(board), do: _initialize_option(%{}, board, 0)
  defp _initialize_option(option,     _, 81), do: option
  defp _initialize_option(option, board,  n) do
    checkboard = fn
      0 -> make_option(board, n)
      _ -> []
    end
    intg = Enum.at(board, n)
    option
      |> Map.put(makekey(div(n,9), rem(n,9)), checkboard.(intg))
      |> _initialize_option(board,  n+1)
  end
  defp make_option(board, n) do
    {y, x} = {div(n, 9), rem(n, 9)}
    skipkeys = 
      ((for j <- 0..8, do: Enum.at(board, j*9 + x)) ++
       (for j <- 0..8, do: Enum.at(board, y*9 + j)) ++
       (for j <- 0..2, i <- 0..2, do: Enum.at(board, (y-rem(y,3)+j)*9 + x-rem(x,3)+i)) )
        |> Enum.filter(fn x -> x != 0 end)
        |> Enum.uniq()
    Enum.to_list(1..9) -- skipkeys
  end
  #
  def display_result(board), do: _display(board, 0, "", 0, 0)
  defp char(board, n), do: Enum.at(board, n) |> Integer.to_string()
  defp _display(    _, 81, acc, _, _), do: acc
  defp _display(board,  n, acc, _, 7), do: _display(board, n+1, acc <> char(board, n) <> "\n", rem(n, 3), rem(n, 9))
  defp _display(board,  n, acc, 1, _), do: _display(board, n+1, acc <> char(board, n) <> " " , rem(n, 3), rem(n, 9))
  defp _display(board,  n, acc, _, _), do: _display(board, n+1, acc <> char(board, n)        , rem(n, 3), rem(n, 9))
end

(*) ソースコード内のパズル例はこちらのサイトの完成図サンプルデータを使わせていただき、そのデータを元に作成いたしました。

終わりに

今回のコード

まだ改良すべきところ、間違っているところ、などいろいろあると思います。アドバイスいただければ幸いです。
まずはgetkey/2をもう少しキレイに書きたいです。
また、今回のコードはまだもう1つ組み込めてないアルゴリズム（選択肢の計算）があるので、そこまでは実施したいです。

私とElixir

今年初めてElixirに出会いました。確かInterface紙の記事がきっかけだったと思います。その後fukuoka.ex, Nerves, エリジョなどのElixir勉強会に参加させていただきました。最初はチンプンカンプンでしたが、半年ほど経ってこんな感じでコードを書けるようになりました。
回帰とパターンマッチングの書き方にスゴさを感じて、「カチリとハマった」ように思います。最初は条件分岐をifでしか考えられず、それをElixirでどう展開するかに時間を使いましたが、Elixirでの書き方が少しわかってきたような気がします。

今後

これからもElixirをもっと学んで活用していきたいです。
まずはNervesにハマってから、Phoenixなどのフレームワークにも手を出していきます。
お読みいただきどうもありがとうございました。

明日は@pojiroさんのElixirのプログラムの実行方法です。