Eight Queens Puzzle in Python

Click me to play

The Eight Queens Puzzle is a classic problem whose goal is to place 8 queens on an 8x8 chessboard in such a way that none of the queens share a row, column or diagonal. The version discussed here allows exploration of not just an 8x8 but an arbitrary size nxn board, and hence the program is called N Queens.

The problem is very interesting from a Computer Science point of view, as is raises many issues to do with data representation, algorithmic efficiency and more. You can explore some of these issues in How to think like a Computer Scientist.

This article focuses on a Python implementation of the game using a fantastic tool for building graphical user interfaces (GUIs) called simplegui. simplegui is a minimal GUI framework for Python which keeps things simple so you can focus on the idea you are trying to implement without getting bogged down in detail. It provides:

  • A canvas area where you can draw shapes and text, and display images
  • A control area where you can easily add buttons and labels
  • keyboard press and mouse click event handling
  • Timers
  • Audio playback functionality

There are two ways you can use this tool:

Play the 8 Queens Puzzle in Python Online

Check out the puzzle here

Please note you may have to run the code a couple of times to get it to work in Codeskulptor. This is to do with image/sound loading times when running in a browser.

Try and solve the puzzle on different size boards. Be aware that a couple of the smaller sizes do not have solutions. Can you tell which ones?


Now that you are familiar with the puzzle, no doubt you are chomping at the bit to write the program for yourself, or at least to peek at the code to see how it works.

You can find the complete code for the puzzle on my GitHub The code is comprised of two files:

  • n_queens.py contains attributes and methods for the logic and data representation of the game, and is completely independent of the GUI code. This separation is generally a very good idea when working with GUIs, as you will learn from experience if you try and build similar games mixing together display logic and game logic.

  • n_queens_gui.py uses attributes and methods from n_queens.py along with the tools available from the simplegui module to make a graphical version of the game.

You will notice that both files use object oriented programming. For some this might be considered an advanced topic. It would be possible to write the program with using classes, but at the level of complexity of this game that approach could quickly become unwieldy, particularly when it comes to keeping track of global variables.

That said, there is a great deal that you can do with Codeskulptor/SimpleguiCS2Pygame without using OOP, so don’t be discouraged if the code here seems a bit beyond your level of understanding. In future articles I may well cover the basics of GUI programming for people who haven’t yet ventured into the world of classes and objects.

Python implementation of the classic Eight Queens Puzzle

# n_queens.py

"""
N-Queens Problem using Codeskulptor/SimpleGUICS2Pygame
By Robin Andrews - info@compucademy.co.uk
https://compucademy.co.uk/blog/
"""

try:
    import n_queens_gui
except ImportError:
    import user47_EF0SvZ5pFJwZRzj_0 as n_queens_gui

QUEEN = 1
EMPTY_SPOT = 0
BOARD_SIZE = 5


class NQueens:
    """
    This class represents the N-Queens problem.
    There is no UI, but its methods and attributes can be used by a GUI.
    """

    def __init__(self, n):
        self._size = n
        self.reset_board()

    def get_size(self):
        """
        Get size of board (square so only one value)
        """
        return self._size

    def reset_new_size(self, value):
        """
        Resets the board with new dimensions (square so only one value).
        """
        self._size = value
        self.reset_board()

    def get_board(self):
        """
        Get game board.
        """
        return self._board

    def reset_board(self):
        """
        Restores board to empty, with current dimensions.
        """
        self._board = [[EMPTY_SPOT] * self._size for _ in range(self._size)]

    def is_winning_position(self):
        """
        Checks whether all queens are placed by counting them. There should be as many as the board size.
        """
        num_queens = sum(row.count(QUEEN) for row in self._board)
        return num_queens >= self._size

    def is_queen(self, pos):
        """
        Check whether given position contains a queen.
        """
        i, j = pos
        return self._board[i][j] == QUEEN

    def place_queen(self, pos):
        """
        Add a queen (represented by 1) at a given (row, col).
        """
        if self.is_legal_move(pos):
            self._board[pos[0]][pos[1]] = QUEEN
            return True  # Return value is useful for GUI - e.g trigger sound.
        return False

    def place_queen_no_checks(self, pos):
        """
        For testing
        """
        self._board[pos[0]][pos[1]] = QUEEN

    def remove_queen(self, pos):
        """
        Set position on board to EMPTY value
        """
        self._board[pos[0]][pos[1]] = EMPTY_SPOT

    def is_legal_move(self, pos):
        """
        Check if position is on board and there are no clashes with existing queens
        """
        return self.check_row(pos[EMPTY_SPOT]) and self.check_cols(pos[1]) and self.check_diagonals(pos)

    def check_row(self, row_num):
        """
        Check a given row for collisions. Returns True if move is legal
        """
        return not QUEEN in self._board[row_num]

    def check_cols(self, pos):
        """
        Check columns and return True if move is legal, False otherwise
        """
        legal = True
        for row in self._board:
            if row[pos] == QUEEN:
                legal = False
        return legal

    def check_diagonals(self, pos):
        """
        Checks all 4 diagonals from given position in a 2d list separately, to determine
        if there is a collision with another queen.
        Returns True if move is legal, else False.
        """
        num_rows, num_cols = len(self._board), len(self._board[0])
        row_num, col_num = pos

        # Lower-right diagonal from (row_num, col_num)
        i, j = row_num, col_num  # This covers case where spot is already occupied.
        while i < num_rows and j < num_cols:
            if self._board[i][j] == QUEEN:
                return False
            i, j = i + 1, j + 1

        # Upper-left diagonal from (row_num, col_num)
        i, j = row_num - 1, col_num - 1
        while i >= 0 and j >= 0:
            if self._board[i][j] == QUEEN:
                return False
            i, j = i - 1, j - 1

        # Upper-right diagonal from (row_num, col_num)
        i, j = row_num - 1, col_num + 1
        while i >= 0 and j < num_cols:
            if self._board[i][j] == QUEEN:
                return False
            i, j = i - 1, j + 1

        # Lower-left diagonal from (row_num, col_num)
        i, j = row_num + 1, col_num - 1
        while i < num_cols and j >= 0:
            if self._board[i][j] == QUEEN:
                return False
            i, j = i + 1, j - 1

        return True

    def __str__(self):
        """
        String representation of board.
        """
        res = ""
        for row in self._board:
            res += str(row) + "\n"
        return res


n_queens_gui.run_gui(NQueens(BOARD_SIZE))
# n_queens_gui.py

"""
GUI code for the N-Queens Problem using Codeskulptor/SimpleGUICS2Pygame
By Robin Andrews - info@compucademy.co.uk
https://compucademy.co.uk/blog/
"""

try:
    import simplegui

    collision_sound = simplegui.load_sound("https://compucademy.co.uk/assets/buzz3x.mp3")
    success_sound = simplegui.load_sound("https://compucademy.co.uk/assets/treasure-found.mp3")

except ImportError:
    import SimpleGUICS2Pygame.simpleguics2pygame as simplegui

    simplegui.Frame._hide_status = True
    simplegui.Frame._keep_timers = False
    collision_sound = simplegui.load_sound("https://compucademy.co.uk/assets/buzz3x.wav")
    success_sound = simplegui.load_sound("https://compucademy.co.uk/assets/treasure-found.wav")

queen_image = simplegui.load_image("https://compucademy.co.uk/assets/queen.PNG")
queen_image_size = (queen_image.get_width(), queen_image.get_height())
FRAME_SIZE = (400, 400)
BOARD_SIZE = 20  # Rows/cols


class NQueensGUI:
    """
    GUI for N-Queens game.
    """

    def __init__(self, game):
        """
        Instantiate the GUI for N-Queens game.
        """
        # Game board
        self._game = game
        self._size = game.get_size()
        self._square_size = FRAME_SIZE[0] // self._size

        # Set up frame
        self.setup_frame()

    def setup_frame(self):
        """
        Create GUI frame and add handlers.
        """
        self._frame = simplegui.create_frame("N-Queens Game",
                                             FRAME_SIZE[0], FRAME_SIZE[1])
        self._frame.set_canvas_background('White')

        # Set handlers
        self._frame.set_draw_handler(self.draw)
        self._frame.set_mouseclick_handler(self.click)
        self._frame.add_label("Welcome to N-Queens")
        self._frame.add_label("")  # For better spacing.
        msg = "Current board size: " + str(self._size)
        self._size_label = self._frame.add_label(msg)  # For better spacing.
        self._frame.add_label("")  # For better spacing.
        self._frame.add_button("Increase board size", self.increase_board_size)

        self._frame.add_button("Decrease board size", self.decrease_board_size)
        self._frame.add_label("")  # For better spacing.
        self._frame.add_button("Reset", self.reset)
        self._frame.add_label("")  # For better spacing.
        self._label = self._frame.add_label("")

    def increase_board_size(self):
        """
        Resets game with board one size larger.
        """
        new_size = self._game.get_size() + 1
        self._game.reset_new_size(new_size)
        self._size = self._game.get_size()
        self._square_size = FRAME_SIZE[0] // self._size
        msg = "Current board size: " + str(self._size)
        self._size_label.set_text(msg)
        self.reset()

    def decrease_board_size(self):
        """
        Resets game with board one size larger.
        """
        if self._game.get_size() > 2:
            new_size = self._game.get_size() - 1
            self._game.reset_new_size(new_size)
            self._size = self._game.get_size()
            self._square_size = FRAME_SIZE[0] // self._size
            msg = "Current board size: " + str(self._size)
            self._size_label.set_text(msg)
            self.reset()

    def start(self):
        """
        Start the GUI.
        """
        self._frame.start()

    def reset(self):
        """
        Reset the board
        """
        self._game.reset_board()
        self._label.set_text("")

    def draw(self, canvas):
        """
        Draw handler for GUI.
        """
        board = self._game.get_board()
        dimension = self._size
        size = self._square_size

        # Draw the squares
        for i in range(dimension):
            for j in range(dimension):
                color = "green" if ((i % 2 == 0 and j % 2 == 0) or i % 2 == 1 and j % 2 == 1) else "red"
                points = [(j * size, i * size), ((j + 1) * size, i * size), ((j + 1) * size, (i + 1) * size),
                          (j * size, (i + 1) * size)]
                canvas.draw_polygon(points, 1, color, color)

                if board[i][j] == 1:
                    canvas.draw_image(
                        queen_image,  # The image source
                        (queen_image_size[0] // 2, queen_image_size[1] // 2),
                        # Position of the center of the source image
                        queen_image_size,  # width and height of source
                        ((j * size) + size // 2, (i * size) + size // 2),
                        # Where the center of the image should be drawn on the canvas
                        (size, size)  # Size of how the image should be drawn
                    )

    def click(self, pos):
        """
        Toggles queen if legal position. Otherwise just removes queen.
        """
        i, j = self.get_grid_from_coords(pos)
        if self._game.is_queen((i, j)):
            self._game.remove_queen((i, j))
            self._label.set_text("")
        else:
            if not self._game.place_queen((i, j)):
                collision_sound.play()
                self._label.set_text("Illegal move!")
            else:
                self._label.set_text("")

        if self._game.is_winning_position():
            success_sound.play()
            self._label.set_text("Well done. You have found a solution.")

    def get_grid_from_coords(self, position):
        """
        Given coordinates on a canvas, gets the indices of
        the grid.
        """
        pos_x, pos_y = position
        return (pos_y // self._square_size,  # row
                pos_x // self._square_size)  # col


def run_gui(game):
    """
    Instantiate and run the GUI
    """
    gui = NQueensGUI(game)
    gui.start()


Below are products related to this article, some of which may be affiliate links.

Sharing is caring!

Leave a Reply

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