8 Puzzle (python)

重排九宫

+---+---+---+      +---+---+---+
| 1 | 2 | 3 |      | 8 | 7 | 6 |
+---+---+---+      +---+---+---+
| 4 | 5 | 6 |  ==> | 5 | 4 | 3 |
+---+---+---+      +---+---+---+
| 7 | 8 |   |      | 2 | 1 |   |
+---+---+---+      +---+---+---+

$ 8puzzle.py -f2
# 30
Number of states enqueued = 14754

#!/usr/bin/env python
 
import sys
from optparse import OptionParser
import math
from struct import pack
import heapq
 
class Solver:
    def __init__(self, n):
        self.N = n
        self.L = n * n
 
        self.GOAL = range(1, self.L)
        self.GOAL.append(0)
 
        # slide rules
        self.SR = {}
        for i in range(self.L):
            s = []
            if i - self.N >= 0:
                s.append(i - self.N)
            if (i % self.N) - 1 >= 0:
                s.append(i - 1)
            if (i % self.N) + 1 < self.N:
                s.append(i + 1)
            if i + self.N < self.L:
                s.append(i + self.N)
            self.SR[i] = s
 
        # queue
        self.queue = []
        self.enqueued = {}
 
        # verbose
        #self.verbose = 104999
        self.verbose = 8963
 
        # h
        self.w = 1
        self.h = self.heuristics
 
    def is_solvable(self, tiles):
        x = 0
        for p in range(len(tiles)):
            a = tiles[p]
            if a < 2 :
                continue
            for b in tiles[p:]:
                if b == 0:
                    continue
                if a > b:
                    x = x + 1
        return (x & 1) == 0
 
    def neighbors(self, tiles):
        n = []
        a = tiles.index(0)
        for b in self.SR[a]:
            n.append(self.swap(list(tiles), a, b))
        return n
 
    def swap(self, tiles, a, b):
        tiles[a], tiles[b] = tiles[b], tiles[a]
        return tiles
 
    def display(self, tiles):
        for i in range(self.L):
            if tiles[i]:
                print '%(n)#2d' % {'n': tiles[i]},
            else:
                print '  ',
            if i % self.N == self.N - 1:
                print
 
    def enqueue(self, state):
        (tiles, parent, h, g) = state
 
        if self.verbose > 0 and len(self.enqueued) % self.verbose == self.verbose - 1:
            print " -->", len(self.enqueued), g
 
        f = h * self.w + g;
        heapq.heappush(self.queue, (f, state))
 
    def dequeue(self):
        if len(self.queue) <= 0:
            return None
        (f, state) = heapq.heappop(self.queue)
        return state
 
    def heuristics(self, tiles):
        return 0;
 
    def manhattan(self, tiles):
        h = 0
        for i in range(self.L):
            n = tiles[i]
            if n == 0:
                continue
            h += int(abs(n - 1 - i) / self.N) + (abs(n - 1 - i) % self.N)
        return h
 
    def hamming(self, tiles):
        h = 0
        for i in range(self.L):
            n = tiles[i]
            if n > 0 and n - 1 != i:
                h += 1
        return h
 
    def solve(self, initial):
        if not self.is_solvable(initial):
            return None
 
        state = (initial, None, self.h(initial), 0);
        if initial == self.GOAL:
            return state
 
        self.enqueue(state)
 
        while True:
            state = self.dequeue()
            if (not state):
                break
 
            (tiles, parent, h, g) = state
            neighbors = self.neighbors(tiles)
            for n_tiles in neighbors:
                if n_tiles == self.GOAL:
                    return (n_tiles, state, 0, g + 1)
 
                packed = pack(self.L*'B', *n_tiles)
                if (packed in self.enqueued):
                    continue;
                self.enqueued[packed] = True                       
 
                n_state = (n_tiles, state, self.h(n_tiles), g + 1)
                self.enqueue(n_state)
 
def main(options, args):
    initial = []
    if args:
        for n in args:
            initial.append(int(n))
    else:
        initial = [8,7,6,5,4,3,2,1,0]
 
    solver = Solver(int(math.sqrt(len(initial))))
 
    solver.verbose = int(options.verbose)
    solver.w = float(options.weight)
    if int(options.function) == 1:
        solver.h = solver.hamming
    elif int(options.function) == 2:
        solver.h = solver.manhattan
 
    state = solver.solve(initial)
    if not state:
        print "No solution possible"
        return 1
 
    solution = []
    while state:
        (tiles, parent, h, g) = state
        solution.insert(0, tiles)
        state = parent
 
    n = 0
    for tiles in solution:
        print "#", n
        solver.display(tiles)
        print
        n += 1
 
    print "Number of states enqueued =", len(solver.enqueued)
    return 0
 
if __name__ == '__main__':
    parser = OptionParser(usage="usage: %prog [options] [tile] [tile] [tiles ...]")
    parser.add_option("-v", "--verbose", metavar="<level>",
            default=8963)
    parser.add_option("-f", "--function", metavar="<fid>",
            help="heuristics function. 1 for hamming, 2 for manhattan [default: None as breadth first]",
            default=0)
    parser.add_option("-w", "--weight", metavar="<n>",
            help="weighting of the heuristics function [default: 1]",
            default=1)
    (options, args) = parser.parse_args()
 
    sys.exit(main(options, args))

15 puzzle

+----+----+----+----+       +----+----+----+----+
| 15 | 14 | 13 | 12 |       |  1 |  2 |  3 |  4 |
+----+----+----+----+       +----+----+----+----+
| 11 | 10 |  9 |  8 |       |  5 |  6 |  7 |  8 |
+----+----+----+----+  ==>  +----+----+----+----+
|  7 |  6 |  5 |  4 |       |  9 | 10 | 11 | 12 |
+----+----+----+----+       +----+----+----+----+
|  3 |  1 |  2 |    |       | 13 | 15 | 14 |    |
+----+----+----+----+       +----+----+----+----+

$ 8puzzle.py -f2 -w1.9 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 0
# 76
Number of states enqueued = 2812200