8 ферзей

Сегодня мы порешаем логические задачи с помощью HiAsm. Покажу я только одну, но схемы помогут лучше понять работу с компонентами, а также логику работы в HiAsm.

Итак, задача называется "8 ферзей". А звучит она очень просто: как расположить на шахматной доске 8 ферзей так, чтобы ни один из них не находился под угрозой других? Да ещё разными способами.

Задача на первый взгляд простая (кому-то так покажется). Все знают, как ходит ферзь (по вертикали, горизонтали и двум диагоналям на любое количество клеток). Быстро нарисуют 64 клетки и начнут отмечать точками ферзей, зачёркивать клетки, на которые распространяется угроза ферзей и на свободные клетки ставить новых ферзей.

Да только после отметки всех клеток 8 ферзей получится у наиболее везучих. Обычно бывает 7 или даже всего 6 ферзей. Что уж там говорить о разных вариантах!

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

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



С виду - сложно, много связей. Но всё очень просто. Программа рисует 7 вертикальных и 7 горизонтальных линий. Делается это в цикле, где каждый раз сначала прибавляется число 47 к предыдущему результату. Затем сначала рисуется вертикальная линия, потом - горизонтальная. Смотрите: у вертикальных координаты Y постоянны, а у горизонтальных - X.

А дальше нужно делать логику программы. Вот её суть.
1. Генерируем случайное число, чтобы выбрать клетку.
2. Проверяем, не занята ли она. Если занята, то генерируем новое, а если нет - ставим на неё ферзя.
3. Зная, как он ходит, помечаем клетки, оказавшиеся под угрозой. Они также являются занятыми, и поставить на них ферзя должно быть невозможно.
4. Повторяем эти действия, пока вся доска не окажется занятой.
5. Считает количество ферзей. Если меньше 8 - начинаем заново.


Но в каких пределах генерировать число и как узнать потом номер клетки, ведь доска-то двухмерная? Мы используем матрицу, которая тоже двумерна. А числа будем генерировать два: для вертикали и горизонтали. Только договоримся так: свободные ячейки матрицы у нас будут иметь значение 0, занятые ферзями - 1, а те, на которые распространяется угроза ферзя - 2. Когда мы будем определять это, то обязательно будем записывать в матрицу значения.



Всё рисование я запихнул во вложенную схему, чтобы оно нам не мешало. Заодно я также сделал перед прорисовкой очищение картинки (дальше нам это понадобится) и инициализацию генератора случайных чисел (дело в том, что если это не сделать, то при каждом входе в программу будет генерироваться всегда одна и та же последовательность чисел).

Здесь есть матрица целых чисел, и в ней 9 столбцов и строк (дело в том, что нумерация их также начинается с 0, и поэтому, чтобы было удобнее, мы берём 9 столбцов и строк, использовать из которых будем 1-8, а самые первые, под индексом 0, будут нерабочими). Кнопка заполняет матрицу нулями (очищает её), а затем генерирует два случайных числа. После генерации идёт проверка: ноль в соответствующей ячейке или нет. Если нет, то генерация производится снова. Если 0, то в ячейку записывается 1, то есть мы устанавливаем ферзя.

Как устанавливать угрозы? По вертикали и горизонтали это просто: нужно лишь перебрать все ячейки по Y при X=const. И наоборот. А вот с диагоналями сложнее.
Посмотрите на рисунок. Ферзь - чёрный квадрат. Видим, что при подъёме или спуске по Y номера красных квадратов (диагональных) по X увеличиваются на 1 по модулю (т.е. по одной диагонали номер уменьшается, по другой - увеличивается) относительно номера по X ферзя. Этим мы и воспользуемся.



Здесь пока установлены только угрозы по горизонтали и вертикали. А также использованы новые компоненты - глобальные переменные. Они хороши тем, что во всех компонентах GlobalVar, имеющих одинаковый параметр Name, содержатся одинаковые данные. Если в каком-то компоненте GlobalVar изменить данные, то в другом GlobalVar с таким же именем данные тоже изменятся. Глобальные переменные используются, чтобы не тянуть много связей.

В схеме также есть два цикла. Первый устанавливает угрозы по вертикали, а второй - по горизонтали. Как видите, у первого MatrixRW Х всегда постоянный. Меняется Y в зависимости от итерации цикла. Таким образом, во всю вертикаль, где находится ферзь, мы заносим значение 2, что означает угрозу. Однако на этой вертикали есть и сам ферзь (это отмечено как 1), и в эту ячейку заносить 2 не нужно. Вот за этим используется IF_else: если Y попался тот, где находится ферзь, то никакое значение в матрицу не заносим.



А здесь уже реализована расстановка угроз по диагонали. Рассмотрим первую часть установки. Она начинается с прибавления 1 к текущему Y (тому, где стоит ферзь). Это значит, полученное значение на доске будет ниже ферзя (см. рисунок выше). В нашем случае - 6. А теперь, чтобы получить при этом Y те значения Х, в которых есть угроза, нужно к текущему Х (где стоит ферзь) прибавить 1 и отнять один (получится два значения).

При следующем прибавлении 1 к Y (итерация цикла) прибавить и отнять нужно уже 2 для Х, где стоит ферзь. Прибавляемое число реализуется в счётчике, который увеличивается на 1.

Также идёт проверка, не выходит ли полученное число за пределы 1 и 8. И в матрицу записывается 2.

Практически так же происходит расстановка угроз и выше ферзя. Только тут нужно идти от 4 (это значение выше Y ферзя на 1) до 1. Так как аналога downto я в HiAsm не нашёл, то просто из текущего Y вычитал прямые итерации цикла. А дальше всё аналогично.

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



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



И вот, наконец, происходит отрисовка. По сути, нам важны ячейки матрицы только со значением 1, там, где ферзи. Значения 2 нужны только на этапе расставления ферзей, чтобы не поставить ферзя под угрозу. Но если есть желание - можно использовать и двойки в матрице.

Фигурку ферзя мы отрисовываем по координатам X и Y. Ведь размер каждой ячейки доски у нас примерно 47, и мы берём из цикла соответствующее значение (не забываем убавить на 1, потому что начинать нужно от 0, а цикл для удобства у нас начинается с 1), умножая его на 48 (это значение подбиралось опытным путём в соответствии с размерами фигурки ферзя).

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

Когда вы испробуете программу, то увидите, что чаще всего на доске оказывается 7 ферзей. Это наиболее вероятная расстановка. Но нажимайте кнопку много раз - и вы поймаете разные ситуации.

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




Внимание! Распаковывать архивы надо архиватором 7zip!

---

Если вам нужно сфотографироваться, то вам нужен фотограф Санкт-Петербург
. Есть фотосессии для беременных в комфортной студии.

Самые разные винтовые компрессоры предлагает фирма "ПневмоТехника". Выберите компрессор из каталога и закажите его.