2015年5月15日金曜日

R-99 その他 - Prolog-99 Ruby版 日本語訳

R-99: 99 の Ruby の問題 - 7. その他

  • 訳注1:問題番号の後のアスタリスクはPrologで解くときの難易度の目安。

その他の問題

7.01 (**) エイトクイーン問題

これは、コンピュータサイエンスの古典的な問題である。目的は、全てのクイーンが互いを攻撃されないように、 チェス盤に 8 個のクイーンを配置することである。すなわち、どのクイーンも、同じ行、同じ列、または 同じ対角線上にない状態である。

ヒント: 番号 1 から N の配列としてクイーンの位置を表す。例:[4,2,7,3,6,8,5,1] 最初の列のクイーンは4行目にあることを、次の列には2行目、というように解釈する。 生成-試験パラダイム(generate-and-test paradigm)を利用せよ。

訳注: 「生成-試験パラダイム」とは、結果を自動的に可視化する戦略である。ここでは、 クイーンの配置列を求めた時、その結果を画面に描画し、正しいかどうかをチェックすることができるように することを指す。

7.02 (**) ナイトツアー

もう一つの有名は問題は、どのようにすれば N×N マスのチェス盤の全てのマスに1度ずつナイトを 移動させることができるか? というものである。

ヒント: 正方形の座標を X/Y と表す時、X,Y の両方は 1〜N の間の整数である。('/'は単に便利な 演算子ではなく、区切りであることに注意せよ!) ナイトは、N×N個のチェス盤上に X/Y から U/V へジャンプすることができるという事実を表現するために 関数jump(x,y,u,v)を定義する。 最後に、N×Nのナイトの位置を配列として問題の解とする。(ナイトの旅:knight's tour)

7.03 (***) フォン-コッホの予想から

数年前、解決策を知らないためにある問題に興味をそそられた数学者がいた。名前はファン-コッホ。 この問題は解決されているかどうかわからない。

とにかく、パズルは以下のようになっている。N 個のノードを持つ ツリーを考える(従って N-1 個のエッジがある)。 1からNのノードに応じて1からN-1の各エッジを列挙するための方法を見つけよ。各エッジ K の ノード番号は K と等しいする。 予想では、これは常に可能であるという。

小さなツリーであれば、この問題を手で解くことは簡単である。しかし、大きなツリーや14は 非常に大きく、解を導くことは非常に困難である。しかも、常に解があるかどうかは分からないことを 忘れないように。

与えられたツリーの採番方法を計算する関数を書け。上記のツリーの解は何か?

7.04 (***) 算術パズル

整数のリストを与えると、正しい方程式の結果のような演算記号(演算子)を挿入する方法を発見せよ。 例) 数の配列 [2,3,5,7,11] は方程式で 2 - 3 + 5 + 7 = 11 または 2 = (3 * 5 + 7) / 11 と書ける(他にも10以上書き方がある)。

7.05 (**)

財務書類上、小切手のように、数字は時々単語の組み合わせとして書く必要がある。 例) 175 は、"one-seven-five"と書く必要がある。 単語の組み合わせで(負ではない)整数を表示する関数full_words(a)を書け。

7.06 (**) 構文チェッカー

特定のプログラミング言語(Ada)で識別子は、構文図(鉄道チャート)の反対として定義される。 ループの含まれない構文図のシステムに構文図を変換せよ。すなわち、これは純粋に再帰である。 これらの変更された図を用いて、与えられた文字列が有効な識別子であるか否かを確認することができる 関数identifierを書け。

identifier => str   # str は正しい識別子

7.07 (**) 数独

数独パズルは次のように解く:

    問題文                 解答

    .  .  4 | 8  .  . | .  1  7      9  3  4 | 8  2  5 | 6  1  7         
            |         |                      |         |
    6  7  . | 9  .  . | .  .  .      6  7  2 | 9  1  4 | 8  5  3
            |         |                      |         |
    5  .  8 | .  3  . | .  .  4      5  1  8 | 6  3  7 | 9  2  4
    --------+---------+--------      --------+---------+--------
    3  .  . | 7  4  . | 1  .  .      3  2  5 | 7  4  8 | 1  6  9
            |         |                      |         |
    .  6  9 | .  .  . | 7  8  .      4  6  9 | 1  5  3 | 7  8  2
            |         |                      |         |
    .  .  1 | .  6  9 | .  .  5      7  8  1 | 2  6  9 | 4  3  5
    --------+---------+--------      --------+---------+--------
    1  .  . | .  8  . | 3  .  6      1  9  7 | 5  8  2 | 3  4  6
            |         |                      |         |
    .  .  . | .  .  6 | .  9  1      8  5  3 | 4  7  6 | 2  9  1
            |         |                      |         |
    2  4  . | .  .  1 | 5  .  .      2  4  6 | 3  9  1 | 5  7  8

パズル内のすべて場所は(水平)行と(垂直)列に属し、1つの3x3の正方形(略してプレースと呼ぶ)も 同様である。はじめに、場所のいくつかには、1から9の1桁の数字が知らされる。 問は、1から9までのすべての数を、各行、各列、各プレースに一度だけ現れるように数字の 入っていない場所に埋めることである。

7.08 (***) ノノグラム

訳注: 「ノノグラム」とは、日本では「イラストロジック(お絵描きロジック)」などと呼ばれている。

1994年頃、あるパズルがイギリスで非常に人気があった。「ノノグラムは、日本から来たパズルであり、 現在はサンデーテレグラフで毎週公開されています。単純にマスを埋め、絵や図を明らかにするために 論理と技術を使います。」と「サンデーテレグラフ」 紙に掲載された。Ruby プログラマとして、 よい場面である。使っているコンピュータに仕事をさせることができる!

パズルは以下の通り。本質的に、長方形の方眼の各行と列に、占有する一続きのマスの数が列挙されている。 パズルを解くにはこれらの長さが指定されたマスを埋める必要がある。

    問題                         解答

    |_|_|_|_|_|_|_|_| 3         |_|X|X|X|_|_|_|_| 3           
    |_|_|_|_|_|_|_|_| 2 1       |X|X|_|X|_|_|_|_| 2 1         
    |_|_|_|_|_|_|_|_| 3 2       |_|X|X|X|_|_|X|X| 3 2         
    |_|_|_|_|_|_|_|_| 2 2       |_|_|X|X|_|_|X|X| 2 2         
    |_|_|_|_|_|_|_|_| 6         |_|_|X|X|X|X|X|X| 6           
    |_|_|_|_|_|_|_|_| 1 5       |X|_|X|X|X|X|X|_| 1 5         
    |_|_|_|_|_|_|_|_| 6         |X|X|X|X|X|X|_|_| 6           
    |_|_|_|_|_|_|_|_| 1         |_|_|_|_|X|_|_|_| 1           
    |_|_|_|_|_|_|_|_| 2         |_|_|_|X|X|_|_|_| 2           
     1 3 1 7 5 3 4 3             1 3 1 7 5 3 4 3              
     2 1 5 1                     2 1 5 1        

上記の例の場合、問題は2つの配列 [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]] と [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]] として行と列、上から下と左から右のそれぞれの 塊の長さとして与えることができる。 公開されたパズルは、この例よりも大きい。例えば25x20で、毎回異なる解を持つ。

7.09 (***) クロスワードパズル

クロスワートパズルの空(またはほとんど空)の枠と単語集が与えらえる。問は、枠に単語を 配置することである。

特定のクロスワードパズルは、最初に任意の順番で単語(1行に一つの単語)をリストにした テキストファイルに指定されている。そして、空行の後、クロスワードの枠組みが定義されている。 この枠の仕様では、空の文字位置をドット(.)で表現する。 解を簡単にするために、文字位置にはあらかじめ定義された文字の値を含むことができる。

単語は少なくとも2文字の文字列である。クロスワードパズルの枠組みの中で文字の入る場所の縦、 横の並びをサイトと呼ぶ。問は、サイト上の単語を矛盾なく配置する方法を見つけることである。

訳注: データファイルの内容例

PERL
PROLOG
ONLINE
GNU
LINUX
WEB
NFS
XML
SQL
MAC
EMACS

......  .
. .  .  .
. ..... .
. . . ...
  . ... .
 ...

ヒント:

  1. この問題は簡単ではない。この問題を完全に理解するためにはいくらか時間が必要になるだろう。
  2. 読み込むデータファイルの解は、上記のようなファイルで提供される。
  3. 効率上の理由から、大きなパズルのために最小の所で、言葉やサイトを特定の順番で ソートすることが重要である。この問題の一部については、1.28 の解は非常に有効だろう。

0 件のコメント:

コメントを投稿