Test cases for the 8-puzzle:

  1 2 3       (3 steps)
    4 6
  7 5 8

------------------------

  3 1 2       (22 steps)
  6 4 5
    7 8

------------------------

  2 6 4       (16 steps)
  5 7 3
  1 8
  
------------------------

  3 2 1       (No solution)
  6 5 4
    8 7
    
------------------------

  8 1 2       (18 steps)
  7   3
  6 5 4


Test cases for the 6-gear puzzle:

     3     5
   /   \ /   \
  6     2     8    (2 steps)
  |     |     |
  9     1     10
   \   / \   /
     7     4
    
------------------------

     2     1
   /   \ /   \
  5     4     3    (10 steps)
  |     |     |
  8     7     6
   \   / \   /
    10     9
    
------------------------

     5     4
   /   \ /   \
  2     1     7    (22 steps)
  |     |     |
  3     10    6
   \   / \   /
     9     8
     
------------------------

     2     3
   /   \ /   \
  7     6     9    (12 steps)
  |     |     |
  4     10    5
   \   / \   /
     1     8
     
------------------------

     1     7
   /   \ /   \
  2     6     8    (21 steps)
  |     |     |
  3     5     9
   \   / \   /
     4    10