Какова интуиция за шахматной доской, охватывающей рекурсивный алгоритм, и как можно лучше сформулировать такой алгоритм?
Возможно, вы слышали о классической головоломке с шахматной доской. Как вы покрываете шахматную доску, у которой отсутствует один угловой квадрат, используя L-образные плитки?
Существует рекурсивный подход к этому, как объяснено в книге "Освоение основных алгоритмов Python на языке Python".
Идея состоит в том, чтобы разделить доску на 4 меньших квадрата, затем поместить L-образную плитку в центр большей доски, эффективно создав 4 маленьких квадрата с отсутствующей одной плиткой, и продолжить через рекурсию.
Концептуально это легко понять, но мне очень трудно думать о реализации. Вот одно решение для реализации -
def cover(board, lab=1, top=0, left=0, side=None):
if side is None: side = len(board)
# Side length
s = side // 2
# Offsets for outer/inner squares of subboards
offsets = ((0, -1), (side-1, 0))
for dy_outer, dy_inner in offsets:
for dx_outer, dx_inner in offsets:
# If the outer corner is not set...
if not board[top+dy_outer][left+dx_outer]:
# ... label the inner corner:
board[top+s+dy_inner][left+s+dx_inner] = lab
# Next label:
lab += 1
if s > 1:
for dy in [0, s]:
for dx in [0, s]:
# Recursive calls, if s is at least 2:
lab = cover(board, lab, top+dy, left+dx, s)
# Return the next available label:
return lab
Чтобы запустить код, вы получите следующее
board = [[0]*8 for i in range(8)]
board[7][7] = -1
cover(board)
for row in board:
print((" %2i"*8)%tuple(row))
3 3 4 4 8 8 9 9
3 2 2 4 8 7 7 9
5 2 6 6 10 10 7 11
5 5 6 1 1 10 11 11
13 13 14 1 18 18 19 19
13 12 14 14 18 17 17 19
15 12 12 16 20 17 21 21
15 15 16 16 20 20 21 -1
Мне потребовалось некоторое время, чтобы понять эту реализацию. Я не уверен, что я даже полностью понимаю это, особенно мысль за линией смещений. Может кто-нибудь попытаться объяснить реализацию кратко? Как развить интуицию, чтобы думать о решении проблем такого типа? Я нашел решение очень умным, особенно настройку линии смещений, как они сделали. Если бы кто-то мог помочь мне понять это и, возможно, предложения о том, как стать лучше, я был бы очень признателен.
Спасибо!
1 ответ
Как развить интуицию, чтобы думать о решении проблем такого типа?
Решение очень умное и довольно специфичное для проблемы, но оно также является примером более общей стратегии решения проблем, называемой "разделяй и властвуй". Вместо того, чтобы атаковать проблему полностью, создайте меньшие версии и попытайтесь решить их, например. с карандашом и бумагой, методом проб и ошибок. Посмотрите, есть ли чему поучиться из этих решений.
В этом случае решение версии 2x2 тривиально, но, тем не менее, интересно отметить, что оно имеет решение.
Ниже приведено решение 4х4. Теперь, просто посмотрев на него некоторое время, можно распознать связь с делом 2х2. Каждый квадрант в основном представляет собой случай 2х2.
3 3 4 4
3 2 2 4
5 2 6 6
5 5 6 -1
Я нашел решение очень умным, особенно настройку линии смещений, как они сделали. Если бы кто-то мог помочь мне понять это [...]
Возможно, это будет легче понять, если развернуть вложенные циклы и заменить переменные цикла их значениями в том виде, в каком они отображаются в offsets, Тогда у вас есть четыре оператора if вместо цикла. Каждый оператор устанавливает один из четырех центральных квадратов, если не установлен соответствующий квадрат в углу доски.
#top left
if not board[top][left]:
board[top+s-1][left+s-1] = lab
#top right
if not board[top][left+side-1]:
board[top+s-1][left+s] = lab
#bottom left
if not board[top+side-1][left]:
board[top+s][left+s-1] = lab
#bottom right
if not board[top+side-1][left+side-1]:
board[top+s][left+s] = lab
Автор, возможно, даже начал с того, что написал это так, но заметил, что код повторяется, и вместо этого создал цикл. offsets Переменная представляет различия между утверждениями.