初次Python 暴力解益智遊戲 ( 二 )

因為不可能讓程式自己獨立解出答案，改成可以支持各種操作的方式輔助縮減答案範圍，再用人腦解決。
第二次寫就好很多了，語法也比較熟悉。
這個版本支持輸入 $表示空的格子，也能指定遞迴深度，還有事先寫好哪些字是禁用的。利用的剪枝還是比較基礎，對於需要的長度的 multiset和超過最大長度就馬上返回。
這次學到的python比較坑的一點是，如果單純對兩個字串寫 T[ i ] = g[ i ]，似乎只會參照，也就是修改 T[ i ] 這個字串中的任何字都會直接影響 g[ i ]。還有 python中的字串是不能直接改變裡面的字元的，這點印象中跟 java是一樣的。

import enchant
from collections import Counter
d = enchant.Dict( "en_US" )
f = open( 'banned', 'r' )
banned = set()
for line in f:
    banned.add( line[ : -1 ] )

MAXLEN = 0

dx = [ 0, 1, 0, -1, 1, -1, 1, -1  ]
dy = [ 1, 0, -1, 0, -1, 1, 1, -1  ]

def outOfRange( x, y ):
    return x < 0 or x >= n or y < 0 or y >= m

def drop( g, path ):
    T = [ "" for i in xrange( n ) ]
    for i in xrange( n ):
        T[ i ] = g[ i ][ : ]
    for ( i, j ) in path:
        T[ i ] = T[ i ][ 0 : j ] + '$' + T[ i ][ j + 1 : ]
    for _i in xrange( n ):
        for j in xrange( m ):
            i = n - _i - 1
            if T[ i ][ j ] != '$': continue
            k = i
            while T[ k ][ j ] == '$':
                k -= 1
                if k < 0: break
            if k >= 0:
                T[ i ] = T[ i ][ 0 : j ] + T[ k ][ j ] + T[ i ][ j + 1 : ]
                T[ k ] = T[ k ][ 0 : j ] + '$' + T[ k ][ j + 1 : ]
    """for i in xrange( n ):
        for j in xrange( m ):
            print T[ i ][ j ],
        print ''"""
    return T

def rsolve( g, slist, depth ):
    global ans, vis
    if depth == dpt:
        if determine:
            for i in xrange( MAXLEN + 1 ):
                if qlen[ i ] > 0:
                    return
        print slist
        # ans.append( slist )
        return
    for i in xrange( n ):
        for j in xrange( m ):
            if g[ i ][ j ] != '$':
                for _i in xrange( n ):
                    for _j in xrange( m ):
                        vis[ depth + 1 ][ _i ][ _j ] = 0
                dfs( g, i, j, [], [], slist, depth + 1 )

def dfs( g, sx, sy, vc, path, slist, depth ):
    if len( vc ) > MAXLEN: return
    global vis, ans
    vis[ depth ][ sx ][ sy ] = 1
    vc.append( g[ sx ][ sy ] )
    path.append( ( sx, sy ) )
    s = ''.join( vc )
    if qlen[ len( s ) ] > 0 and d.check( s ) and s not in banned:
        qlen[ len( s ) ] -= 1
        T = drop( g, path )
        slist.append( s )
        rsolve( T, slist, depth )
        slist.pop()
        qlen[ len( s ) ] += 1
    for di in xrange( 8 ):
        nx = sx + dx[ di ]
        ny = sy + dy[ di ]
        if outOfRange( nx, ny ): continue
        if g[ sx ][ sy ] == '$': continue
        if vis[ depth ][ nx ][ ny ]: continue
        dfs( g, nx, ny, vc, path, slist, depth )
    path.pop()
    vc.pop()
    vis[ depth ][ sx ][ sy ] = 0

def printAns():
    if len( ans ) == 0:
        print "Answer not found, maybe some letter must be capitalized."
    else:
        for s in ans:
            print s

def solve():
    rsolve( G, [], 0 )
    # printAns()

G = [ "" for i in xrange( 8 ) ]
vis = [ [ [ 0 for i in xrange( 8 ) ] for j in xrange( 8 ) ] for depth in xrange( 30 ) ]
ans = []
qlen = Counter()

n = int( input( "n = " ) )
m = int( input( "m = " ) )
q = int( input( "q = " ) )
for i in xrange( q ):
    v = ( int( input( "len %d : " % ( i + 1 ) ) ) )
    qlen[ v ] += 1
    MAXLEN = max( MAXLEN, v )
determine = 0
dpt = int( input( "Try depth ( add 2 extra 0s to imply determination ) = " ) )
if dpt >= 100:
    dpt /= 100
    determine = 1

for i in xrange( n ):
    G[ i ] = raw_input( "Row %d : " % ( i + 1 ) )

solve()