-3

このようなボードがあるとしましょう

. . x . . .
. . . . . .
. . x . . x

x はボックスと '.' を使用します。は無料です。すべての領域を埋めるためにトリオミンを配置する必要があるため、空きセルはありません。トリオミンはL字型で、同じトリオミノには同じ番号をつけています。

したがって、解決策は次のようになります。

1 1 x 3 5 5
1 2 3 3 4 5
2 2 x 4 4 x

考えられるバックトラッキング python アルゴリズムは何ですか?

4

1 に答える 1

2

アルゴリズムは非常に単純です。最初に、このボード構成で使用可能なセルのリストを取得します。基本的に、禁止されているセルを除いたすべての可能なセルをリストします。

次に、利用可能なセル リストを反復処理し、4 つの可能な方向を使用してトリオミノ ピースをこの特定のセル位置に適合させようとすることで、ソリューション ステップを作成します (利用可能なセルは角であり、回転のために 4 つの方向があります)。

ピースが収まる場合は、ステップを増やし、使用可能なセルがなくなるまで、リストから占有されたセルを削除して、もう一度解決を試みます。これは、ボード全体がカバーされたことを意味します。

#!/usr/bin/env python

solution = {}

orientations = [(1,1),(1,-1),(-1,1),(-1,-1)]    # 4 possible orientations

def solve( avl, step ) :
    if not len(avl) :
        print 'done!'
        return True

    for i,j in avl :
        for oi,oj in orientations :
            if (i+oi,j) in avl and (i,j+oj) in avl :
                occupied = [(i,j),(i+oi,j),(i,j+oj)]
                # remove occupied from available, increase step and keep solving
                if solve( [a for a in avl if a not in occupied], step + 1 ) :
                    for occ in occupied :
                        solution[occ] = step
                    return True

# initial conditions for this configuration
#
# . . x . . .
# . . . . . .
# . . x . . x

X_SIZE, Y_SIZE = 6, 3
forbidden_cells = [(0,2),(2,2),(2,5)]

if __name__ == '__main__' :
    available = []

    # fill the available cells list
    for i in range(Y_SIZE) :
        for j in range(X_SIZE) :
            if (i,j) not in forbidden_cells :
                available.append( (i,j) )

    # print the original problem
    for i in range(Y_SIZE) :
        for j in range(X_SIZE) :
            print '.' if (i,j) in available else 'x',
        print

    # solve away!
    if solve( available, 1 ) :
        for i in range(Y_SIZE) :
            for j in range(X_SIZE) :
                print solution[(i,j)] if (i,j) in available else 'x',
            print
    else :
        print 'sorry, no solution found'

出力は次のとおりです。

$ ./triomines.py 
. . x . . .
. . . . . .
. . x . . x
done!
1 1 x 3 2 2
1 4 3 3 5 2
4 4 x 5 5 x
$
于 2014-05-19T20:48:02.837 に答える