Построение графа для задачи о ходе коня¶
Чтобы представить задачу о ходе коня в виде графа, воспользуемся следующими двумя соображениями: каждая клетка на доске будет узлом, а каждый возможный ход фигуры - ребром. Рисунок 1 иллюстрирует соответствие доступных фигуре ходов рёбрам графа.
Чтобы построить полный граф для доски \(n \times n\), мы используем код на Python, показанный в листинге 1. Функция knightGraph совершает один проход через всю доску. В каждой из клеток она вызывает вспомогательную функцию genLegalMoves, чтобы создать список возможных ходов для этой позиции. Все они конвертируются в рёбра графа. Другая вспомогательная функция posToNodeId преобразует положение фигуры на доске в терминах столбца и строки в линейный номер вершины, аналогичный номерам, показанным на рисунке 1.
Листинг 1
from pythonds.graphs import Graph
def knightGraph(bdSize):
ktGraph = Graph()
for row in range(bdSize):
for col in range(bdSize):
nodeId = posToNodeId(row,col,bdSize)
newPositions = genLegalMoves(row,col,bdSize)
for e in newPositions:
nid = posToNodeId(e[0],e[1],bdSize)
ktGraph.addEdge(nodeId,nid)
return ktGraph
Функция genLegalMoves (листинг 2) принимает позицию коня на доске и генерирует восемь доступных ходов. Вспомогательная функция legalCoord (листинг 2) проверяет, что сгенерированный ход всё ещё лежит на доске.
Листинг 2
def genLegalMoves(x,y,bdSize):
newMoves = []
moveOffsets = [(-1,-2),(-1,2),(-2,-1),(-2,1),
( 1,-2),( 1,2),( 2,-1),( 2,1)]
for i in moveOffsets:
newX = x + i[0]
newY = y + i[1]
if legalCoord(newX,bdSize) and \
legalCoord(newY,bdSize):
newMoves.append((newX,newY))
return newMoves
def legalCoord(x,bdSize):
if x >= 0 and x < bdSize:
return True
else:
return False
На рисунке 2 показан полный граф возможных ходов для доски \(8 \times 8\). Это ровно 336 рёбер. Обратите внимание: вершины, на которые отображаются клетки на краю доски, имеют меньше связей (возможных ходов), чем вершины из середины. Мы снова видим, насколько граф разрежен. Если бы он был полностью связан, то имел бы 4 096 рёбер. Но поскольку их в нём всего лишь 336, то матрица смежности будет заполнена всего на 8.2%