3

「四角」

入力:

ボードサイズ m × n (m, n ∈ {1,...,32}), トリプルのリスト(i, j, k), ここで i ∈ {1,...,m}, j ∈ {1,...,n}, k ∈ {0,...,(n-2)·(m-2)}) 数字でフィールドを記述します。

出力:

(i, j, d)解決されたなぞなぞを示すトリプルのリスト。トリプルは、座標と(i, j, d)で反対の頂点を持つ正方形を表します。(i, j)(i+d, j+d)

例：

入力：

7. 7. [(3,3,0)、(3,5,0)、(4,4,1)、(5,1,0)、(6,6,3)]。

出力:

[(1,1,2), (1,5,2), (2,2,4), (5,1,2), (4,4,3)]

画像：

例

説明：

x個の正方形（x =数字のあるフィールド）の配置を見つける必要があります。各正方形の回路上で、正確に彼の角の 1 つで、正方形内の数字の数に等しい 1 つの数字のみにする必要があります。角と同じように、正方形の辺は互いに重なり合うことはできません。正方形の線は「塗りつぶしフィールド」であるため、(0,0,1) の正方形は 4 つのフィールドを塗りつぶし、内部には 0 つのフィールドがあります。

Prolog でこのなぞなぞの解決策をコーディングするのに少し助けが必要です。誰かが私を正しい方向に向けることができますか? どの述語、ルールを使用する必要がありますか。

4

1 に答える 1

1

Naimads の命は救う価値があるので (!)、ここでさらに指示的なヘルプを示します。

プログラマーは、プロジェクトをボトムアップ (「下位」レベルの機能から開始し、完全なアプリケーションを構築する) またはトップダウン (入力/出力を提供する機能の高レベル「シェル」から開始) で作業する傾向があります。ただし、後で改良するためにソリューション処理がスタブされています)。

いずれにせよ、Ruby プログラミング コミュニティによって擁護されてきた Prolog プログラミングのアプローチをお勧めします: Test Driven Developmentです。

高い機能要件と低い機能要件を 2 つ挙げて、この考え方がどのように役立つかについて説明します。

Prolog の高レベルの述語は、すべての入力引数と出力引数を取り、意味的に問題を定義する述語です。解決プロセスがどのように実装されるかを気にせずに、そのような述語を書き留めることができることに注意してください。

/* squaresRiddle/4 takes inputs of Height and Width of a "board" with
   a list of (nonnegative) integers located at cells of the board, and
   produces a corresponding list of squares having one corner at each
   of those locations "boxing in" exactly the specified counts of them
   in their interiors.  No edges can overlap nor corners coincide.  */
squaresRiddle(Height,Width,BoxedCountList, OutputSquaresList).

これまでのところ、問題を組み立てただけです。有用な進行状況はコメントによって示され (大まかな入力と出力を明確に定義します)、この時点のコードは、渡された引数が何であれ「成功」を保証するだけです。したがって、このコードの「テスト」:

?= squaresRiddle(7,7,ListIn,ListOut).

自由変数以外は何も生成しません。

次に、入力リストと出力リストがどのように表現されるべきかについて考えてみましょう。質問では、これらのリストのエントリとして整数のトリプルを使用することが提案されています。代わりに名前付きファンクターを使用することをお勧めします。これらの入力トリプルのセマンティクス (セルの x、y 座標をカウントと共に与える) は、出力トリプル (左上隅の x、y 座標を与える) のセマンティクスとは微妙に異なるためです。および正方形の「範囲」(高さと幅))。特に、出力正方形は、対応する入力項目の角とは異なる角で記述される場合があることに注意してください。ただし、入力項目の角は、出力正方形の 4 つの角の 1 つでなければなりません。

BoxedCountList = [box(3,3,0),box(3,5,0),box(4,4,1),box(5,1,0),box(6,6,3)]したがって、これらのコンストラクトが単純なファンクター名 ( vs.など) で区別されている場合、コードが読みやすくなる傾向がありますOutputSquaresList = [sqr(1,1,2), sqr(1,5,2), sqr(2,2,4), sqr(5,1,2), sqr(4,4,3)]。

解決策の探索がどのように進行するかを少し考えてみましょう。出力項目は入力項目と 1 対 1 で対応しているため、リストは最終的に同じ長さになります。ただし、k 番目の出力アイテムの選択は、k 番目の入力アイテムだけでなく、すべての入力アイテム (出力正方形の内部にいくつあるかをカウントするため) と、前の出力アイテム (交わるコーナーとコーナーを許可しないため) に依存します。重なり合うエッジ)。

この要件に一致する意思決定の流れを管理する方法はいくつかありますが、この演習の核心は、1 つのアプローチを選択して機能させることです。差分リストまたはアキュムレータに精通している場合は、それを行う方法について有利なスタートを切ることができます。

ここで、いくつかの下位レベルの機能の説明に切り替えましょう。入力が与えられると、それに対応するbox可能性のある多数の出力が存在する可能性がありますsqr。出力に正の「範囲」が指定されている場合X,Y、入力の座標は、出力正方形の 4 つの隅のいずれかと一致する可能性があります。ソリューションを検証するにはさらにチェックが必要ですが、この側面はテストを開始するのに適しているようです。

/* check that coordinates X,Y are indeed a corner of candidate square */
hasCorner(sqr(SX,SY,Extent),X,Y) :-
    (SX is X ; SX is X + Extent),
    (SY is Y ; SY is Y + Extent).

このテストをどのように利用しますか？考えられるすべての正方形を生成し (「ボード」の高さと幅に収まる正方形に限定することもできます)、必要な角があるかどうかを確認します。これはかなり非効率的かもしれません。より良い方法 (効率が上がる限り) はExtent、ボード サイズのパラメーターに従って、角を使用して (角から 4 つの方向のいずれかに拡張することによって) 可能な正方形を生成します。この「最適化」の実装は、読者の課題として残されています。

于 2013-04-26T00:16:04.383 に答える