0w1

初次Python 暴力解益智遊戲

Brain Word Puzzle - Google Play の Android アプリ
WordBrain on the App Store
這是一個文字遊戲,前面的關卡都是一個 4 * 3 的矩陣,每個格子裡有一個字母。會給兩個長度,相加等於 12,第一次操作要選擇一個字母當起點,然後移動到尚未拜訪的周圍八格其中一個別的字母,不斷進行直到為其中一個給定的長度,並且是一個合法的英文單字。完成這一步之後,其他格子會往下降,這時候再用一樣的方法另外一個單字就行了。
因為 python 有一個很有趣的函數庫 "enchant",可以查詢一個單字是否在英文字典裡,查詢速度也非常快,因此這次試著用python暴力解解看。
不過呢,後來發現後面的關卡最多可以到 7 * 7 的矩陣,並且是不定多的單字要完成,這夠我想一陣子的了。。
程式碼如下:

import enchant
from collections import deque
d = enchant.Dict( "en_US" )

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

len1 = -1 # int( input( "len1 = " ) )
len2 = -1 # int( input( "len2 = " ) )

G = {}
vis1 = set()
vis2 = set()

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

ans = set()

def dfs2( sx, sy, vc, s1, F ) :
    global len1
    global len2
    global G
    global vis1
    global vis2
    vis2.add( ( sx, sy ) )
    vc.append( F[ sx, sy ] )
    if len( vc ) + len( s1 ) == 12 and d.check( ''.join( vc ) ) :
        ans.add( ( ''.join( s1 ), ''.join( vc ) ) )
        vc.pop()
        vis2.remove( ( sx, sy ) )
        return
    for di in xrange( 8 ) :
        nx = sx + dx[ di ]
        ny = sy + dy[ di ]
        if outOfRange( nx, ny ) : continue
        if ( nx, ny ) in vis2 : continue
        if F[ nx, ny ] == '$' : continue
        dfs2( nx, ny, vc, s1, F )
    vc.pop()
    vis2.remove( ( sx, sy ) )

def middler( s1 ) :
    global len1
    global len2
    global G
    global vis1
    global vis2
    oth = []
    F = {}
    used = set()
    vis2 = set()
    for i in xrange( 4 ) :
        for j in xrange( 3 ) :
            k = i
            while ( i, j ) in vis1 or ( i, j ) in vis2:
                k = k - 1
                if k < 0 : break
            if k < 0 :
                F[ i, j ] = '$'
            else :
                F[ i, j ] = G[ k, j ]
                vis2.add( ( k, j ) )
    for i in xrange( 4 ) :
        for j in xrange( 3 ) :
            if ( i, j ) not in vis1 :
                vc = []
                vis2 = set()
                dfs2( i, j, vc, s1, F )

def dfs( sx, sy, vc ) :
    global len1
    global len2
    global G
    global vis1
    global vis2
    #if ccCount() > 1 : return
    vis1.add( ( sx, sy ) )
    vc.append( G[ sx, sy ] )
    if len( vc ) == len1 and d.check( ''.join( vc ) ):
        if len( vc ) == 12 :
            ans.add( ( ''.join( vc ), '' ) )
        else :
            middler( vc )
        vc.pop()
        vis1.remove( ( sx, sy ) )
        return
    for di in xrange( 8 ) :
        nx = sx + dx[ di ]
        ny = sy + dy[ di ]
        if outOfRange( nx, ny ) : continue
        if ( nx, ny ) in vis1 : continue
        dfs( nx, ny, vc )
    vc.pop()
    vis1.remove( ( sx, sy ) )

tried_name = 0

def show() :
    for i in xrange( 4 ) :
        for j in xrange( 3 ) :
            print G[ i, j ],
        print ''

def tryName() :
    global played_cnt
    global G
    for i in xrange( 4 ) :
        for j in xrange( 3 ) :
            G[ i, j ] = G[ i, j ].upper()
            #show()
            played_cnt = 0
            solve()
            played_cnt = 1
            G[ i, j ] = G[ i, j ].lower()
    printAns()

played_cnt = 0

def printAns() :
    global played_cnt
    global tried_name
    if len( ans ) == 0 :
        if tried_name == -1 and played_cnt == 1 : return
        if played_cnt == 1 :
            if tried_name == 0 :
                tried_name = -1 # trying
                print "Searching for names"
                tryName()
                tried_name = 1
            return
        played_cnt = 1
        global len1
        global len2
        temp = len1
        len1 = len2
        len2 = temp
        if tried_name == 0 :
            print "Answer not found, trying len1 = %d, len2 = %d" % ( len1, len2 )
        solve()
        return
    for ( a, b ) in ans :
        print a,
        print '/',
        print b

def solve() :
    global len1
    global len2
    global G
    global vis1
    global vis2
    vis1 = set()
    vis2 = set()
    for i in xrange( 4 ) :
        for j in xrange( 3 ) :
            vc = []
            dfs( i, j, vc )
    printAns()

def main() :
    global len1
    global len2
    global G
    global vis1
    global vis2
    for i in xrange( 4 ) :
        s = raw_input( "%d th row : " % ( i + 1 ) )
        for j in xrange( 3 ) :
            G[ i, j ] = s[ j ]
    len1 = int( input( "len1 = " ) )
    len2 = int( input( "len2 = " ) )
    solve()

if __name__ == "__main__":
        main()