How To Develop A Digital N-Puzzle Game With Python

Leave a Comment / Python / PyQt5, Python Game

N-puzzle is a kind of intellectual game. The common types of N-puzzle are 15 numbers and 8 numbers. There will be 15 squares and a space on the board of the 15 numbers n-puzzle game. The space is equal to one square in size (for moving the squares). When the 15 digits are sorted in turn and the last space is empty, it means that the challenge is successful.

1. Prerequisites.

  1. This example uses PyQt5 for design and implementation, but the most important is the algorithm, after learned the algorithm, you can use PyGame or Tkinter to implement the game also.
  2. Open a terminal and run the command pip install PyQt5 to install PyQt5. 
    $ pip install PyQt5
Collecting PyQt5
  Downloading PyQt5-5.15.4-cp36.cp37.cp38.cp39-abi3-macosx_10_13_intel.whl (7.0 MB)
     |████████████████████████████████| 7.0 MB 232 kB/s 
Collecting PyQt5-sip<13,>=12.8
  Downloading PyQt5_sip-12.9.0-cp37-cp37m-macosx_10_9_x86_64.whl (63 kB)
     |████████████████████████████████| 63 kB 795 kB/s 
Collecting PyQt5-Qt5>=5.15
  Downloading PyQt5_Qt5-5.15.2-py3-none-macosx_10_13_intel.whl (40.5 MB)
     |████████████████████████████████| 40.5 MB 173 kB/s 
Installing collected packages: PyQt5-sip, PyQt5-Qt5, PyQt5
Successfully installed PyQt5-5.15.4 PyQt5-Qt5-5.15.2 PyQt5-sip-12.9.

2. Layout Design.

  1. The n-puzzle layout design is shown in the below picture.
    n-puzzle-game-layoutn-puzzle-game-layout
  2. The gray part of the picture uses QWidget as the carrier of the entire game.
  3. The yellow part uses QGridLayout as the layout of the number square.
  4. The red part uses QLabel as the number square.

3. Algorithm Design.

  1. As shown in the figure above, the game requires a total of 15 blocks, each block represents a number.
  2. We can use a two-dimensional list to store the numbers on the block.
  3. In fact, we need to create a 4×4 list to store the numbers from 0 to 15. 0 represents the empty position.

3.1 Create And Initialize Arrays.

  1. Create an array with a length of 16, and store 0~15 in the corresponding position; disrupt the order. 
    import random

# A two-dimensional array used to store location information.
blocks = []

# Generate a random array, 0 represents an empty position.
arr = range(16)
numbers = random.sample(arr, 16)

for row in range(4):
    blocks.append([])
    for column in range(4):
        blocks[row].append(numbers[row*4 + column])

# Print results.
for i in range(4):
    print(blocks[i])

[out]
[2, 5, 7, 9]
[11, 8, 4, 12]
[6, 13, 10, 15]
[1, 14, 0, 3]
[Finished in 0.1s]

3.2 Move Square Algorithm.

  1. If the position of the number before moving is as shown on the left, then when the left arrow is pressed, it will become as shown on the right.
    n-puzzle-algorithm
  2. You can see that the numbers in the two positions (1, 2) and (1, 3) are swapped, that is, 0 and 8 are swapped.
  3. If you press the left arrow again as shown on the right, then all the numbers will not change, because there are no more numbers to the right of the number 0 ( the white square ).
  4. If the position of the number 0 is (row, column), and column≠3, after pressing the left arrow, the arrays at positions (row, column) and (row, column+1) are swapped.
  5. If the position of the number 0 is (row, column), and column≠0, after pressing the right arrow, the array element values at the positions of (row, column) and (row, column-1) are exchanged.
  6. If the number 0 is located in (row, column) and row ≠ 3, then the array elements in (row, column) and (row + 1, column) are exchanged after pressing the up arrow.
  7. If the position of the number 0 is (row, column), and row ≠ 0, then after pressing the down arrow, the array elements in (row, column) and (row-1, column) positions are exchanged.
  8. Encapsulate the move square algorithm into a function as follows. 
    # zero_row represents the row subscript of the two-dimensional array where the number 0 is located, zero_column represents the column subscript of the two-dimensional array where the number 0 is located
def move(direction):
    if(direction == 'UP'): # Move up
        if zero_row != 3:
            blocks[zero_row][zero_column] = blocks[zero_row + 1][zero_column]
            blocks[zero_row + 1][zero_column] = 0
            zero_row += 1
    if(direction == 'DOWN'): # Move down.
        if zero_row != 0:
            blocks[zero_row][zero_column] = blocks[zero_row - 1][zero_column]
            blocks[zero_row - 1][zero_column] = 0
            zero_row -= 1
    if(direction == 'LEFT'): # Move to left.
        if zero_column != 3:
            blocks[zero_row][zero_column] = blocks[zero_row][zero_column + 1]
            blocks[zero_row][zero_column + 1] = 0
            zero_column += 1
    if(direction == 'RIGHT'): # Move to right
        if zero_column != 0:
            blocks[zero_row][zero_column] = blocks[zero_row][zero_column - 1]
            blocks[zero_row][zero_column - 1] = 0
            zero_column -= 1

3.3 Victory Detection Algorithm.

  1. Detecting victory is very simple: if the first 15 positions saved the related correct numbers, and the last one is 0 then it means you win.
  2. However, in order to avoid unnecessary calculation, we first check whether the last one is 0. If it is not 0, there is no need to compare others.
  3. Below is the python code that implements the victory detection function. 
    # Check whether the test is complete or not.
def checkResult():
        # First check whether the bottom right corner square is 0
        if blocks[3][3] != 0:
            return False

        for row in range(4):
            for column in range(4):
            	# Below condition means that the square block value of the bottom right corner is 0 theb pass
                if row == 3 and column == 3:
                    pass
                # Check whether the square block number is correct number.
                elif blocks[row][column] != row * 4 + column + 1:
                    return False

        return True

4. Implementation.

4.1 Program Structure Creation.

  1. Create QWidget as the container of the whole game. 
    import sys
from PyQt5.QtWidgets import QWidget, QApplication

class NumberPuzzle(QWidget):
    """ N-puzzle game class """
    def __init__(self):
        super().__init__()
        self.initUI()

    def initUI(self):
        # Set game container frame width and height.
        self.setFixedSize(400, 400)
        # Set game window title.
        self.setWindowTitle('N-Puzzle Game')
        # Set the background color.
        self.setStyleSheet("background-color:gray;")
        self.show()

if __name__ == '__main__':
    app = QApplication(sys.argv)
    ex = NumberPuzzle()
    sys.exit(app.exec_())

4.2 Number Block Implementation.

  1. As mentioned earlier, we use a two-dimensional array to store 0 ~ 16 numbers. Now, we need to convert it into a number block and create a class to represent a number block.
  2. This class inherits from the QLabel class. The class initialization requires passing in a number parameter, the parameter is the number displayed on the number block. 
    class Block(QLabel):
    """ Number block """
    def __init__(self, number):
        super().__init__()

        self.number = number
        self.setFixedSize(80, 80)

        # Set the number font.
        font = QFont()
        font.setPointSize(30)
        font.setBold(True)
        self.setFont(font)

        # Set text color.
        pa = QPalette()
        pa.setColor(QPalette.WindowText, Qt.white)
        self.setPalette(pa)

        # Set the text alignment.
        self.setAlignment(Qt.AlignCenter)

        # Set background color, filleted corner and text content.
        if self.number == 0:
            self.setStyleSheet("background-color:white;border-radius:10px;")
        else:
            self.setStyleSheet("background-color:red;border-radius:10px;")
            self.setText(str(self.number))

4.3 Convert Numbers To Blocks To Add To Layout.

  1. The layout uses QGridLayout to create a 4×4 self.gltMain, and adds 16 blocks to self.gltMain. 
    def updatePanel(self):
    for row in range(4):
        for column in range(4):
            # Create 16 block objects and add the block object to the gltMain layout object.
            self.gltMain.addWidget(Block(self.blocks[row][column]), row, column)
   
    # Set the container layout.
    self.setLayout(self.gltMain)

4.4 Initialize Layout.

  1. Initializing the layout includes generating random data and converting numbers into blocks to add to the layout. 
    # Initialize layout
    def onInit(self):
        # Generate a random array, 0 for the empty position.
        arr = range(16)
        self.numbers = random.sample(arr, 16)

        # Add a number block to the layout.
        for row in range(4):
            self.blocks.append([])
            for column in range(4):
                temp = self.numbers[row * 4 + column]

                if temp == 0:
                    self.zero_row = row
                    self.zero_column = column
                self.blocks[row].append(temp)
                self.gltMain.addWidget(Block(temp), row, column)

4.5 Key Press Detection.

  1. QWidget has a keyPressEvent event handle function. We just need to overwrite the method.
  2. After the program detects that the key is pressed, it checks whether the key value is “↑ ↓ ← →” or “WSAD”, and makes the corresponding move, then refreshes the layout after a move.
  3. Finally, check whether the challenge is successful. If the challenge is successful, a prompt box will pop up. If you click the OK button, the game will restart. 
    # Detect key press event.
def keyPressEvent(self, event):
    key = event.key()
    if(key == Qt.Key_Up or key == Qt.Key_W):
        self.move(Direction.UP)
    if(key == Qt.Key_Down or key == Qt.Key_S):
        self.move(Direction.DOWN)
    if(key == Qt.Key_Left or key == Qt.Key_A):
        self.move(Direction.LEFT)
    if(key == Qt.Key_Right or key == Qt.Key_D):
        self.move(Direction.RIGHT)
    self.updatePanel()
    if self.checkResult():
        if QMessageBox.Ok == QMessageBox.information(self, 'Challenge Results', 'Congratulations on completing the challenge!'):
            self.onInit()

4.6 Find The Bugs.

  1. So far, all the functional modules are introduced. Don’t worry about the full source code. Let’s run the program to see if there are bugs.
  2. After playing a few games, I found that not all the games can be restored.
  3. If the position of 14 and 15 blocks is reversed, it can’t be restored in any case. This situation is random. Why?
  4. Do you remember how our two-dimensional array is generated? randomly generated, that is, it may be too random to restore.
  5. How to avoid this? When initializing the array, all the positions are correct numbers, and then use the move function to scramble it.
  6. Since each function module has been written as a method separately, we only need to modify the onInit method.
  7. First, create a sequential array, and save [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0] in the array, and then convert them to two-dimensional blocks array, and then move 500 times, and finally add them to the layout. 
    # Initialize layout
def onInit(self):
    # Generate sequential arrays.
    self.numbers = list(range(1, 16))
    self.numbers.append(0)

    # Adds numbers to a two-dimensional array
    for row in range(4):
        self.blocks.append([])
        for column in range(4):
            temp = self.numbers[row * 4 + column]

            if temp == 0:
                self.zero_row = row
                self.zero_column = column
            self.blocks[row].append(temp)

    # Scrambling the array.
    for i in range(500):
        random_num = random.randint(0, 3)
        self.move(Direction(random_num))

    self.updatePanel()

5. The Full Source Code.

  1. Below is the full source code for this example. 
    import sys
import random
from enum import IntEnum
from PyQt5.QtWidgets import QLabel, QWidget, QApplication, QGridLayout, QMessageBox
from PyQt5.QtGui import QFont, QPalette
from PyQt5.QtCore import Qt

# Using enumeration class to represent direction.
class Direction(IntEnum):
    UP = 0
    DOWN = 1
    LEFT = 2
    RIGHT = 3


class NumberNPuzzle(QWidget):
    """ N-puzzle main program """
    def __init__(self):
        super().__init__()
        self.blocks = []
        self.zero_row = 0
        self.zero_column = 0
        self.gltMain = QGridLayout()

        self.initUI()

    def initUI(self):      
        # Set number block spacing
        self.gltMain.setSpacing(10)

        self.onInit()

        # Set layout.
        self.setLayout(self.gltMain)
        # Set window width and height.
        self.setFixedSize(400, 400)
        # Set window title.
        self.setWindowTitle('N-puzzle Game.')
        # Set window background color.
        self.setStyleSheet("background-color:gray;")
        self.show()

    # Initialize layout.
    def onInit(self):
        # Create sequential array.
        self.numbers = list(range(1, 16))
        self.numbers.append(0)

        # Add number to the two-dimensional array.
        for row in range(4):
            self.blocks.append([])
            for column in range(4):
                temp = self.numbers[row * 4 + column]

                if temp == 0:
                    self.zero_row = row
                    self.zero_column = column
                self.blocks[row].append(temp)

        # Scrambling the array.
        for i in range(500):
            random_num = random.randint(0, 3)
            self.move(Direction(random_num))

        self.updatePanel()

    # Detect key press event.
    def keyPressEvent(self, event):
        key = event.key()
        if(key == Qt.Key_Up or key == Qt.Key_W):
            self.move(Direction.UP)
        if(key == Qt.Key_Down or key == Qt.Key_S):
            self.move(Direction.DOWN)
        if(key == Qt.Key_Left or key == Qt.Key_A):
            self.move(Direction.LEFT)
        if(key == Qt.Key_Right or key == Qt.Key_D):
            self.move(Direction.RIGHT)
        self.updatePanel()
        if self.checkResult():
            if QMessageBox.Ok == QMessageBox.information(self, 'Challenge Results', 'Congratulations on completing the challenge!'):
                self.onInit()

    # Block moving algorithm.
    def move(self, direction):
        if(direction == Direction.UP): # Move up.
            if self.zero_row != 3:
                self.blocks[self.zero_row][self.zero_column] = self.blocks[self.zero_row + 1][self.zero_column]
                self.blocks[self.zero_row + 1][self.zero_column] = 0
                self.zero_row += 1
        if(direction == Direction.DOWN): # Move down.
            if self.zero_row != 0:
                self.blocks[self.zero_row][self.zero_column] = self.blocks[self.zero_row - 1][self.zero_column]
                self.blocks[self.zero_row - 1][self.zero_column] = 0
                self.zero_row -= 1
        if(direction == Direction.LEFT): # Move left.
            if self.zero_column != 3:
                self.blocks[self.zero_row][self.zero_column] = self.blocks[self.zero_row][self.zero_column + 1]
                self.blocks[self.zero_row][self.zero_column + 1] = 0
                self.zero_column += 1
        if(direction == Direction.RIGHT): # Move right.
            if self.zero_column != 0:
                self.blocks[self.zero_row][self.zero_column] = self.blocks[self.zero_row][self.zero_column - 1]
                self.blocks[self.zero_row][self.zero_column - 1] = 0
                self.zero_column -= 1

    def updatePanel(self):
        for row in range(4):
            for column in range(4):
                self.gltMain.addWidget(Block(self.blocks[row][column]), row, column)

        self.setLayout(self.gltMain)

    # Check whether the challenge is completed or not.
    def checkResult(self):
        # First check whether the block value in the bottom right corner is 0。
        if self.blocks[3][3] != 0:
            return False

        for row in range(4):
            for column in range(4):
                # The value of the block in the bottom right corner is 0, pass.
                if row == 3 and column == 3:
                    pass
                # Check whether the square block number is correct number.
                elif self.blocks[row][column] != row * 4 + column + 1:
                    return False

        return True

class Block(QLabel):
    """ Number block """

    def __init__(self, number):
        super().__init__()

        self.number = number
        self.setFixedSize(80, 80)

        # Set text font.
        font = QFont()
        font.setPointSize(30)
        font.setBold(True)
        self.setFont(font)

        # Set text color.
        pa = QPalette()
        pa.setColor(QPalette.WindowText, Qt.white)
        self.setPalette(pa)

        # Set text alignment.
        self.setAlignment(Qt.AlignCenter)

        # Set background color, filleted corner and text content。
        if self.number == 0:
            self.setStyleSheet("background-color:white;border-radius:10px;")
        else:
            self.setStyleSheet("background-color:red;border-radius:10px;")
            self.setText(str(self.number))


if __name__ == '__main__':
    app = QApplication(sys.argv)
    ex = NumberHuaRong()
    sys.exit(app.exec_())

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.