🔢

Google Colaboratoryで動かすProlog

に公開
Prolog
Google Colaboratory
論理プログラミング
数独
tech

Prolog、いいですよね。何も分からないところが。
「論理プログラミング」とかいうパラダイムであることだけは知っているけど、それが具体的に何かは一切分からない人が大半なのではないかと思います。

しかし、最近はHaskellの父として有名なSimon Peyton Jones氏が開発しているVerseやCurryのように論理型の混じったマルチパラダイムな言語がじわじわ増えている流れもあり、論理プログラミングを学ぶ機運が高まっています。

ということで、論理プログラミングを学ぶためにPrologに入門してみました。

今回はPrologで数独のルールを記述します。
それによって何が実現できるのかを見ていくことで、Prologの強力さが体感することが目標です。

PRISMを使えばGoogle Colaboratory上でPrologが動かせるので、WebブラウザさえあればPrologに入門できます！
コードはここから実行できます
https://colab.research.google.com/drive/1ZgSb0CVqOKlOKWlVGN4xoQHZPV7TYoEK?usp=sharing

PRISMとは

PRISM はBProlog(Prologの処理系の一つ)に確率を扱えるように拡張したものです。

PRISMを使ってデータ分析やAIの構築することが可能なわけですが、Prologで制約を入れることによって解釈性・説明性を担保されたモデルを簡単に作れるという点が既存のscikit-learnやpytorchとの違いです。

詳しくは以下のPrologやPRISMのチュートリアルを参照ください。

Prologチュートリアル: https://colab.research.google.com/drive/1EhnP2ApqsuchEY-k9ZFUzBZg8Enjyytz?usp=sharing
PRISMチュートリアル: https://colab.research.google.com/drive/182ujzp3Z1jfwDTnd61QnrPDdwoT5CSq7

準備: PythonからPrologを使う

まずはPyPRISMをインストールする必要があります。

# A prebuild PRISM binary can be downloaded from github
! wget "https://github.com/prismplp/prism/releases/download/v2.4.2a(T-PRISM)-prerelease/prism_linux_dev4colab.auto.zip"
! unzip -q -o prism_linux_dev4colab.auto.zip

# Installation of PyPRISM
! pip install -I "git+https://github.com/prismplp/pyprism.git"

インストールが済んだらpyprismパッケージをインポートします。

from pyprism import PrismEngine
import pyprism

engine=PrismEngine(bin_path="prism/bin")

これで準備は完了です。
試しにHello Worldしてみて、ちゃんと表示されればOKです。

engine.query('format("hello world\n").')

まずは数独のルールを日本語でおさらい

数独をPrologで定義する前に、日本語で数独のルールをおさらいしてみます。

  • 9*9 のマスがある
  • 全てのマスに 1 から 9 までの数字が入る
  • それぞれの行・列に数字の重複があってはならない
  • 全体を9個に分割してできる 3*3 の区画の中でも数字の重複があってはならない

ざっとこんな感じでしょうか。
空白の混じった 9*9 のマスを与えられて、このルールを手掛かりに数字を特定していくゲームですね。

数独のルールをPrologで記述する

Prologの使い方は他のプログラミング言語とは違っており、Prologのソースコードがそのまま実行されるわけではありません。
Prologのソースコードは知識を表現したものであり、処理系にそれを読み込ませた上でクエリー(問い合わせ)を投げ、答えてもらうというのがPrologの使い方です。

Prologの詳細な書き方についてはPrologチュートリアルに譲ることにして、とりあえず先ほど整理した数独のルールをPrologで記述します。

sudoku(Rows) :-
  % 9*9 のマスがある
  length(Rows, 9), % 行が9個ある
  foreach(Row in Rows, length(Row, 9)), % それぞれの行には9個のマスがある

  % 全てのマスに 1 から 9 までの数字が入る
  foreach(Row in Rows, N in Row, N in 1..9),

  % それぞれの行に重複がない
  foreach(Row in Rows, all_distinct(Row)),
  % それぞれの列に重複がない
  transpose(Rows, Columns), foreach(Col in Columns, all_distinct(Col)),

  % 全体を9個に分割してできる 3*3 の区画の中に重複がない
  Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
  blocks(As, Bs, Cs),
  blocks(Ds, Es, Fs),
  blocks(Gs, Hs, Is).

% 与えられた3つの行の最初の3個を取り出して調べる
blocks([N1,N2,N3 | Ns1], [N4,N5,N6 | Ns2], [N7,N8,N9 | Ns3]) :-
  % N1 から N9 が1つのブロックなので、このブロックの中で重複がない
  all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
  % N1 から N9 に問題なければ、残りを調べる
  blocks(Ns1, Ns2, Ns3).
% 3個ずつ取り出して重複がなければ、最終的に Ns1 Ns2 Ns3 が全て空リストになって問題なく終了
blocks([], [], []).

このPrologのコードを文字列としてengine.set_dbに渡してやればOKです。

db="""
sudoku(Rows) :-
  % 9*9 のマスがある
  length(Rows, 9), % 行が9個ある
  foreach(Row in Rows, length(Row, 9)), % それぞれの行には9個のマスがある

  % 全てのマスに 1 から 9 までの数字が入る
  foreach(Row in Rows, N in Row, N in 1..9),

  % それぞれの行に重複がない
  foreach(Row in Rows, all_distinct(Row)),
  % それぞれの列に重複がない
  transpose(Rows, Columns), foreach(Col in Columns, all_distinct(Col)),

  % 全体を9個に分割してできる 3*3 の区画の中に重複がない
  Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
  blocks(As, Bs, Cs),
  blocks(Ds, Es, Fs),
  blocks(Gs, Hs, Is).

% 与えられた3つの行の最初の3個を取り出して調べる
blocks([N1,N2,N3 | Ns1], [N4,N5,N6 | Ns2], [N7,N8,N9 | Ns3]) :-
  % N1 から N9 が1つのブロックなので、このブロックの中で重複がない
  all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
  % N1 から N9 に問題なければ、残りを調べる
  blocks(Ns1, Ns2, Ns3).
% 3個ずつ取り出して重複がなければ、最終的に Ns1 Ns2 Ns3 が全て空リストになって問題なく終了
blocks([], [], []).
"""

engine.set_db(db)

これで数独のルールをPrologに教えることができたので、適当な数字列を入力してそれが数独のルールに違反していないかどうかを調べることができます。

engine.query("""
Rows = [
  [7,6,5,8,4,3,1,2,9],
  [8,1,4,9,2,5,7,3,6],
  [9,2,3,6,7,1,4,8,5],
  [2,5,6,4,9,8,3,1,7],
  [1,4,9,3,5,7,2,6,8],
  [3,8,7,2,1,6,9,5,4],
  [4,3,1,5,6,9,8,7,2],
  [5,7,2,1,8,4,6,9,3],
  [6,9,8,7,3,2,5,4,1]
],
sudoku(Rows)
""")
実行結果

([], 'yes')

実行してみるとyesという答えが返されるので、これは数独のルールに違反していないということですね！

入力をいじって重複させたり要素数を9個から変えたりするとnoが返ってくることも確認できます。

数独ソルバー

今Prologに教えたのは数独のルールであって数独の解き方ではありませんが、実はこれだけで数独ソルバーも出来上がっています。

試しに入力を穴あき状態にして、実行時にout=['Rows']という引数を指定してみます。

engine.query("""
Rows = [
  [_,6,5,_,_,_,_,2,9],
  [8,_,_,_,2,_,7,_,_],
  [_,_,_,_,7,_,_,_,_],
  [_,_,_,_,_,_,_,_,_],
  [_,4,_,3,_,7,_,6,_],
  [_,_,_,2,1,_,_,_,_],
  [4,3,_,5,_,_,8,_,2],
  [5,_,_,_,_,4,_,_,_],
  [_,9,_,_,_,_,5,_,1]
],
sudoku(Rows)
""", out=['Rows'])
実行結果

(['Rows=[[7,6,5,8,4,3,1,2,9],[8,1,4,9,2,5,7,3,6],[9,2,3,6,7,1,4,8,5],[2,5,6,4,9,8,3,1,7],[1,4,9,3,5,7,2,6,8],[3,8,7,2,1,6,9,5,4],[4,3,1,5,6,9,8,7,2],[5,7,2,1,8,4,6,9,3],[6,9,8,7,3,2,5,4,1]]'],
'yes')

するとyesという答えの他に、穴が埋まった状態のRowsが結果に含まれています。
Prolog…恐ろしい子…！

解の列挙

先ほどのクエリーでは数独としての解が1つに定まるものを入力していましたが、そこから更に穴を増やして解が1つに定まらないようにすると、今度は可能な解を列挙することもできます。

engine.query("""
Rows = [
  [_,6,5,_,_,_,_,2,9],
  [8,_,_,_,2,_,7,_,_],
  [_,_,_,_,7,_,_,_,_],
  [_,_,_,_,_,_,_,_,_],
  [_,4,_,3,_,7,_,6,_],
  [_,_,_,2,1,_,_,_,_],
  [4,3,_,5,_,_,8,_,2],
  [5,_,_,_,_,4,_,_,_],
  [_,9,_,_,_,_,5,_,_]
],
sudoku(Rows), foreach(Row in Rows, labeling(Row))
""", out=['Rows'], find_n=10)
実行結果

(['Rows=[[7,6,5,1,4,8,3,2,9],[8,1,3,9,2,5,7,4,6],[9,2,4,6,7,3,1,5,8],[1,5,6,4,8,9,2,3,7],[2,4,8,3,5,7,9,6,1],[3,7,9,2,1,6,4,8,5],[4,3,7,5,6,1,8,9,2],[5,8,2,7,9,4,6,1,3],[6,9,1,8,3,2,5,7,4]]',
'Rows=[[7,6,5,1,4,8,3,2,9],[8,1,3,9,2,5,7,4,6],[9,2,4,6,7,3,1,5,8],[1,5,9,4,8,6,2,3,7],[2,4,8,3,5,7,9,6,1],[3,7,6,2,1,9,4,8,5],[4,3,7,5,6,1,8,9,2],[5,8,2,7,9,4,6,1,3],[6,9,1,8,3,2,5,7,4]]',
'Rows=[[7,6,5,1,4,8,3,2,9],[8,1,3,9,2,5,7,4,6],[9,2,4,6,7,3,1,5,8],[1,7,6,4,8,9,2,3,5],[2,4,8,3,5,7,9,6,1],[3,5,9,2,1,6,4,8,7],[4,3,7,5,6,1,8,9,2],[5,8,2,7,9,4,6,1,3],[6,9,1,8,3,2,5,7,4]]',
'Rows=[[7,6,5,1,4,8,3,2,9],[8,1,3,9,2,5,7,4,6],[9,2,4,6,7,3,1,5,8],[1,7,9,4,8,6,2,3,5],[2,4,8,3,5,7,9,6,1],[3,5,6,2,1,9,4,8,7],[4,3,7,5,6,1,8,9,2],[5,8,2,7,9,4,6,1,3],[6,9,1,8,3,2,5,7,4]]',
'Rows=[[7,6,5,1,4,8,3,2,9],[8,1,3,9,2,5,7,4,6],[9,2,4,6,7,3,1,5,8],[2,7,8,4,5,6,9,1,3],[1,4,9,3,8,7,2,6,5],[3,5,6,2,1,9,4,8,7],[4,3,7,5,6,1,8,9,2],[5,8,2,7,9,4,6,3,1],[6,9,1,8,3,2,5,7,4]]',
'Rows=[[7,6,5,1,4,8,3,2,9],[8,1,3,9,2,5,7,4,6],[9,2,4,6,7,3,1,5,8],[2,7,8,4,5,6,9,3,1],[1,4,9,3,8,7,2,6,5],[3,5,6,2,1,9,4,8,7],[4,3,7,5,6,1,8,9,2],[5,8,2,7,9,4,6,1,3],[6,9,1,8,3,2,5,7,4]]',
'Rows=[[7,6,5,1,4,8,3,2,9],[8,1,3,9,2,5,7,4,6],[9,2,4,6,7,3,1,5,8],[3,7,9,4,5,6,2,8,1],[2,4,1,3,8,7,9,6,5],[6,5,8,2,1,9,4,3,7],[4,3,7,5,6,1,8,9,2],[5,8,2,7,9,4,6,1,3],[1,9,6,8,3,2,5,7,4]]',
'Rows=[[7,6,5,1,4,8,3,2,9],[8,1,3,9,2,5,7,4,6],[9,2,4,6,7,3,1,5,8],[3,8,9,4,5,6,2,1,7],[2,4,1,3,8,7,9,6,5],[6,5,7,2,1,9,4,8,3],[4,3,6,5,9,1,8,7,2],[5,7,2,8,3,4,6,9,1],[1,9,8,7,6,2,5,3,4]]',
'Rows=[[7,6,5,1,4,8,3,2,9],[8,1,3,9,2,5,7,4,6],[9,2,4,6,7,3,1,5,8],[6,5,1,4,8,9,2,3,7],[2,4,8,3,5,7,9,6,1],[3,7,9,2,1,6,4,8,5],[4,3,7,5,6,1,8,9,2],[5,8,2,7,9,4,6,1,3],[1,9,6,8,3,2,5,7,4]]',
'Rows=[[7,6,5,1,4,8,3,2,9],[8,1,3,9,2,5,7,4,6],[9,2,4,6,7,3,1,5,8],[6,7,1,4,8,9,2,3,5],[2,4,8,3,5,7,9,6,1],[3,5,9,2,1,6,4,8,7],[4,3,7,5,6,1,8,9,2],[5,8,2,7,9,4,6,1,3],[1,9,6,8,3,2,5,7,4]]'],
'yes')

find_n=10の代わりにfindall=Trueを指定すると全列挙されます。
この例だと全列挙も可能ですが、穴が多すぎると止まらなくなるので注意してください。

Pythonでいい感じに包む

今までPythonはPrologを呼び出すためだけに使っていましたが、せっかくGoogle Colabの中にいるのでipywidgetを使ってちょっとリッチな数独ソルバーのUIを作ってみます。

まずPrologの返した結果をPythonで扱いやすいように加工します。

import json

def solve(problem):
  query = f"Rows = {problem}, sudoku(Rows)"
  result = engine.query(query, out=["Rows"])
  if result[1] != 'yes':
    return ('err', 'wrong_input')
  answer = result[0][0].split('=')[1]
  if '_' in answer:
    return ('err', 'no_unique_solution')
  return ('ok', json.loads(answer))

solve("""
[
  [_,6,5,_,_,_,_,2,9],
  [8,_,_,_,2,_,7,_,_],
  [_,_,_,_,7,_,_,_,_],
  [_,_,_,_,_,_,_,_,_],
  [_,4,_,3,_,7,_,6,_],
  [_,_,_,2,1,_,_,_,_],
  [4,3,_,5,_,_,8,_,2],
  [5,_,_,_,_,4,_,_,_],
  [_,9,_,_,_,_,5,_,1]
]
""")
実行結果

('ok',
[[7, 6, 5, 8, 4, 3, 1, 2, 9],
[8, 1, 4, 9, 2, 5, 7, 3, 6],
[9, 2, 3, 6, 7, 1, 4, 8, 5],
[2, 5, 6, 4, 9, 8, 3, 1, 7],
[1, 4, 9, 3, 5, 7, 2, 6, 8],
[3, 8, 7, 2, 1, 6, 9, 5, 4],
[4, 3, 1, 5, 6, 9, 8, 7, 2],
[5, 7, 2, 1, 8, 4, 6, 9, 3],
[6, 9, 8, 7, 3, 2, 5, 4, 1]])

これで解が文字列ではなく二次元配列として得られるし、もし解が得られなかった場合も 入力が間違っている / 解が1つに定まらない のどちらが原因かが簡単に分かるようになります。

ipywidgetを使って数独のUIを作るコードは長くなるので省略しますが、これでまあまあいい感じのUIができました。
UIはsudoku_gridという関数から呼び出せるようにしました。

_ = 0
sudoku_grid([
  [_,_,_,_,_,_,_,_,_],
  [_,_,_,_,_,3,_,8,5],
  [_,_,1,_,2,_,_,_,_],
  [_,_,_,5,_,7,_,_,_],
  [_,_,4,_,_,_,1,_,_],
  [_,9,_,_,_,_,_,_,_],
  [5,_,_,_,_,_,_,7,3],
  [_,_,2,_,1,_,_,_,_],
  [_,_,_,_,4,_,_,_,9]
])

ついでに解を列挙する方もPythonから扱えるようにしておきます。

def listup(problem, max=10):
  query = f"Rows = {problem}, sudoku(Rows), foreach(Row in Rows, labeling(Row))"
  result = engine.query(query, out=["Rows"], find_n=max) if max != 0 else engine.query(query, out=["Rows"], findall=True)
  if result[1] != 'yes':
    return ('err', 'wrong_input')
  return ('ok', list(map(lambda r: json.loads(r.split('=')[1]), result[0])))

listup("""[
  [_,6,5,_,_,_,_,2,9],
  [8,_,_,_,2,_,7,_,_],
  [_,_,_,_,7,_,_,_,_],
  [_,_,_,_,_,_,_,_,_],
  [_,4,_,3,_,7,_,6,_],
  [_,_,_,2,1,_,_,_,_],
  [4,3,_,5,_,_,8,_,2],
  [5,_,_,_,_,4,_,_,_],
  [_,9,_,_,_,_,5,_,_]
]""", max=2)
実行結果

('ok',
[[[7, 6, 5, 1, 4, 8, 3, 2, 9],
[8, 1, 3, 9, 2, 5, 7, 4, 6],
[9, 2, 4, 6, 7, 3, 1, 5, 8],
[1, 5, 6, 4, 8, 9, 2, 3, 7],
[2, 4, 8, 3, 5, 7, 9, 6, 1],
[3, 7, 9, 2, 1, 6, 4, 8, 5],
[4, 3, 7, 5, 6, 1, 8, 9, 2],
[5, 8, 2, 7, 9, 4, 6, 1, 3],
[6, 9, 1, 8, 3, 2, 5, 7, 4]],
[[7, 6, 5, 1, 4, 8, 3, 2, 9],
[8, 1, 3, 9, 2, 5, 7, 4, 6],
[9, 2, 4, 6, 7, 3, 1, 5, 8],
[1, 5, 9, 4, 8, 6, 2, 3, 7],
[2, 4, 8, 3, 5, 7, 9, 6, 1],
[3, 7, 6, 2, 1, 9, 4, 8, 5],
[4, 3, 7, 5, 6, 1, 8, 9, 2],
[5, 8, 2, 7, 9, 4, 6, 1, 3],
[6, 9, 1, 8, 3, 2, 5, 7, 4]]])

おまけ: 作問機能

数独ソルバーはできましたが、数独の作問はPrologでできるのか？と思ってやってみました。
Prologでも乱数を扱えるので、穴がたくさんある状態からランダムな場所を具体化させたり、逆に全て数字が埋まっている状態からランダムな場所を穴に変えていくことができれば実現できそうです。

数独のルールに加えて以下を追加します。

% 数独の解をランダムに作る。Rowsは全て穴が埋まった状態になることに注意
random_problem(Rows) :-
  % Rows が 9*9 で各マスが 1~9 であることを確認
  sudoku(Rows),
  % 穴を埋める場所をランダムに指定
  Row is (random mod 9) + 1, Col is (random mod 9) + 1,
  % 指定された場所を具体化させる。既に具体化されていれば何も起きない
  Rows^[Row, Col] @= X, indomain(X),
  % 解が1つに定まるようになれば終わり。そうでなければもう一度繰り返す
  (one_solution(Rows) -> true; random_problem(Rows)).

% 解が1つに定まる間、穴を増やしていく
make_problem(Rows, Problem) :-
  % 穴を空ける場所をランダムに指定
  Row is random mod 9, Col is random mod 9,
  % 指定された場所に穴を空ける
  make_hole_rows(Rows, NewRows, 0, Row, Col),
  % 後の one_solution で空けた穴が埋められないようにコピーが必要
  copy_term(NewRows, CheckRows),
  % 穴を空けた後も解が1つに定まる場合は更に穴を増やす。解が定まらなくなったら終了
  (one_solution(CheckRows) -> make_problem(NewRows, Problem) ; Problem = Rows).

% リストの指定された位置に穴を空ける(変数化する)
make_hole([], [], _, _).
make_hole([A|R1], [B|R2], SpecifiedPos, SpecifiedPos) :-
  B = _, CP is SpecifiedPos + 1, make_hole(R1, R2, CP, SpecifiedPos).
make_hole([A|R1], [B|R2], CurrentPos, SpecifiedPos) :-
  B = A, CP is CurrentPos + 1, make_hole(R1, R2, CP, SpecifiedPos).

% make_holeの2次元リストへの拡張
make_hole_rows([], [], CurRow, SpeRow, SpeCol).
make_hole_rows([OriginRow | OriginRest], [NewRow | NewRest], SpeRow, SpeRow, SpeCol) :-
  make_hole(OriginRow, NewRow, 0, SpeCol), CP is SpeRow + 1, make_hole_rows(OriginRest, NewRest, CP, SpeRow, SpeCol).
make_hole_rows([OriginRow | OriginRest], [NewRow | NewRest], CurRow, SpeRow, SpeCol) :-
  OriginRow = NewRow, CP is CurRow + 1, make_hole_rows(OriginRest, NewRest, CP, SpeRow, SpeCol).

% 解が1つのみかどうか
one_solution(Rows) :-
  sudoku(Rows), ground(Rows).

それを engine.set_db でセットしたらPython側で結果を見やすく加工するための関数を書きます。

import re
import random

def make_problem(rows):
  result = engine.query(f"Rows = {rows}, make_problem(Rows, Problem)", out=['Problem'])
  return re.sub(r'_(\d|[a-z])+', '_', result[0][0].split('=')[1])

def random_problem(seed=None, rows='_'):
  seed = random.randint(0, 10 ** 30) if seed is None else seed
  result = engine.query(f"Rows = {rows}, _ is random({seed}), random_problem(Rows), make_problem(Rows, Problem)", out=['Problem'])
  if result[1] == 'no':
    return ('err', 'wrong_input')
  return ('ok', seed, re.sub(r'_(\d|[a-z])+', '_', result[0][0].split('=')[1]))

試しに解を入力にして作問してみます。

make_problem("""[
  [7,6,5,1,4,8,3,2,9],
  [8,1,3,9,2,5,7,4,6],
  [9,2,4,6,7,3,1,5,8],
  [1,5,6,4,8,9,2,3,7],
  [2,4,8,3,5,7,9,6,1],
  [3,7,9,2,1,6,4,8,5],
  [4,3,7,5,6,1,8,9,2],
  [5,8,2,7,9,4,6,1,3],
  [6,9,1,8,3,2,5,7,4]
]""")
実行結果

'[[,,,,,8,3,,9],[8,,3,,2,,7,,],[9,,4,,7,,,5,],[1,5,,4,8,9,2,,7],[2,4,,,,7,,,1],[,7,,,,,,,5],[,,,5,6,,,9,],[,,,,9,4,,1,3],[,,1,,,2,5,7,]]'

結果を見る限りもっと穴が増やせそうなので、限界まで穴を空けられているわけではないようです。
どの数字を消しても解が1つに定まらなくなる状態まで穴を増やすこともきっとできると思うので、やり方を見つけた人はぜひ教えてください。

解を指定しない状態から作問することもできるようになりました。

random_problem()
実行結果

('ok',
251461459268566127606911847176,
'[[9,7,,,5,8,,,4],[,4,,,6,,5,7,],[,,,,7,,,2,9],[6,,,5,2,,8,,1],[,5,7,,,1,2,,3],[,,,,3,6,,5,7],[4,9,3,2,,5,,,],[7,,,,,,,3,2],[1,,6,7,8,,_,9,5]]')

seed値を結果に含めることで結果を固定することができるようにもしてあります。

また、自分で自由に数字を埋めて作問できるようにもしています。

# 円周率を埋め込んだ問題を作ってみた例
random_problem(rows="""[
  [3,1,4,_,_,_,_,_,_],
  [_,_,_,1,5,9,2,_,_],
  [_,_,_,6,_,_,_,_,_],
  [5,3,_,_,_,_,_,_,_],
  [_,_,_,5,8,_,9,7,_],
  [9,_,_,3,2,_,_,_,_],
  [_,_,3,8,4,_,6,2,_],
  [6,4,_,_,_,3,_,_,_],
  [_,_,_,_,_,_,3,_,_]
]""")
実行結果

('ok',
7546071795797524802650968225,
'[[3,1,4,2,7,8,5,,],[7,6,8,1,5,9,2,3,4],[2,,5,,3,,1,,],[5,3,1,4,9,7,8,,2],[,,,5,8,1,9,,3],[9,,7,3,2,6,4,1,],[1,,3,,4,5,6,2,],[,_,2,9,1,3,7,5,8],[8,5,9,7,6,2,3,4,1]]')

最後に、ipywidgetと組み合わせて数独で遊べるようにします

def play_sudoku(seed=None):
  result = random_problem(seed)
  seed = result[1]
  problem = json.loads(result[2].replace('_', '0'))
  print(f"seed: {seed}")
  sudoku_grid(problem)

最後のセルを実行すると、(UIはだいぶ簡素ですが)数独ゲームで遊ぶことができます。

穴を空けていく手順がどうしても手続き的になってしまうので綺麗なコードにはなりませんでしたが、ちょっと込み入ったPrologのコード例が作れて良かったです。

まとめ

Prologで書かれたシンプルな数独のルールから、クエリーを変えることで数独ソルバーや解の列挙などが実現できることを確認しました。

おかげでPrologの書き方にある程度慣れることはできましたが、他にも練習に適した題材があれば積極的に遊んでいきたいです。

(この記事は研究室で取り組みました: https://kojima-r.github.io/kojima/ )

Discussion