如何为Puzzle Number 9制作一个有效的解算器

Question

有这个游戏,iOS并Andriod称为拼图9号(我与创作者没有任何联系).您从一个3x3网格开始,其中数字1到9随机放置在电路板上.然后组合相邻的数字(跟踪路径)以加起来9.路径中的最后一个节点变为9,所有其他数字增加1.您将相同的9的倍数组合在一起,其中结束节点变为数字的两倍并且起始节点返回到一个节点.例如,如果你开始

1 2 3
5 4 6
7 8 9 

你可以从2-3-4开始,然后结束

1 3 4
5 9 6
7 8 9

然后结合两个9

1 3 4
5 1 6
7 8 18

游戏的目标是达到1152.基本上它就像2048但没有随机元素.例如,当你用完总数为9的数字时,游戏结束

8 7 6
5 5 5
9 1 72

我写了一个简单的深度优先搜索python它适用于一些谜题,但我的内存耗尽其他谜题:

import sys
import Queue

conf = "213 547 689"
grid1 = []
for y in conf.split():
    for x in y:
        grid1.append(int(x))

a = []
explored = set()
sol = Queue.LifoQueue()

def tostr(node):
    s = ''
    for i in range(0,9):
        s += str(node[i]) + ' '
    return s

def printsol():
    while not sol.empty():
        print sol.get()        

def same(x, y, grid):
    for n in neighbors(y):
        ng = grid[:]
        if grid[n] == x and n != y:
            if x == 576:
                printsol()
                sys.exit()
            ng[n] = 2*x
            ng[y] = 1
            sol.put(tostr(ng))
            same(2*x, n, ng)
            solve(ng, grid)
            sol.get()
            ng[n] = 1
            ng[y] = 2*x
            sol.put(tostr(ng))
            same(2*x, y, ng)
            solve(ng, grid)
            sol.get()

##succeeding functions are edited versions of Boggle solver from http://stackoverflow.com/questions/746082/how-to-find-list-of-possible-words-from-a-letter-matrix-boggle-solver
def solve(grid2, grid1):
    for i in range(0,9):
        if grid2[i] < 9 and tostr(grid2) not in explored:
            for result in extending(grid2[i], (i,), grid2):
                newgrid = grid2[:]
                y = len(result) - 1
                for j in range(0, y):
                    newgrid[result[j]] += 1
                newgrid[result[y]] = 9
                sol.put(tostr(newgrid))
                if tostr(newgrid) not in explored:
                    same(9, result[y], newgrid)
                    solve(newgrid, grid2)
                sol.get()
    explored.add(tostr(grid2))

def extending(add, path, grid2):
    if add == 9:
        yield path
    for n in neighbors(path[-1]):
        if n not in path:
            add1 = add + grid2[n]
            if add1 <= 9:
                for result in extending(add1, path + (n,), grid2):
                    yield result

def neighbors(n):
    for nx in range(max(0, n%3-1), min(n%3+2, 3)):
        for ny in range(max(0, n/3-1), min(n/3+2, 3)):
            yield ny*3+nx

sol.put(tostr(grid1))
solve(grid1, grid1)

你如何提高效率？如果不是这样,对于知情搜索来说什么是一个很好的启发式？我想从一定数量上取出板上数字的平均值的绝对差值,但这个数字是多少呢？

Answer 1

我不久前写了一些东西并在这里发布：http://sourceforge.net/p/puzzlenumber9

这是一种强力搜索，但我对每个深度返回的选项进行排序，并限制深度以使其更快。我现在只是不记得我是如何排序和限制深度的，哈哈。（我将看一下代码，稍后当我有时间时添加...我认为代码只是在最后一次运行具有最高总和的每个深度处获取少量结果。）

我确实记得在看到程序返回解决方案感到满意后，在设备上输入路径一一移动似乎相当乏味:)

我喜欢这段代码的地方在于，它是随意组合在一起的，基本上是“完成工作”，而不是努力寻找最简洁、最有效的方法。我特别喜欢这个长长的case ix of列表，它打破了传统，挑战了功能的简化。

哈斯克尔代码：

{-# OPTIONS_GHC -O2 #-}
import Data.List (sortBy,nubBy)
import Data.Ord (compare)
import System.Time

main = do  
    putStrLn "Puzzle Number 9 Solver Copyright May 2015 alhambra1"
    putStrLn "\nEnter 'e' at any time to exit"
    putStrLn "\nEnter target number"
    target <- getLine  
    if null target  
        then main
        else if head target == 'e'    
                then return ()        
                else do 
                      putStrLn "Enter number of moves at each choice point (density, 3 to 6 recommended)"  
                      density <- getLine  
                      if null density  
                          then main
                          else if head density == 'e'    
                                  then return ()        
                                  else do 
                                        putStrLn "Enter board numbers separated by spaces"  
                                        board <- getLine  
                                        if null board  
                                            then main
                                            else if head board == 'e'    
                                                    then return ()        
                                                    else do 
                                                        putStrLn ""
                                                        time1 <- getClockTime 
                                                        let b = map (\x -> read x :: Int) (take 9 $ words board)
                                                            t = read (head (words target)) :: Int
                                                            d = read (head (words density)) :: Int
                                                        print (map reverse $ reverse $ head $ take 1 $ f t b [] d)
                                                        time2 <- getClockTime
                                                        putStrLn ""
                                                        print (timeDiffToString $ diffClockTimes time2 time1)
                                                        putStrLn ""
                                                        exit

exit = do
     putStrLn "Enter 'a' to start again or 'e' to exit"
     line <- getLine
     if null line 
        then exit
             else if head line == 'a'
                     then do putStrLn ""
                             main
                          else if head line == 'e'
                                  then return ()
                                  else exit

f target board paths toTake
  | not (null hasTarget) = [(((\(x,y,z)-> z) . head $ hasTarget):paths)]
  | null ms              = []
  | otherwise            = do (s,bd,idxs) <- take toTake (sortBy (\(x,y,z) (x',y',z') -> compare x' x) ms')
                              f target bd (idxs:paths) toTake
 where hasTarget = filter ((==target) . (\(x,y,z)-> x)) ms
       ms = moves board
       ms' = nubBy (\(x,y,z) (x',y',z') -> let a = drop 1 (init z)
                                               b = drop 1 (init z')
                                           in if not (null a) && not (null b)
                                                 then a == b
                                                 else False) ms

moves board = do j <- [1..9]
                 let num = board !! (j - 1)
                     board' = (take (j - 1) board) ++ [num + 1] ++ (drop j board)
                 moves' j board' num [j] 0 num
 where moves' ix board s idxs prev next
        | (s == 9 || multiple) && (length idxs > 1) = [(s,board',idxs)]
        | s > 9 && mod s 9 /= 0 = []
        | otherwise = case ix of
            1 -> if elem 2 idxs then [] else moves' 2 board' (s + b) (2:idxs) next b
                 ++ (if elem 4 idxs then [] else moves' 4 board' (s + d) (4:idxs) next d)
                 ++ (if elem 5 idxs then [] else moves' 5 board' (s + e) (5:idxs) next e)
            2 -> if elem 1 idxs then [] else moves' 1 board' (s + a) (1:idxs) next a
                 ++ (if elem 3 idxs then [] else moves' 3 board' (s + c) (3:idxs) next c)
                 ++ (if elem 4 idxs then [] else moves' 4 board' (s + d) (4:idxs) next d)
                 ++ (if elem 5 idxs then [] else moves' 5 board' (s + e) (5:idxs) next e)
                 ++ (if elem 6 idxs then [] else moves' 6 board' (s + f) (6:idxs) next f)
            3 -> if elem 2 idxs then [] else moves' 2 board' (s + b) (2:idxs) next b
                 ++ (if elem 5 idxs then [] else moves' 5 board' (s + e) (5:idxs) next e)
                 ++ (if elem 6 idxs then [] else moves' 6 board' (s + f) (6:idxs) next f)
            4 -> if elem 1 idxs then [] else moves' 1 board' (s + a) (1:idxs) next a
                 ++ (if elem 2 idxs then [] else moves' 2 board' (s + b) (2:idxs) next b)
                 ++ (if elem 5 idxs then [] else moves' 5 board' (s + e) (5:idxs) next e)
                 ++ (if elem 7 idxs then [] else moves' 7 board' (s + g) (7:idxs) next g)
                 ++ (if elem 8 idxs then [] else moves' 8 board' (s + h) (8:idxs) next h)
            5 -> if elem 1 idxs then [] else moves' 1 board' (s + a) (1:idxs) next a
                 ++ (if elem 2 idxs then [] else moves' 2 board' (s + b) (2:idxs) next b)
                 ++ (if elem 3 idxs then [] else moves' 3 board' (s + c) (3:idxs) next c)
                 ++ (if elem 4 idxs then [] else moves' 4 board' (s + d) (4:idxs) next d)
                 ++ (if elem 6 idxs then [] else moves' 6 board' (s + f) (6:idxs) next f)
                 ++ (if elem 7 idxs then [] else moves' 7 board' (s + g) (7:idxs) next g)
                 ++ (if elem 8 idxs then [] else moves' 8 board' (s + h) (8:idxs) next h)
                 ++ (if elem 9 idxs then [] else moves' 9 board' (s + i) (9:idxs) next i)
            6 -> if elem 2 idxs then [] else moves' 2 board' (s + b) (2:idxs) next b
                 ++ (if elem 3 idxs then [] else moves' 3 board' (s + c) (3:idxs) next c)
                 ++ (if elem 5 idxs then [] else moves' 5 board' (s + e) (5:idxs) next e)
                 ++ (if elem 8 idxs then [] else moves' 8 board' (s + h) (8:idxs) next h)
                 ++ (if elem 9 idxs then [] else moves' 9 board' (s + i) (9:idxs) next i)
            7 -> if elem 4 idxs then [] else moves' 4 board' (s + d) (4:idxs) next d
                 ++ (if elem 5 idxs then [] else moves' 5 board' (s + e) (5:idxs) next e)
                 ++ (if elem 8 idxs then [] else moves' 8 board' (s + h) (8:idxs) next h)
            8 -> if elem 4 idxs then [] else moves' 4 board' (s + d) (4:idxs) next d
                 ++ (if elem 5 idxs then [] else moves' 5 board' (s + e) (5:idxs) next e)
                 ++ (if elem 6 idxs then [] else moves' 6 board' (s + f) (6:idxs) next f)
                 ++ (if elem 7 idxs then [] else moves' 7 board' (s + g) (7:idxs) next g)
                 ++ (if elem 9 idxs then [] else moves' 9 board' (s + i) (9:idxs) next i)
            9 -> if elem 5 idxs then [] else moves' 5 board' (s + e) (5:idxs) next e
                 ++ (if elem 6 idxs then [] else moves' 6 board' (s + f) (6:idxs) next f)
                 ++ (if elem 8 idxs then [] else moves' 8 board' (s + h) (8:idxs) next h)
          where multiple = length idxs == 2 && prev == next && mod s 9 == 0
                [a,b,c,d,e,f,g,h,i] = board
                board' = if s == 9
                            then (take (headIdxs - 1) board) ++ [9] ++ (drop headIdxs board)
                            else if multiple
                                    then board''
                                    else (take (headIdxs - 1) board) ++ [next + 1] ++ (drop headIdxs board)
                board'' = map (\(x,y) -> if x == headIdxs then y * 2 else if x == last idxs then 1 else y) (zip [1..] board)
                headIdxs = head idxs