Excel и задача о восьми ферзях

2.1. Минимум автоматизации

При решении задачи о восьми ферзях в Эксель можно начать с того, что использовать Эксель просто как холст, как тетрадку, используя минимум из всех возможностей Эксель.

Вначале создадим нужный файл, который будет отвечать за решение этой задачи. Это должен быть не простой файл, а файл с поддержкой макросов. Это значит, что у этого файла будет расширение: «xlsm». Перед расширением можно задать имя: «Восемь_ферзей».

Далее можно изменить ширину столбцов. Рекомендуемая ширина – около 2,6 условных единиц. Это необходимо сделать для того, чтобы каждая клетка Эксель была больше похожа на квадрат, чем на простой прямоугольник. Ведь каждая ячейка Эксель будет символизировать клетку шахматной доски, а клетка доски – это именно квадрат.

Итак, начнем с составления первого варианта решения задачи.

Выделим квадрат размером 8 на 8 клеток Эксель. Этот квадрат будет символизировать шахматную доску (рисунок 2.1).

Рисунок 2.1.

Мы добавили внешние границы квадрату, который символизирует шахматную доску. Ячейка A1 Эксель (левая верхняя ячейка рисунка) будет означать поле a8 шахматной доски (тоже левое верхнее поле).

Теперь можно начать составлять возможные позиции, при которых на доске будет находиться 8 ферзей, не угрожающих друг другу.

Начнем с того, что предположим, что в первой позиции в верхней строке ферзь будет в первом (левом) столбце. Допустим, что цифра 1 будет символизировать ферзя, а какой-то символ (например, буква «х» будет означать те клетки, в которых ферзя точно не может быть.

Покажем эту ситуацию на рисунке 2.2.

Рисунок 2.2.

Далее продолжим заполнять наш квадрат единицами. Следующая строка – вторая строка сверху. Ячейки A2 и B2 Эксель не могут содержать единицу, так как там уже находятся символы «х». Это значит, что самый первый столбец, где можно предполагать наличие единицы в строке 2 Эксель, – это столбец C Эксель, ячейка C2. Поставим там единицу, а также добавим символы «х» везде, где это необходимо. Покажем ситуацию на рисунке 2.3.

Рисунок 2.3.

Затем заполняем строку 3. Здесь первые 4 ячейки уже заняты. Ближайшее свободное место, где можно разместить единицу, – это ячейка E3 Эксель. Поместим туда единицу, а также добавим символы «х» везде, где это будет необходимо. Покажем результат на рисунке 2.4.

Рисунок 2.4.

Затем надо заполнить строку 4 Эксель.

Но здесь можно просто применить логику. В строке 4 пока всего 3 свободные клетки. Но если мы поместим единицу в ячейку B4 или H4, то это будет значить, что для столбцов F и G не осталось ни одного варианта, которые позволили бы разместить в этих столбцах два ферзя, поскольку эти варианты не оставляют две свободные клетки в этих столбцах так, чтобы в этих клетках можно было разместить 2 ферзя, не угрожающих друг другу.

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

Следовательно, можно прийти к выводу: в ситуации, изображенной на рисунке 2.3, в ячейке E3 размещать единицу нельзя, можно попробовать другие варианты. Начнем с варианта, когда единица будет в ячейке F3 (рисунок 2.5).

Рисунок 2.5.

Попробуем поместить единицу в ячейку B4 (рисунок 2.6):

Рисунок 2.6.

Здесь тоже можно рассуждать логически. В строке 5 Эксель есть только одно свободное место, но если туда поместить единицу, тогда в столбце H не останется вариантов для единицы. Это значит, что при ситуации на рисунке 2.5 в ячейку B4 нельзя поместить единицу. Попробуем найти другое место для единицы в строке 4 после той ситуации, что показана на рисунке 2.5. Между прочим, остается всего один вариант: нужно поместить единицу в ячейку H4. Покажем сложившуюся ситуацию на рисунке 2.7.

Рисунок 2.7.

Если проанализировать эту ситуацию, то станет очевидным, что при такой расстановке единиц (ферзей) правильный ответ на задачу получить нельзя, потому что единственная свободная ячейка в столбце G закрывает все варианты для столбца E.

Если присваивать код каждой позиции, тогда этот код будет представлять собой 8-значное число. Первая цифра этого числа будет показывать, в каком столбце находится единица в первой (верхней) строке, вторая цифра – в каком столбце будет единица во второй сверху строке, и так далее.

Все возможные варианты нужно перебирать таким образом, чтобы каждый следующий вариант был чуть больше предыдущего, чтобы разница в числах, образованных кодами этих вариантов, была минимальной. В принципе, мы именно так и начали подбирать варианты: начали с того, что предположили, что первая единица будет в строке 1 и в столбце 1, а вторая – в строке 2 и столбце 3, следовательно, сам код начинался с сочетаний цифр 13…

Итак, только что мы перебрали несколько вариантов расстановки ферзей, и все они показали свою несостоятельность, ошибочность, отсутствие правильного решения. Хотя мы еще разобрали далеко не все возможные варианты, но если вспомнить о кодировке, которую мы присвоили всем возможным вариантам, то уже сейчас можно смело сказать: все варианты кода, которые начинаются с сочетаний цифр 135… и 136…, оказались ошибочными.

Теперь можно начать проверку варианта 137… Это значит, что в первой строке будет единица в столбце 1, во второй строке – в столбце 3, в третьей строке – в столбце 7.

Покажем этот вариант на рисунке 2.8, добавим на этом рисунке символы «х» везде, где это необходимо.

Рисунок 2.8.

К сожалению, если чуть-чуть внимательней присмотреться к тому варианту, что показан на рисунке 2.8, можно его сразу же «забраковать»: ведь в строке 4 есть только две свободные клетки. Наличие единицы в ячейке B4 сделает отсутствие решений для столбцов D и E, поскольку там останутся только 4 пустые клетки, и они будут настолько близко друг к другу, что в них может расположиться только одна единица, и это значит что для второй единицы нет места. А если мы поставим единицу в ячейке D4, тогда похожая безвыходная ситуация будет создана для столбцов E и F, там останутся только 3 пустые клетки, в них нельзя разместить две единицы по всем ранее оговоренным правилам.