初次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()