Автор оригинала: Robin Andrews.
Восемь пазл Queens это классическая проблема, целью которой – разместить 8 королев на 8x8 Шахматная доска таким образом, что ни одна из королев не поделяется ряд, колонна или диагональю. Обсуждаемая здесь версия позволяет разведочную не только 8x8 Но произвольный размер NXN доска, и, следовательно, программа называется N Queens Отказ
Проблема очень интересна с точки зрения компьютерной науки, так как является повышение многих вопросов, связанных с представлением данных, эффективностью алгоритмии и более. Вы можете исследовать некоторые из этих проблем в Как думать как компьютерный ученый Отказ
В этой статье ориентировано на реализацию игры Python с использованием фантастического инструмента для строительства Графические пользовательские интерфейсы (Guis) называется SimpleGui Отказ SimpleGui Это минимальная база для Python для Python, которая сохраняет вещи просто, поэтому вы можете сосредоточиться на идее, которую вы пытаетесь реализовать, не увядая подробно. Это обеспечивает:
- Область холста, где вы можете рисовать фигуры и текст, и отображать изображения
- Область управления, где вы можете легко добавлять кнопки и этикетки
- Клавиатура Нажмите и мышь Click Обработка событий
- Таймеры
- Функциональность воспроизведения звука
Есть два способа, которыми вы можете использовать этот инструмент:
- В браузере, используя Кодыкульптор Отказ (См. здесь для некоторых потрясающих демо.)
- Локально используя Знаменитый пакет Pygame вместе с Olivier Pirson’s SimpleGuics2PyGame Package который использует
PygameДля реализации функциональности CodeSkulptor’sSimpleGuiмодуль.
Играть 8 пазл Queens в Python Online
Проверьте головоломку здесь
Попробуйте решить головоломку на разных размерах. Помните, что пара небольших размеров не имеет решений. Можете ли вы сказать, какие из них?
Теперь, когда вы знакомы с головоломкой, без сомнения, вы находитесь в бит, чтобы написать программу для себя или, по крайней мере, заглянуть в код, чтобы увидеть, как это работает.
Вы можете найти полный код для головоломки На моем Github Код состоит из двух файлов:
n_queens.pyСодержит атрибуты и методы для логики и представления данных игры и полностью независимы от кода GUI. Это разделение, как правило, является очень хорошей идеей при работе с GUI, как вы узнаете на опыте, если вы попытаетесь построить подобные игры, смешивающие вместе логику и игровую логику.n_queens_gui.pyиспользует атрибуты и методы отn_queens.pyНаряду с инструментами, доступными изSimpleGuiМодуль, чтобы сделать графическую версию игры.
Вы заметите, что оба файла используют объектно-ориентированное программирование. Для некоторых этого можно считать продвинутой темой. Было бы возможно написать программу с использованием классов, но на уровне сложности этой игры этот подход может быстро стать громоздкими, особенно когда речь идет о том, чтобы отслеживать Глобальные переменные Отказ
Тем не менее, есть много, что вы можете сделать с CodeSkulptor/SimpleGuics2PyGame, не используя OOP, поэтому не откладывайте, если код здесь кажется немного за пределами вашего уровня понимания. В будущих статьях я могу хорошо освещать основы программирования GUI для людей, которые еще не рисковали в мир классов и объектов.
Python внедрение классических восьми головоломки Queens
# n_queens.py
"""
N-Queens Problem using Codeskulptor/SimpleGUICS2Pygame
By Robin Andrews - info@compucademy.co.uk
https://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
https://compucademy.net/blog/
"""
try:
import simplegui
collision_sound = simplegui.load_sound("https://compucademy.net/assets/buzz3x.mp3")
success_sound = simplegui.load_sound("https://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("https://compucademy.net/assets/buzz3x.wav")
success_sound = simplegui.load_sound("https://compucademy.net/assets/treasure-found.wav")
queen_image = simplegui.load_image("https://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()