Программирование игр и головоломок

Но при 1 ? k ? 8, 1 ? i ? 8 сумма меняется от 2 до 16, а разность — от ?7 до 7. Чтобы остаться в промежутке от 1 до 13 (чего некоторые языки просто требуют), нужно вычитать 1 из суммы и прибавлять 8 к разности, Тогда диагонали, проходящие через k, i, суть дп [k + i ? 1] и дм [k ? i + 8].

Операция «искать первое свободное поле…» реализуется маленьким циклом в программе. Вот — на псевдоязыке, используемом в этой книге и близком к Бейсику, LSE и языку Паскаль, — что из всего этого получается:

  ТАБЛИЦА с[8], ст[8], дп[15], дм[15]
    k := 1
  ДЛЯ j := 1 ДО 8 ВЫПОЛНЯТЬ
    ст[j] = 0
  ВЕРНУТЬСЯ
  ДЛЯ j := 1 ДО 15 ВЫПОЛНЯТЬ
    дп[j] := 0; дм := 0
  ВЕРНУТЬСЯ
С c[k] : = 0
И i := c[k] + 1
  ВЫПОЛНЯТЬ
    ЕСЛИ i = 9 ТО КОНЧЕНО
    КОНЕЦ_ЕСЛИ
    ЕСЛИ ст[i] = 0 И дп[k + i ? 1] = 0 И
      дм[k ? i + 8] = 0 ТО КОНЧЕНО
    КОНЕЦ_ЕСЛИ
    i := i + 1
  ВЕРНУТЬСЯ
  ЕСЛИ i = 9 ТО ПЕРЕЙТИ К СБ КОНЕЦ_ЕСЛИ
СОК c[k] := i
  ЕСЛИ k = 8 ТО ВЫВЕСТИ c;
  ПЕРЕЙТИ К СБ КОНЕЦ_ЕСЛИ
  ст[i] := k; дп[k + i ? 1] := k;
  дм[k ? i + 8] := k; k := k + 1
  ПЕРЕЙТИ К С
СБ k := k ? 1
  ЕСЛИ k = 0 ТО ПЕРЕЙТИ К Я КОНЕЦ_ЕСЛИ
  i := c[k]; ст [i] := 0; дп[k + i ? 1] := 0;
  дм[k ? i + 8] := 0
  ПЕРЕЙТИ К И
Я КОНЕЦ_РАБОТЫ

У вас теперь есть все, что только может быть вам нужно для того, чтобы это заработало на вашем компьютере.

Что касается симметрии, то вот указание. Эта программа заставляет первого ферзя пробежать всю первую строку. Но достаточно, чтобы он пробежал половину, а затем дополнить результат по симметрии. Остановить пробег, когда c[1] достигает значения 4, нелегко, но легко начать пробег с цифры 5. Ну, уж теперь-то я сказал вам достаточно…

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

Головоломка 21.

Я не вижу способа взяться за эту задачу, существенно отличного от предыдущего. Нужно найти нижнюю границу для числа ферзей. На пустой шахматной доске ферзь может блокировать 28 полей. Следовательно, нужно по крайней мере 3 ферзя, чтобы блокировать доску. Их нужно не больше 7: если вы уже пытались вручную поставить 8 ферзей, то вы должны были убедиться, что шахматная доска часто блокируется до того, как мы смогли поставить восьмого ферзя. Точно так же вероятно, что 6 ферзей должно хватить. Поэтому нужно исследовать отрезок от 3 до 6 ферзей.

Нет никакой уверенности в том, что эти ферзи не должны бить друг друга. Конечно, на шахматной доске есть поля, которые бьются по крайней мере двумя ферзями. Но нужно иметь возможность ограничить поиск решениями, для которых никакие два ферзя не бьют друг друга, или, может быть, немного проще — решениями, для которых никакие два ферзя не стоят на одной строке.

Вы размещаете k ферзей. Вы пробегаете шахматную доску в поисках свободного поля. Если его нет, то у вас есть решение. Если свободное поле есть, то вы ставите туда ферзя и начинаете поиск сначала. Бесполезно пробегать строки, на которых ферзь уже есть, Это соображение ускоряет проверку.

Головоломка 22.

Ничего трудного. Нужно перепробовать все комбинации, Берем какую-нибудь шашку домино в качестве начальной шашки цепочки и пробуем шашки одну за другой. Они вынимаются из хранилища, а затем отыскивается первая шашка, которую можно связать с данной, тем же способом, которым отыскивалось первое свободное поле на следующей строке.

Тщательно выберите ваше представление шашек домино.

Головоломка 23.

И на этот раз программирование достаточно просто. Вы задаете крайние члены последовательности:

a₁ = 0, a_n = k.

С помощью уже проведенного рассуждения вы можете зафиксировать

a₂ = 1, a_n?1 = k ? 2.

Затем вы размещаете следующие члены в интервале (2, k ? 3), например, уплотняя их к началу:

a₃ = 2, a₄ = 3, a₅ = 4…

Вы образуете разности и, если они дают слишком много повторений (вы можете узнать его, не вычисляя всех разностей, что ускоряет тест), вы увеличиваете последний подвижный член a_n?2 и, когда добираетесь до конца, увеличиваете предпоследний подвижный член, затем берете a_n?2 = a_n?3 + 1 и продолжаете дальше.

Для последовательности с 5 членами есть только один подлежащий размещению член, и все идет очень быстро. Но сложность растет с ростом n очень круто. Если при 5 членах есть только один подлежащий размещению член, то с n = 6 их уже два и задача квадратична. Для произвольного n число подлежащих испытанию случаев имеет порядок n^n?4.