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:
- In a browser, using CodeSkulptor. (See here for some awsome demos.)
- Locally using the famous pygame package along with Olivier Pirson’s SimpleGUICS2Pygame package which uses
pygameto implement the functionality of Codeskulptor’ssimpleguimodule.
Play the 8 Queens Puzzle in Python Online
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.pycontains 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.pyuses attributes and methods fromn_queens.pyalong with the tools available from thesimpleguimodule 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
http://compucademy.net/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
http://compucademy.net/blog/
"""
try:
import simplegui
collision_sound = simplegui.load_sound("http://compucademy.net/assets/buzz3x.mp3")
success_sound = simplegui.load_sound("http://compucademy.net/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("http://compucademy.net/assets/buzz3x.wav")
success_sound = simplegui.load_sound("http://compucademy.net/assets/treasure-found.wav")
queen_image = simplegui.load_image("http://compucademy.net/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()