Prologには複雑な問題を解決するための多くの資料があります（例えば、
B-Prologに関するHakan Kjellerstrandページ ）。 ただし、多くの場合、ソリューション用に手動で作成された（小さな検索スペースを持つ）タスク、または最初は論理プログラミングを使用してソリューションに向けられたタスクが与えられます。
Facebook Hacker Cup 2014の第1ラウンドのPrologue AAAAAAに対するソリューションを示したいと思います。タスクはかなり大きな検索スペースを持ち、一般的なプログラミング言語の経験豊富なスポーツプログラマーによる解決を目的として作成されました。
タスクの本質：
テストごとに、
N ×
Mグリッド（
Nおよび
M最大500）が入力に供給されます。 各グリッドセルには次のいずれかが含まれます
. '-オープンセル、または'
# '-クローズドセル（「車でブロック」）。 目標は、パスの各セル（最初のセルを除く）が前のセルの右または下になるように、左上隅から開いているセルに沿って最大長のパス（「人の並び」）を構築することです。
1つの例外が許可されています-パスの連続したセクションを左または上に移動できます。 各オープンセルは1回しか使用できません。
各テストのプログラムの出力は、最長パスの長さです。 1つのファイルに最大20個のテストを含めることができます。
入力および出力データの例：
5 5 5 ..... ..... ..... ..... ..... 1 10 .......... 5 5 ...#. ...#. ...#. ...#. ..... 3 3 ..# #.# ... 3 8 ........ #.#.#.#. #.#.#.#.
Case #1: 17 Case #2: 10 Case #3: 17 Case #4: 5 Case #5: 10
最初の例では、閉じたセルはありません。 最大長の1つの可能な方法：
↓→↓. ↓↑↓.. ↓↑↓.. ↓↑↓.. →↑→→⊕
最後の例の最長の方法：
→→→→→→→↓ #.#.#.#↓ #.#.#.#⊕
私のソリューションでは、
メモ化の形式である
B-Prolog固有の「モード指示タブリング」を使用します。 集計はPrologの標準機能ではないため、プログラムは他のPrologシステムでは動作しません（
XSBと
YAPには同様の機能があります）。
このソリューションでは、トップダウンの
動的プログラミング手法を使用しています。 ソリューションを理解するために、動的プログラミングの特別な知識は必要ありません。プログラムは単にキューを継続するすべての可能な方法を説明し、B-Prologにこのキューの長さの最大値を見つけるよう求めます。
コンテスト中に作成して送信したコードは次のとおりです。
:- table queue(+, +, +, +, +, +, max). queue(_R, _C, _, _, X, Y, 1) :- \+ car(X, Y). % move down queue(R, C, Used, Prev, X, Y, S) :- X < R, Prev \= up, Xp1 is X + 1, \+ car(Xp1, Y), queue(R, C, Used, down, Xp1, Y, Snext), S is 1 + Snext. % move right queue(R, C, Used, Prev, X, Y, S) :- Y < C, Prev \= left, Yp1 is Y + 1, \+ car(X, Yp1), queue(R, C, Used, right, X, Yp1, Snext), S is 1 + Snext. % move up queue(R, C, Used, Prev, X, Y, S) :- X > 1, (Used =:= 0 ; Prev == up), Prev \= down, Xm1 is X - 1, \+ car(Xm1, Y), queue(R, C, 1, up, Xm1, Y, Snext), S is 1 + Snext. % move left queue(R, C, Used, Prev, X, Y, S) :- Y > 1, (Used =:= 0 ; Prev == left), Prev \= right, Ym1 is Y - 1, \+ car(X, Ym1), queue(R, C, 1, left, X, Ym1, Snext), S is 1 + Snext. do_case(Case_num, R, C) :- queue(R, C, 0, right, 1, 1, S), format("Case #~w: ~w\n", [Case_num, S]). main :- read(T), foreach(Case_num in 1..T, [R, C, N], ( initialize_table, abolish, read([R, C]), read(N), assert(car(-1, -1)), % dummy foreach(_I in 1..N, [X, Y], (read([X, Y]), assert(car(X, Y)))), do_case(Case_num, R, C) )).
最初の行は、
queue述語の集計モードを設定し
queue 。最初の6つのパラメーターは入力で、最後は出力です。入力パラメーターに複数の異なる出力値が可能な場合、最大化する必要があります。
queue述語パラメーター：
Rグリッド内の行数
Cはグリッド内の列の数です
Used -左または上への移動が既に使用されている場合は1、それ以外の場合は0
Prev -前のステップの方向
Xは現在のX座標です
Y現在のY座標
Sは（ X 、 Y ）からのパスの長さです。
queue述語の最初のルールは、セル（
X 、
Y ）が車によってブロックされていない場合、このセルで開始する（少なくとも）長さ1のキューが可能であることを示しています。
次に、キューを継続する4つの可能な方法を説明する4つのルールがあります。下、右、上、左です。
下に進むルール：
- 現在の行
Xの数は、グリッドR行数より少ない
- 前のステップがアップしていません（「アップ」）
- セル（
X+1 、 Y ）は車によってブロックされていません
- 結果のキューの長さは、1プラスセルで始まるキューの長さ（
X+1 、 Y ）になります。
右に進むためのルールは、下に進むためのルールに似ています。
上および左に継続するためのルールには、左または上への移動がまだ使用されていないという追加条件が含まれます。または、左/上に順番に移動し続けます。
(Used =:= 0 ; Prev == up) 。
do_caseは
queueを使用して、左上隅から始まるキューの最大長を見つけます。 集計のおかげで、サブタスクの結果は一度だけ計算されます。
mainはテストの数を読み取り、各テストで
R 、
C 、および車両位置をPrologにとって便利な形式で読み取ります。 車ごとに、ファクトがPrologファクトベースに追加され、
queue述語ルールで使用されます。
B-Prologでタスクの入力データをすぐに操作することは可能ですが、私は決めました
Pythonスクリプトを使用して前処理するのがはるかに簡単になります
（車ごとに2要素の座標リストが表示され、各行はドットで終わります）：
T = int(raw_input()) print "%d." % T for case_num in range(1, T + 1): R, C = map(int, raw_input().split()) print "[%d, %d]." % (R, C) cars = [] for i in range(R): row = raw_input().strip() for j in range(C): if row[j] == '#': cars.append([i + 1, j + 1]) print "%d." % len(cars) for car in cars: print "[%d, %d]." % (car[0], car[1])
実行するコマンド（
tailは結果からB-Prologバージョンメッセージを削除します）：
cat in-file | python preprocess.py | bp -g "cl('AAAAAA.pl'),main,halt" -l | tail -n +7 > out-file
特定のソリューションと比較するために、B-Prologは、他の参加者（主にJavaまたはC ++）
のソリューションの
結果テーブルページからダウンロードできます。 それらのほとんど（すべてではないにしても）は、何らかの形式の動的プログラミングを使用します。