Есть ли постоянное время для решения проблемы безопасной королевы? (Python) - PullRequest
Новая
       9

Есть ли постоянное время для решения проблемы безопасной королевы? (Python)

0 голосов
/ 16 июня 2019

Я работаю над проблемой безопасной королевы, и мне любопытно, есть ли постоянное время для решения вопроса.

Safe Queens

В шахматах ферзь - самая мощная фигура, так как она может перемещать любое количество незанятых квадратов по прямой вдоль столбцов (называемых «файлами»), рядов (называемых «рангами») и диагоналей. Однако на доске можно разместить 8 королев, чтобы ни одна из них не угрожала другой.

В этом задании мы читаем ввод из 8 позиций в стандартной алгебраической записи (файлы «a» - «h» и ранги «1» - «8»). Наша цель - с помощью функции safe_queens определить, все ли королевы защищены друг от друга, то есть ни одна из них не должна иметь общий файл, ранг или диагональ. Если все они безопасны, функция должна вывести «YES», в противном случае она должна вывести «NO».

Пример: Входные данные: a5 b3 c1 d7 e2 f8 g6 h4

(примерные позиции ввода показаны на плате ниже)

Выход: ДА

В этом примере выводится «YES», потому что ни одна королева не имеет общего файла, ранга или диагонали. Если бы a5 был a4, он бы вывел «NO», потому что две крайние левые королевы были бы на одной диагонали.

Я считаю, что вы можете преобразовать решение в постоянное время, отслеживая посещенные квадраты и проверяя вывод диагоналей, но я не уверен на 100%. 

def safe_queens():
  positions = [input() for _ in range(8)]

  # if there isn't exactly one queen per file and per rank then return 'NO'
  if (len({i[0] for i in positions}) != 8) or (
      len({i[1] for i in positions}) != 8):
       return 'NO'

  # to check diagonals compare difference between each queen combinations
  # rank values and file values, adjust for both diagonal directions by 
  # using abs()
  for p in range(8):
    for q in range(p+1, 8):
      if (abs(ord(positions[p][0]) - ord(positions[q][0]))) == (
          abs(int(positions[p][1]) - int(positions[q][1]))):
        return 'NO'
  return 'YES'

Ссылка на ноутбук colab с описанием проблемы и моим решением: https://colab.research.google.com/drive/1sJN6KnQ0yN-E_Uj6fAgQCNdOO7rcif8G

Решение выше O (n ^ 2), но я ищу решение с постоянным временем. Спасибо!

1 Ответ

0 голосов
/ 16 июня 2019

Просто сделайте то же самое для диагоналей, что и для файлов и рангов: сделайте набор всех диагональных чисел и проверьте длину набора. Вы можете нумеровать диагонали так: 

diagonals1 = {ord(position[0]) - int(position[1]) for position in positions}
if len(diagonals1) < 8:
    return 'NO'

diagonals2 = {ord(position[0]) + int(position[1]) for position in positions}
if len(diagonals2) < 8:
    return 'NO'
...