0

私はテレビのタレントショーを見ていましたが、ある男が問題を解決するために全国 ( ! ) に挑戦しました。それを解決するための小さなスクリプトを書くことができるように感じますが、それでもどうにかして問題を認識する必要があります。したがって、問題は次のようになります。

    +---+---+---+
    |   |   |   |  -->
    +---+---+---+
    |   |   |   |  -->  sum of
    +---+---+---+       3 rows
    |   |   |   |  -->
    +---+---+---+

      |   |   |     also sum of
      v   v   v     2 diagonals
       sum of
       3 columns

マークされたすべての線で同じ合計が得られるように、上記の四角形にから1までの数字を書きます(例: 3 行、3 列、および 2 つの対角線の合計)。9

その後、彼は、大きな正方形を一時的に拡張し、次のように順番に数字を書くことによって、この問題のインスタンスの解決策を示し続けました。

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

次に、余分な四角形を削除し、それらの値をそれぞれ最も遠い空の四角形に配置しました。

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

それから彼は合計を得ました：

rows:
2 + 7 + 6 = 15
9 + 5 + 1 = 15
4 + 3 + 8 = 15

columns:
2 + 9 + 4 = 15
7 + 5 + 3 = 15
6 + 1 + 8 = 15

diagonals:
2 + 5 + 8 = 15
6 + 5 + 4 = 15

問題は、これを 100 x 100 の正方形で解決することです。

  1. これは何の問題ですか？
  2. NPコンプリートですか？
  3. どうすればこれを解決できますか?

詳細の一部を覚えていない可能性がありますが、まだ YouTube にはありませんので、お気軽に問題の変更を提案してください。

注テレビは素晴らしいです

4

2 に答える 2

2

これは「魔方陣」と呼ばれ、ウィキペディアには、それを生成するためのアルゴリズムの例がいくつかあります。

于 2012-11-24T21:33:00.907 に答える
2

このような正方形は MAGIC SQUARES と呼ばれます。http://en.wikipedia.org/wiki/Magic_square#Method_for_constructing_a_magic_square_of_odd_orderでそれらの構築について読んでください

于 2012-11-24T21:41:53.237 に答える