A N-Puzzle or sliding puzzle is a popular puzzle that challenges a player to slide pieces on a board to establish a certain end configuration. The pieces to be moved may consist of numbers, letters, or sections of a larger picture (like a jigsaw puzzle).
It consists of N tiles where N can be 8, 15, 24, and so on and one empty space where the tiles can be moved. The puzzle can be solved by moving the tiles one by one in the single empty space and thus achieving the target configuration. Typically, the goal of the puzzle is to place the tiles in numerical or alphabetical order.
import pygame, sys, random, copy from pygame.locals import * import enum, configparser from heapq import heappush, heappop
This code is based on Making Games with Python & Pygame, Slide Puzzle by Al Sweigart, [email protected], http://inventwithpython.com/pygame, Creative Commons BY-NC-SA 3.0 US and it is released under the same license.
BLANK = None # Blank tile # Define the colors of the game. BLACK = ( 0, 0, 0) WHITE = (255, 255, 255) BRIGHTBLUE = ( 0, 50, 255) NAVYBLUE = ( 0, 0, 128) ROYALBLUE = ( 65, 105, 225) global game TILECOLOR = ROYALBLUE TEXTCOLOR = WHITE BORDERCOLOR = BRIGHTBLUE BGCOLOR = NAVYBLUE MESSAGECOLOR = WHITE
An enumeration is a set of symbolic names (members) bound to unique, constant values. Enumerations can be used to create simple custom data types.
class Movement(enum.Enum): """ It represents the four movements of the game. """ LEFT = 'left' UP = 'up' DOWN = 'down' RIGHT = 'right' def allMovement(): return [Movement.LEFT, Movement.DOWN, Movement.UP, Movement.RIGHT] def opposite(self): if self == Movement.UP: return Movement.DOWN elif self == Movement.DOWN: return Movement.UP elif self == Movement.RIGHT: return Movement.LEFT elif self == Movement.LEFT: return Movement.RIGHT def coordinates(self): if self == Movement.LEFT: return [1, 0] elif self == Movement.DOWN: return [0, -1] elif self == Movement.RIGHT: return [-1, 0] elif self == Movement.UP: return [0, 1] class Mode(enum.Enum): # It represents the three modes of playing the game. The pieces or tiles could consist of numbers, letters, or sections of a picture. Text = 1 Letters = 2 Image = 3
class Game: # It represents the game itself def __init__(self): self.running = True # It indicates that the game is runnning. pygame.init() # It initializes all imported pygame modules. self.fpsClock = pygame.time.Clock( ) # A pygame.time.Clock object helps us to make sure our program runs at a certain FPS. self.config = configparser.ConfigParser() # We create an instance of the main configuration parser.
We will use the ConfigParser module to manage a user-editable configuration file for our application. It provides a structure similar to what’s found in Microsoft Windows INI files. Our config file slidepuzzle.ini is quite simple:
[BASIC] # The file consists of sections, each of which contains keys with values. COLUMNS = 4 ROWS = 4 WINDOWWIDTH = 640 WINDOWHEIGHT = 480 TILESIZE = 90 FPS = 30 INITIALRANDOM = 7 MODE = 3
self.config.read("slidepuzzle.ini") # We read the configuration file. self.font = pygame.font.Font(pygame.font.get_default_font(), 20) # pygame.font.Font allows us to render fonts in the game. WINDOWWIDTH = int(self.config['BASIC']['WINDOWWIDTH']) WINDOWHEIGHT = int(self.config['BASIC']['WINDOWHEIGHT']) self.tilesize = int(self.config['BASIC']['TILESIZE']) # It indicates the size of the board's tiles. self.mode = Mode(int(self.config['BASIC']['MODE'])) # It indicates the mode of the game: text, letters, or image. self.screen = pygame.display.set_mode((WINDOWWIDTH, WINDOWHEIGHT)) # It sets the display mode and creates an instance of the pygame.Surface class. self.columns = int(self.config['BASIC']['COLUMNS']) # Number of columns in the board. self.rows = int(self.config['BASIC']['ROWS']) # Number of rows in the board. self.image = self.load_puzzle_image("myImage.jpg", image_size=(self.tilesize*self.columns, self.tilesize*self.rows)) # It loads the image for the puzzle. # It creates Surface and Rect objects for out three buttons: Reset, New Game, and Solve. self.reset_surf, self.reset_rect = self.makeText('Reset', TEXTCOLOR, TILECOLOR, WINDOWWIDTH - 120, WINDOWHEIGHT - 90) self.new_surf, self.new_rect = self.makeText('New Game', TEXTCOLOR, TILECOLOR, WINDOWWIDTH - 120, WINDOWHEIGHT - 60) self.solve_surf, self.solve_rect = self.makeText('Solve', TEXTCOLOR, TILECOLOR, WINDOWWIDTH - 120, WINDOWHEIGHT - 30) self.xmargin = int((WINDOWWIDTH - (self.tilesize * self.columns)) / 2) self.ymargin = int((WINDOWHEIGHT - (self.tilesize * self.rows)) / 2) self.fps = int(self.config['BASIC']['FPS']) # Our frame rate (expressed in frames per second or FPS). It is the frequency or rate at which consecutive images or frames are captured or displayed in the game. pygame.display.set_caption('Slide Puzzle') # It sets the current window caption. self.board = self.targetBoard =  # It initializes our main and target boards. The main board represents the current game state. self.tiles =  # It will store the image that is divided into tiles. self.allUserMoves =  self.targetBoard = self.getStartingBoard() self.randomBoard(int(self.config['BASIC']['INITIALRANDOM'])) self.MOUSEBUTTONUP = self.KEYUP = False self.KEYLEFT = self.KEYRIGHT = self.KEYUP = self.KEYDOWN = False self.slideTo = None # It is an attribute that keeps the direction, if any, a tile should slide. def load_puzzle_image(self, path, image_size): """ It loads the puzzle image. The image is scaled to the image_size param.""" surface = pygame.image.load(path).convert_alpha() return pygame.transform.scale(surface, image_size) def randomBoard(self, numMovements): """ It will create a random board. """ self.board = self.getStartingBoard() # It starts in a ordered, solved board... lastMove = None for i in range(numMovements): # ... and randomly scramble it by generating "numNovements" random movements. move = self.getRandomMove(lastMove) self.slideAnimation(move, 'Generating a new puzzle...', animationSpeed=int(self.tilesize / 3)) self.makeMove(move) lastMove = move def isValidMove(self, move): """ It returns True if move is possible or valid. Otherwise, it returns False.""" blankx, blanky = self.getBlankPosition()
self.getBlankPosition() gets the x, y coordinates of the blank spot.
A move swaps or interchanges the blank tile with one of its neighboring tiles. If we want to move UP, the blank will move down, so the movement is only valid is blanky is not self.rows - 1. In other words, the blank tile is not in the last row.
return (move == Movement.UP and blanky != self.rows - 1) or \ (move == Movement.DOWN and blanky != 0) or \ (move == Movement.LEFT and blankx != self.columns - 1) or (move == Movement.RIGHT and blankx != 0) def getRandomMove(self, lastMove=None): """ It generates a random move. It is used by randomBoard to create a random board.""" validMoves = Movement.allMovement() # This is a list of all possible moves. # It removes those moves from the list that are not valid. It also removes pointless moves. If you have moved previously to the left (lastMove), and then slid a tile to the right, you would end up with the same board you had at the start. if lastMove == Movement.UP or not self.isValidMove(Movement.DOWN): validMoves.remove(Movement.DOWN) if lastMove == Movement.DOWN or not self.isValidMove(Movement.UP): validMoves.remove(Movement.UP) if lastMove == Movement.LEFT or not self.isValidMove(Movement.RIGHT): validMoves.remove(Movement.RIGHT) if lastMove == Movement.RIGHT or not self.isValidMove(Movement.LEFT): validMoves.remove(Movement.LEFT) # It returns a random move from the list of remaining moves. return random.choice(validMoves) def getStartingBoard(self):
It returns a board with tiles in the solved state. The image “self.image” is divided into tiles or blocks and saved in the array “self.tiles”.
For example, if we want a 3×3 board, it returns [[1, 4, 7], [2, 5, 8], [3, 6, BLANK]] where all the tiles are in order and the blank tile is in the lower right corner. Notice that the numbers on the tiles increase by 1 going across the row, not down the column. Going down the column, the numbers of the tiles increase by the size of the board’s width or columns.
counter = 1 board =  for x in range(self.columns): column =  columnTiles =  for y in range(self.rows): column.append(counter) counter += self.columns columnTiles.append(self.image.subsurface (x*self.tilesize, y*self.tilesize, self.tilesize, self.tilesize)) # self.image.subsurface returns a surface that represents a rectangular section of the (jigsaw) image. board.append(column) self.tiles.append(columnTiles) counter -= self.columns*(self.rows-1) + self.columns - 1 board[self.columns-1][self.rows-1] = BLANK return board def makeText(self, message, color, bgcolor, top, left): """ It creates the Surface and Rect objects for the message. These are used for drawing and positioning our message on the screen. """ textSurf = self.font.render(message, True, color, bgcolor) textRect = textSurf.get_rect() textRect.topleft = (top, left) return (textSurf, textRect) def drawMessage(self, message): """ This method handles the drawing of message at the top of the window. """ textSurf, textRect = self.makeText(message, MESSAGECOLOR, BGCOLOR, 5, 5) self.screen.blit(textSurf, textRect) def drawBoard(self): """ It draws the current board. """ left, top = self.getLeftTopOfTile(0, 0) width = self.columns * self.tilesize height = self.rows * self.tilesize self.screen.fill(BGCOLOR) # It completely fills over the main display Surface object before anything else so that we can start from scratch. pygame.draw.rect(self.screen, BORDERCOLOR, (left - 4, top - 4, width + 10, height + 10), 4) # It draws a border along the tiles. # It draws each and every tile to the main Surface object by calling the drawTile() method. for tilex in range(self.columns): for tiley in range(self.rows): if self.board[tilex][tiley]: self.drawTile(tilex, tiley, self.board[tilex][tiley]) def drawButtons(self): # It draws our game's buttons: Reset, New Game, and Solve. self.screen.blit(self.reset_surf, self.reset_rect) self.screen.blit(self.solve_surf, self.solve_rect) self.screen.blit(self.new_surf, self.new_rect) def drawGame(self, message=None): # It draws the actual state of the game. self.drawBoard() # It draws the current board. self.drawMessage(message) self.drawButtons() # It draws the three buttons. pygame.display.update() # It will update the full display surface to the screen. self.fpsClock.tick(self.fps) # It just sets up how fast our game should run. def drawTile(self, tilex, tiley, number, adjx=0, adjy=0): # It draws a tile on the board. tilex and tiley are the board coordinates of the tile. The adjx and adjy parameters are used for making small adjustments to the position of the tile. They are used for _sliding_ tiles into their final positions. left, top = self.getLeftTopOfTile(tilex, tiley) # It converts the board coordinates (tilex, tiley) to pixel coordinates. These pixel coordinates will be stored in the variables left and top respectively. if self.mode==Mode.Image: # If we are playing in "Image" mode, we draw the tile's surface that contains the tile's section of the image onto the main Surface. self.screen.blit(self.tiles[tilex][tiley], (left + adjx, top + adjy, self.tilesize, self.tilesize)) return # We create the Surface object with the text or letter drawn on it and the Rect object for positioning the Surface object. pygame.draw.rect(self.screen, TILECOLOR, (left + adjx, top + adjy, self.tilesize, self.tilesize)) if self.mode==Mode.Text: textSurf = self.font.render(str(number), True, TEXTCOLOR) elif self.mode==Mode.Letters: textSurf = self.font.render(chr(number+64), True, TEXTCOLOR) textRect = textSurf.get_rect() textRect.center = left + int(self.tilesize / 2) + adjx, top + int(self.tilesize / 2) + adjy self.screen.blit(textSurf, textRect) # We draw the Surface object with the text or letter drawn on it onto the main Surface. def getLeftTopOfTile(self, tileX, tileY): """ It converts the board coordinates in tilex and tiley to pixel coordinates.""" left = self.xmargin + (tileX * self.tilesize) + tileX top = self.ymargin + (tileY * self.tilesize) + tileY return (left, top) def getBlankPosition(self): """ It returns the x and y board coordinates of the blank space/spot.""" for x in range(self.columns): for y in range(self.rows): if self.board[x][y] == BLANK: return (x, y) def getSpotClicked(self, x, y): """ It converts from pixel coordinates (x, y) to board coordinates.""" for tileX in range(self.columns): for tileY in range(self.rows): left, top = self.getLeftTopOfTile(tileX, tileY) tileRect = pygame.Rect(left, top, self.tilesize, self.tilesize) # The tileRect is a Rect object that represents the tile's place on the board. if tileRect.collidepoint(x, y): # It uses the "collidepoint" method of the Rect class to check if the pixel coordinates (x, y) are inside the tile's area. return (tileX, tileY) return (None, None) def nextMovement(self, spotx, spoty): # It checks if the clicked tile was next to the blank tile. If this is the case, it updates the attribute "slideTo" with the value that the tile should slide to. blankx, blanky = self.getBlankPosition() if spotx == blankx + 1 and spoty == blanky: self.slideTo = Movement.LEFT elif spotx == blankx - 1 and spoty == blanky: self.slideTo = Movement.RIGHT elif spotx == blankx and spoty == blanky + 1: self.slideTo = Movement.UP elif spotx == blankx and spoty == blanky - 1: self.slideTo = Movement.DOWN def solve(self): """ It returns True if the puzzle is solved. Otherwise, it returns False. """ return self.board == self.targetBoard
The method gameLoop controls the overall flow for the entire game program. There are three tasks: 1. Check all events. 2. Process these events and take action accordingly. 3. Draw the current state of the game so the player can see what is going on.
def gameLoop(self): while self.running: msg = 'Click on a tile or press the arrow keys to slide.' if self.solve(): msg = 'The puzzle is solved!' self.drawGame(msg) # If the player is actually playing, we draw the game. self.check_events() # It checks all the events. # Now, we are going to process the events. if self.MOUSEBUTTONUP: # If the user has released a mouse's button over the game's window ... spotx, spoty = self.getSpotClicked(self.pos, self.pos) # We call the getSpotClicked() method with the mouse's coordinates. It returns the board coordinates of the spot on the board where the mouse was released. if (spotx, spoty) == (None, None): # The mouse button was not released over the board. if self.reset_rect.collidepoint(self.pos): # However, it was released over the Reset button. self.resetAnimation() self.allUserMoves =  elif self.new_rect.collidepoint(self.pos): # The mouse button was released over the New Game button. self.randomBoard(int(self.config['BASIC']['INITIALRANDOM'])) self.allUserMoves =  elif self.solve_rect.collidepoint(self.pos): # The mouse button was released over the Solve button. solve(self.board, self.targetBoard, self.getBlankPosition(), self.rows, self.columns) self.allUserMoves =  else: self.nextMovement(spotx, sporty) # It checks if the clicked tile was next to the blank tile. If this is the case, it updates the slideTo attribute. elif self.KEYUP: # It checks if the user has pressed an arrow key to slide a tile and it also makes sure that the movement is a valid one. If this is the case, it updates the "slideTo" attribute. if self.KEYLEFT and self.isValidMove(Movement.LEFT): self.slideTo = Movement.LEFT elif self.KEYRIGHT and self.isValidMove(Movement.RIGHT): self.slideTo = Movement.RIGHT elif self.KEYUP and self.isValidMove(Movement.UP): self.slideTo = Movement.UP elif self.KEYDOWN and self.isValidMove(Movement.DOWN): self.slideTo = Movement.DOWN if self.slideTo: # If slideTo has been set then we call the slideAnimation() method to perform the sliding animation. The method's parameters are the direction of the slide, a message to display and inform the user while sliding the tile, and the speed of the animation. self.slideAnimation(self.slideTo, 'Click a tile or press the arrow keys to slide.', animationSpeed=int(self.tilesize / 10)) self.makeMove(self.slideTo) # Next, we need to update the game's board. self.allUserMoves.append(self.slideTo) # And add this "move" or slide to our movement list. self.slideTo = None pygame.display.update() # It will update the full display surface to the screen. self.fpsClock.tick(self.fps) self.reset_keys() # We reset the keys as we have already processed the key's associated event. def swapTiles(self, x, y, x2, y2): self.board[x][y], self.board[x2][y2] = self.board[x2][y2], self.board[x][y] self.tiles[x][y], self.tiles[x2][y2] = self.tiles[x2][y2], self.tiles[x][y] def makeMove(self, move): # It updates the game's board and tiles. blankx, blanky = self.getBlankPosition() if move == Movement.UP: self.swapTiles(blankx, blanky, blankx, blanky + 1) elif move == Movement.DOWN: self.swapTiles(blankx, blanky, blankx, blanky - 1) elif move == Movement.LEFT: self.swapTiles(blankx, blanky, blankx + 1, blanky) elif move == Movement.RIGHT: self.swapTiles(blankx, blanky, blankx - 1, blanky) def slideAnimation(self, direction, message, animationSpeed): # It performs the sliding animation. blankx, blanky = self.getBlankPosition() # It returns where the blank tile is. if direction == Movement.UP: # It calculates the board coordinates of the tile that will slide from movex, movey to blankx, blanky. movex = blankx movey = blanky + 1 elif direction == Movement.DOWN: movex = blankx movey = blanky - 1 elif direction == Movement.LEFT: movex = blankx + 1 movey = blanky elif direction == Movement.RIGHT: movex = blankx - 1 movey = blanky self.drawGame(message) # The copy() method of our main Surface object (self.screen) will return a new Surface object that has the same image drawn to it. baseSurf = self.screen.copy() # It draws a blank space over the moving tile on the baseSurf Surface. moveLeft, moveTop = self.getLeftTopOfTile(movex, movey) pygame.draw.rect(baseSurf, BGCOLOR, (moveLeft, moveTop, self.tilesize, self.tilesize)) for i in range(0, self.tilesize, animationSpeed):
It animates the tile by drawing a number of frames. First, we draw the baseSurf surface on our main display Surface (self.screen), and then we draw the sliding tile closer and closer to its final position (e.g., if the direction of the movement is UP, the tile will move or slide from movex, movey to movex, movey-self.tilesize).
self.screen.blit(baseSurf, (0, 0)) if direction == Movement.UP: self.drawTile(movex, movey, self.board[movex][movey], 0, -i) if direction == Movement.DOWN: self.drawTile(movex, movey, self.board[movex][movey], 0, i) if direction == Movement.LEFT: self.drawTile(movex, movey, self.board[movex][movey], -i, 0) if direction == Movement.RIGHT: self.drawTile(movex, movey, self.board[movex][movey], i, 0) pygame.display.update() self.fpsClock.tick(self.fps) def check_events(self): # Pygame handles all its event messaging through an event queue. This method checks all these events. for event in pygame.event.get(): # It gets events from the queue. if event.type == pygame.QUIT: self.running = False sys.exit() if event.type == pygame.MOUSEBUTTONUP: self.MOUSEBUTTONUP = True self.pos = event.pos elif event.type == KEYUP: self.KEYUP = True if event.key in (K_LEFT, K_a): self.KEYLEFT = True elif event.key in (K_RIGHT, K_d): self.KEYRIGHT = True elif event.key in (K_UP, K_w): self.KEYUP = True elif event.key in (K_DOWN, K_s): self.KEYDOWN = True def reset_keys(self): # Reset all the keys self.MOUSEBUTTONUP = False self.KEYUP = False self.KEYLEFT = self.KEYRIGHT = self.KEYUP = self.KEYDOWN = False def resetAnimation(self): # It undoes all of the moves being made to the board. revAllMoves = self.allUserMoves[:] # It gets a copy of the list of moves. revAllMoves.reverse() # It performs the opposite move of the moves in self.allUserMoves, but it also needs to do so in reverse order, that's why we need to call the reverse function. for move in revAllMoves: oppositeMove = move.opposite() self.slideAnimation(oppositeMove, '', animationSpeed=int(self.tilesize / 2)) self.makeMove(oppositeMove) if __name__ == '__main__': game = Game() # It creates an instance of our Game class. game.gameLoop() # It calls the game's game_loop function.
This section is based on the article 8 puzzle Problem using Branch And Bound by Geeks for Geeks. There are two types of searching techniques: uninformed (these algorithms do not know anything about what they are searching and where they should search for) and informed search. Heuristic search is an informed search technique. A heuristic function tells the algorithm which path will provide the solution as fast as possible.
The A* algorithm keeps a list (live nodes) that holds all the nodes that are left to be explored and it chooses the most optimal node from this list.
class PriorityQueue: """ It implements a priority queue.""" def __init__(self): self.heap =  # It inserts a new key 'k'. def push(self, k): heappush(self.heap, k) # It removes the minimum element from the queue. def pop(self): return heappop(self.heap) def empty(self): return len(self.heap)==0 class Node: """ It implements a node in the search tree.""" def __init__(self, parent, board, empty_tile_pos, cost, level, move): # It stores the parent node of the current node. self.parent = parent self.board = board # It stores the blank tile position. self.empty_tile_pos = empty_tile_pos # It stores the number of misplaced tiles. self.cost = cost # It stores the number of moves so far. self.level = level # It stores the movement that leads to this node. self.move = move # This method is necessary so that the priority queue is based on the cost. def __lt__(self, nxt): return self.cost + self.level < nxt.cost + nxt.level
This last method is wrong in the mentioned article.
When a node is chosen from the live nodes, the decision is based on its f score (), i.e., the node with the least f score is picked up and explored. A uses a combination of heuristic value (h-score = self.cost: how far the goal node is or the number of misplaced tiles) and the g-score (g-score = self.level, i.e. the number of nodes traversed from the start node to get to the current node).
def calculateCost(board, targetBoard, columns, rows): # It calculates the number of misplaced tiles. count = 0 for tileX in range(columns): for tileY in range(rows): if ((board[tileX][tileY]!=None) and (board[tileX][tileY] != targetBoard[tileX][tileY])): count += 1 return count def isValid(x, y, columns, rows): # It checks if (x, y) is a valid coordinate in the board. return x >= 0 and x < columns and y >= 0 and y < rows def makeMovesSolution(root): # Once that we have found the solution, we could access and make all the solution's movements by following the tree path. if root == None: return game.makeMove(root.move) pygame.time.wait(1000) game.makeMove(root.move) # Our game instance needs to be a global variable. game.drawGame() def newNode(board, empty_tile, new_empty_tile, level, parent, final, move=None): """ It creates a new node in the tree.""" # It makes a deep copy of our board. copyBoard = copy.deepcopy(board) # It updates the board with the new movement. copyBoard[empty_tile][empty_tile], copyBoard[new_empty_tile][new_empty_tile] = \ copyBoard[new_empty_tile][new_empty_tile], copyBoard[empty_tile][empty_tile] # It calculates the cost, i.e., the number of misplaced tiles. cost = calculateCost(copyBoard, final, len(board), len(board)) new_node = Node(parent, copyBoard, new_empty_tile, cost, level, move) return new_node def solve(board, targetBoard, emptyTile, columns, rows): pq = PriorityQueue() # It creates a priority queue to store the live nodes of the search tree. The A* Algorithm holds all the nodes that are left to be explored and it chooses the most optimal node from this list. cost = calculateCost(board, targetBoard, columns, rows) root = Node(None, board, emptyTile, cost, 0, None) pq.push(root) # It initializes our priority queue by putting the root node with the initial board on it. while not pq.empty(): # It finds the most optimal node with the least estimated cost (*). minimum = pq.pop() if minimum.cost == 0: # We have found the solution! makeMovesSolution(minimum) return # It generates all possible moves from our board. validMoves = Movement.allMovement() for move in validMoves: new_tile_pos = [ minimum.empty_tile_pos + move.coordinates(), minimum.empty_tile_pos + move.coordinates() ] if isValid(new_tile_pos, new_tile_pos, columns, rows): # If the movement is valid, then we add a new node to our list or tree of live nodes. child = newNode(minimum.board, minimum.empty_tile_pos, new_tile_pos, minimum.level + 1, minimum, targetBoard, move) pq.push(child)