fork download
copy 
  1. #!/usr/bin/python3
  2.  
  3. import heapq
  4.  
  5. class state(object):
  6.     __slots__ = ['zero', 'puzzle', 'moves', 'parent', 'key']
  7.     def __init__(self, zero, puzzle, moves, parent=None):
  8.         self.zero = zero
  9.         self.puzzle = puzzle
  10.         self.moves = moves
  11.         self.parent = parent
  12.         self.key = self.heuristics() + self.moves
  13.     def heuristics(self):
  14.         h = 0
  15.         for i, p in enumerate(self.puzzle):
  16.             if p != 0:
  17.                 r1, c1 = divmod(i, 3)
  18.                 r2, c2 = divmod(p - 1, 3)
  19.                 h += abs(r1 - r2) + abs(c1 - c2)
  20.         return h
  21.     def children(self):
  22.         row, col = divmod(self.zero, 3)
  23.         if row > 0: yield self.child(self.zero - 3)
  24.         if row < 2: yield self.child(self.zero + 3)
  25.         if col > 0: yield self.child(self.zero - 1)
  26.         if col < 2: yield self.child(self.zero + 1)
  27.     def child(self, newpos):
  28.         p = list(self.puzzle)
  29.         p[self.zero] = p[newpos]
  30.         p[newpos] = 0
  31.         return state(newpos, tuple(p), self.moves + 1, self)
  32.     def ancestry(self):
  33.         a = []
  34.         s = self
  35.         while s:
  36.             a.append(s)
  37.             s = s.parent
  38.         return reversed(a)
  39.     def __lt__(self, other):
  40.         return self.key < other.key
  41.     def __le__(self, other):
  42.         return self.key <= other.key
  43.     def __gt__(self, other):
  44.         return self.key > other.key
  45.     def __ge__(self, other):
  46.         return self.key >= other.key
  47.     def __str__(self):
  48.         s = tuple((str(i) if i else ' ') for i in self.puzzle)
  49.         return '{} {} {}\n{} {} {}\n{} {} {}'.format(*s)
  50.  
  51. def puzzle8(p):
  52.     assert len(p) == 9
  53.     assert frozenset(p) == frozenset(range(9))
  54.     p = tuple(p)
  55.     zero = None
  56.     for i, pi in enumerate(p):
  57.         if pi == 0:
  58.             zero = i
  59.             break
  60.     assert p[zero] == 0
  61.     queue = [state(zero, p, 0)]
  62.     seen = dict()
  63.     seen[queue[0].puzzle] = queue[0]
  64.     goal = (1, 2, 3,
  65.             4, 5, 6,
  66.             7, 8, 0)
  67.     while queue:
  68.         s = heapq.heappop(queue)
  69.         if (s.puzzle == goal):
  70.             for a in s.ancestry():
  71.                 print(a)
  72.                 print('')
  73.             print('Minimal number of moves: {}'.format(s.moves))
  74.             print('')
  75.             return
  76.         for c in s.children():
  77.             try:
  78.                 o = seen[c.puzzle]
  79.                 if o.key > c.key:
  80.                     o.moves = c.moves
  81.                     o.parent = c.parent
  82.                     o.key = c.key
  83.                     heapq.heapify(queue) # heapq has no decrease key op
  84.             except KeyError:
  85.                 seen[c.puzzle] = c
  86.                 heapq.heappush(queue, c)
  87.  
  88. puzzle8([1, 3, 0,
  89.          8, 4, 5,
  90.          7, 2, 6])
  91.  
  92. puzzle8([3, 5, 1,
  93.          6, 8, 0,
  94.          7, 2, 4])
  95.  
Success #stdin #stdout 0.39s 10552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 3  
8 4 5
7 2 6

1   3
8 4 5
7 2 6

  1 3
8 4 5
7 2 6

8 1 3
  4 5
7 2 6

8 1 3
4   5
7 2 6

8 1 3
4 2 5
7   6

8 1 3
4 2 5
  7 6

8 1 3
  2 5
4 7 6

  1 3
8 2 5
4 7 6

1   3
8 2 5
4 7 6

1 2 3
8   5
4 7 6

1 2 3
  8 5
4 7 6

1 2 3
4 8 5
  7 6

1 2 3
4 8 5
7   6

1 2 3
4   5
7 8 6

1 2 3
4 5  
7 8 6

1 2 3
4 5 6
7 8  

Minimal number of moves: 16

3 5 1
6 8  
7 2 4

3 5 1
6   8
7 2 4

3 5 1
  6 8
7 2 4

3 5 1
7 6 8
  2 4

3 5 1
7 6 8
2   4

3 5 1
7 6 8
2 4  

3 5 1
7 6  
2 4 8

3 5 1
7   6
2 4 8

3 5 1
  7 6
2 4 8

3 5 1
2 7 6
  4 8

3 5 1
2 7 6
4   8

3 5 1
2   6
4 7 8

3   1
2 5 6
4 7 8

3 1  
2 5 6
4 7 8

3 1 6
2 5  
4 7 8

3 1 6
2   5
4 7 8

3   6
2 1 5
4 7 8

  3 6
2 1 5
4 7 8

2 3 6
  1 5
4 7 8

2 3 6
1   5
4 7 8

2 3 6
1 5  
4 7 8

2 3  
1 5 6
4 7 8

2   3
1 5 6
4 7 8

  2 3
1 5 6
4 7 8

1 2 3
  5 6
4 7 8

1 2 3
4 5 6
  7 8

1 2 3
4 5 6
7   8

1 2 3
4 5 6
7 8  

Minimal number of moves: 27
https://ideone.com/XRC69t
language:
Python 3 (python  3.12)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!