6

クラシックなチェッカーボード カバー パズルについて聞いたことがあるかもしれません。L字型のタイルを使用して、コーナーの正方形が1つ欠けているチェッカーボードをどのようにカバーしますか?

「Python 言語で基本的なアルゴリズムをマスターする Python アルゴリズム」という本で説明されているように、これには再帰的なアプローチがあります。

アイデアは、ボードを 4 つの小さな正方形に分割し、L 字型のタイルを大きなボードの中央に配置して、1 つのタイルが欠けている 4 つの小さな正方形を効果的に作成し、再帰を介して続行することです。

概念的には理解しやすいのですが、実装を考えるのは非常に難しいと思います。実装ソリューションの 1 つを次に示します。

    def cover(board, lab=1, top=0, left=0, side=None):
        if side is None: side = len(board)

        # Side length 
        s = side // 2

        # Offsets for outer/inner squares of subboards
        offsets = ((0, -1), (side-1, 0))

        for dy_outer, dy_inner in offsets:
            for dx_outer, dx_inner in offsets:
            # If the outer corner is not set...
                if not board[top+dy_outer][left+dx_outer]:
                # ... label the inner corner: 
                    board[top+s+dy_inner][left+s+dx_inner] = lab


        # Next label: 
        lab += 1
        if s > 1:
            for dy in [0, s]:
                for dx in [0, s]:
                    # Recursive calls, if s is at least 2:
                    lab = cover(board, lab, top+dy, left+dx, s)

        # Return the next available label: 
        return lab

コードを実行するには、次を取得します

    board = [[0]*8 for i in range(8)]
    board[7][7] = -1
    cover(board)
    for row in board:
        print((" %2i"*8)%tuple(row))

    3  3  4  4  8  8  9  9
    3  2  2  4  8  7  7  9
    5  2  6  6 10 10  7 11
    5  5  6  1  1 10 11 11
   13 13 14  1 18 18 19 19
   13 12 14 14 18 17 17 19
   15 12 12 16 20 17 21 21
   15 15 16 16 20 20 21 -1

この実装を理解するのに時間がかかりました。特にオフセットラインの背後にある考えを完全に理解しているかどうかさえわかりません。誰かが実装を簡潔に説明しようとすることができますか? この種の問題の解決策を考えるための直感をどのように発達させるのでしょうか? 特に彼らが行ったようにオフセットラインを設定することで、解決策が非常に巧妙であることがわかりました。誰かがこれを理解するのを手伝ってくれて、おそらくより良くなる方法についての提案をしてくれたら、私はそれを大いに感謝します.

ありがとう！

4

1 に答える 1

2

この種の問題の解決策を考えるための直感をどのように発達させるのでしょうか?

解決策は非常に巧妙で、問題に特化していますが、分割統治と呼ばれるより一般的な問題解決戦略の例でもあります。問題を完全に攻撃する代わりに、より小さなバージョンを作成し、それらを解決しようとします。紙と鉛筆で試行錯誤。これらのソリューションから学ぶべきことがあるかどうかを確認してください。

この場合、2x2 バージョンは簡単に解決できますが、解決策があることに注意することは興味深いことです。

以下は 4x4 ソリューションです。さて、しばらく眺めていると、2x2 のケースとの関連性に気付くかもしれません。各象限は基本的に2x2 のケースです。

3  3  4  4 
3  2  2  4  
5  2  6  6 
5  5  6 -1

特に彼らが行ったようにオフセットラインを設定することで、解決策は非常に巧妙であることがわかりました。誰かがこれを理解するのを助けることができれば[...]

ネストされたループを展開し、ループ変数を に表示されている値に置き換えると、おそらく理解しやすくなりますoffsets。次に、ループの代わりに 4 つの if ステートメントがあります。各ステートメントは、ボードの隅にある対応する正方形が設定されていない場合、中央の 4 つの正方形の 1 つを設定します。

#top left                    
if not board[top][left]:
    board[top+s-1][left+s-1] = lab
#top right    
if not board[top][left+side-1]:
    board[top+s-1][left+s] = lab
#bottom left    
if not board[top+side-1][left]:
    board[top+s][left+s-1] = lab
#bottom right    
if not board[top+side-1][left+side-1]:
    board[top+s][left+s] = lab

作成者はこのように書き始めたかもしれませんが、コードが反復的であることに気付き、代わりにループを作成しました。変数は、ステートメント間のoffsets違いを表します。

于 2015-05-26T15:41:07.737 に答える