CODEWITHSUNDEEP
pythonpython-3.xlistshufflesliding-tile-puzzle
DeadManProp
DeadManProp

Reputation: 89

How to shuffle a sliding tile puzzle without making it unsolvable? (Python 3)

I'm trying to figure out if there's a simple way to code a shuffling method/function in a sliding tile puzzle with 8 tiles, in Python 3. Here's what I mean.

Let's say this array represents our 9 squares, with 0 representing the empty space.

puzzle = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

I know there's a built-in shuffle() function in Python, but I cannot find information on whether it can be used to shuffle a 3x3 puzzle without making it unsolvable.

Upvotes: 0

Views: 3724

Answers (2)

OysterShucker
OysterShucker

Reputation: 5531

With this solution:

  1. you do not need to juggle a multi-dimensional list
  2. you can determine the amount of moves you want it to take
  3. it should work on a puzzle of any dimensions - even unequal ones

The logic is very simple. shuffle runs for the amount of moves you designated, getting the pieces surrounding the empty at every iteration. It then randomly chooses a piece from the returned pieces and swaps the selected piece with the empty one. It is the program equivalent of manually scrambling one of these puzzles by hand. Considering it always makes a valid move the final scrambled puzzle should always be solvable.

lastPiece is used to make sure we don't undo the previous move. It simply stores the index of the last move and then gets removed from the choices on the next iteration.

aside:
I'm sure you will probably use a list of graphics in the long run. Still use the numbers to get the shuffle. Once the number list is shuffled you can iterate over it and assign graphics to each position based on the number. Shuffling graphics data is a lot more CPU intensive than shuffling numbers.

edit:
As a bonus I added in the solution and solution parser (solve). Gimme about another hour and I'll make your whole game! :D The solution is compressed. Instead of something like [(2, 1), (1, 4), (4, 5)] where each tuple equals (to, from), since the from is always the next to (because from is the new empty index) we do this instead [2, 1, 4, 5] and juggle the compression in solve.

import random, math

def surroundingPieces(z, w, h):
    x = z%w
    y = math.floor(z/h)

    left  = None if x == 0 else z - 1
    up    = None if y == 0 else z - w
    right = None if x == (w-1) else z + 1
    down  = None if y == (h-1) else z + w

    return list(filter(None, [left, up, right, down]))

def shuffle(puzzle, moves, width, height):
    empty = puzzle.index(0)     #find initial empty index
    lastPiece = empty           #init lastPiece
    solution  = [empty]         #init solution

    for _ in range(moves):
        #get surrounding pieces
        pieces = surroundingPieces(empty, width, height)

        #remove the last piece we moved
        if lastPiece in pieces:
            pieces.remove(lastPiece)

        #select a piece
        pieceIndex = random.choice(pieces)
        solution.insert(0, pieceIndex) #insert move in solution

        #swap        
        puzzle[empty] = puzzle[pieceIndex]
        lastPiece = empty  #store this piece index

        puzzle[pieceIndex] = 0
        empty = pieceIndex #store new empty index

    return puzzle, solution

    
#this is the program equivalent of manually solving the puzzle
def solve(pzl, sol):
    for i in range(len(sol)-1):
        pzl[sol[i]]   = pzl[sol[i+1]]
        pzl[sol[i+1]] = 0
        
    return pzl

puzzle, solution = shuffle([1, 2, 3, 4, 0, 5, 6, 7, 8], 10, 3, 3)

print(puzzle)                       #[1, 3, 0, 7, 2, 6, 4, 8, 5]     
print(solution)                     #[2, 1, 4, 5, 8, 7, 4, 3, 6, 7, 4]
print(solve(puzzle[:], solution))   #[1, 2, 3, 4, 0, 5, 6, 7, 8]

Upvotes: 3

mujjiga
mujjiga

Reputation: 16876

Slow method: Shuffle until you get a solvable puzzle

A 3X3 is not solvable if it has odd number of inversions. Flow this answer for solvability of 3X3 puzzle.

Code

def is_solvable(puzzle):
  p = puzzle[puzzle != 0]
  inversions = 0
  for i, x in enumerate(p):
    for y in p[i+1:]:
      if x > y:
        inversions += 1
  return inversions % 2==0

# Now lets generate until we get a solvable puzzle
while True:
  puzzle = np.random.choice(np.arange(9), size=9, replace=False)
  if is_solvable(puzzle):
    break

print (puzzle.reshape(3,3))

output:

[[8 3 4]
 [2 1 7]
 [5 6 0]]

Upvotes: 2

Related Questions