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

除了細節稍做改良之外，提供路徑打印模式，有答案便能快速給出路徑。現在配合人腦，勉強能解出5 * 5。
還有些功能正在思考怎麼實作比較好：
像是若知道某些字串存在，但不知道何時何地使用，是否能做合理的剪枝。
也該做某種東西顯示它大略的進度，否則還要跑多久是完全不會有概念的。

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 printPath( path ):
    G = [ [ '$' for j in xrange( m ) ] for i in xrange( n ) ]
    cnt = 1
    for ( x, y ) in path:
        G[ x ][ y ] = cnt
        cnt += 1
    print '--------'
    for i in xrange( n ):
        for j in xrange( m ):
            print G[ i ][ j ],
        print ''

def rsolve( g, slist, plist, depth ):
    if PRINT_MODE == -1: return
    global ans, vis, PRINT_MODE
    if depth == dpt:
        if PRINT_MODE:
            for path in plist:
                printPath( path )
            PRINT_MODE = -1
        else:
            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, plist, depth + 1 )

def dfs( g, sx, sy, vc, path, slist, plist, depth ):
    if PRINT_MODE == -1: return
    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 PRINT_MODE and s not in ans:
        path.pop()
        vc.pop()
        vis[ depth ][ sx ][ sy ] = 0
        return
    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 )
        if PRINT_MODE: plist.append( path )
        rsolve( T, slist, plist, depth )
        if PRINT_MODE: plist.pop()
        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, plist, 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 = set()
qlen = Counter()

PRINT_MODE = 0

n = int( input( "n ( 999 for PRINTPATH mode )= " ) )
if n == 999:
    PRINT_MODE = 1
    n = int( input( "n = " ) )
m = int( input( "m = " ) )
q = int( input( "q = " ) )
for i in xrange( q ):
    if PRINT_MODE:
        s = ( raw_input( "Ans %d = " % ( i + 1 ) ) )
        for i in xrange( len( s ) + 1 ):
            ans.add( s[ 0 : i ] )
        qlen[ len( s ) ] += 1
        MAXLEN = max( MAXLEN, len( s ) )
    else:
        v = ( int( input( "len %d : " % ( i + 1 ) ) ) )
        qlen[ v ] += 1
        MAXLEN = max( MAXLEN, v )
dpt = int( input( "Try depth = " ) )

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

solve()