fork(4) download 
  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 = set([queue[0].puzzle])
  63.     goal = (1, 2, 3,
  64.             4, 5, 6,
  65.             7, 8, 0)
  66.     while queue:
  67.         s = heapq.heappop(queue)
  68.         if (s.puzzle == goal):
  69.             for a in s.ancestry():
  70.                 print(a)
  71.                 print('')
  72.             print('Minimal number of moves: {}'.format(s.moves))
  73.             print('')
  74.             return
  75.         for c in s.children():
  76.             if c.puzzle not in seen:
  77.                 seen.add(c.puzzle)
  78.                 heapq.heappush(queue, c)
  79.  
  80. puzzle8([1, 3, 0,
  81.          8, 4, 5,
  82.          7, 2, 6])
  83.  
  84. puzzle8([3, 5, 1,
  85.          6, 8, 0,
  86.          7, 2, 4])
  87.  
Success #stdin #stdout 0.22s 9600KB
comments (?)
stdin 
Standard input is empty
stdout 
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 4
7 2  

3 5 1
6 8 4
7   2

3 5 1
6   4
7 8 2

3 5 1
  6 4
7 8 2

3 5 1
7 6 4
  8 2

3 5 1
7 6 4
8   2

3 5 1
7   4
8 6 2

3 5 1
7 4  
8 6 2

3 5 1
7 4 2
8 6  

3 5 1
7 4 2
8   6

3 5 1
7 4 2
  8 6

3 5 1
  4 2
7 8 6

3 5 1
4   2
7 8 6

3   1
4 5 2
7 8 6

  3 1
4 5 2
7 8 6

4 3 1
  5 2
7 8 6

4 3 1
5   2
7 8 6

4   1
5 3 2
7 8 6

4 1  
5 3 2
7 8 6

4 1 2
5 3  
7 8 6

4 1 2
5   3
7 8 6

4 1 2
  5 3
7 8 6

  1 2
4 5 3
7 8 6

1   2
4 5 3
7 8 6

1 2  
4 5 3
7 8 6

1 2 3
4 5  
7 8 6

1 2 3
4 5 6
7 8  

Minimal number of moves: 27
https://ideone.com/UZKd8b
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!