Тест 8 ферзей на МК-61: другие подходы
Программы-победители конкурса поиска расстановок 8 ферзей на шахматной доске были опубликованы в журнале "НиЖ" №10 за 1988 год. Время счета измерялось часами, потребовались оптимизация перебора: получение 12 базовых расстановок и 80 производных от них. Тем не менее, общее время выполнения оставалось значительным.
Конкурс также был ограничен моделями второго поколения Б3-34, МК-54 и МК-56. Может показаться странным, но реализации на старых моделях -- более эффективные за счет разорванной в МК-61 связи между регистрами 0 и Е: цикл по П0 совмещался с операциями с "массивом" по КПЕ/КИПЕ, не уменьшавших значение регистра 0.
Тест производительности не требует поиска всех расстановок, достаточно найти первую. Приведенная по ссылке программа Ильи Васильева (AtH) выполняется на "железной" реплике МК-61 mini за 402 секунды (6 мин 42 сек). Замеры выполнил Алексей Сугоняев, подробнее в разделе "Спортивное программирование" в нашей телеграм-группе.
По сравнению с 8-9 секундами выполнения на МК-152, МК61 mini, использующий полный эмулятор, примерно в 40-50 раз медленнее, хотя и в 20 раз быстрее оригинала.
Есть ли другие подходы?
Подход с использованием битовых масок
Хотя реализация 8х8 на МК-61 может быть медленнее, чем простой перебор, данный алгоритм растет как n^2, а не n^3: требуются два вложенных цикла, а не три.
Идея использования битовых масок состоит в формировании маски текущих занятых/пробиваемых ферзями полей, и одного сравнения с ней позиции нового ферзя вместо перебора пересечений по горизонталям и диагоналям.
В отличие от Б3-34, МК-61 обладает логическими операциями, весьма странно реализованными: старший разряд не используется, после него алгоритм устанавливает десятичную точку, операции проводятся поразрядно над дробной частью. То есть в нашем распоряжении только 7 разрядов по 4 бита.
На доске 8х8 имеется 8 горизонталей и 26 диагоналей, если не считать угловые клетки вырожденной диагональю. Такое количество должно помещаться в две маски:
- маска горизонталей
- маска диагоналей
Маска вертикалей нас не интересует, ферзи устанавливаются на вертикали 1-8 последовательно, не пересекаясь.
Вычисление маски для горизонталей (координата y):
M(y) = int( 10^(y − 2) + 2 / y^2 ) + 10000000
Вычисление маски для горизонталей (координаты поля x,y):
M(x, y) = int(A + 2B) + 10000000, где
- A = 10^a + 8 * 10^(−a),
- B = 10^b + 2 * 10^(−b).
- a = x − y
- b = x + y − 9
Операция int() соответствует отбрасыванию дробной части на ПМК. Константа 10000000 требуется для перевода 7-разрядной маски в пригодный для логических операций вид.
Выражения, переведенные на язык стековой машины с набором операций МК-61, выглядят следующим образом:
-- Маска горизонтали
y 2 − 10^x 2 y x^2 / + int 10000000 +
-- Маска диагоналей
x y − 10^x dup 1/x 8 * +
x y + 9 − 10^x dup 1/x 2 * + 2 *
+ int 10000000 +
Выражения для преобразования координат поля в битовые маски подбирались с помощью БЯМ (LLM) Sonet 5.5, доступной пока бесплатно.
Как видно, даже оптимизированные выражения со стековыми операциями занимают в сумме 38 команд (12 и 26) без учета возвратов. Для основной программы остается не так уж много, 66 шагов, так что техническая оптимизация будет неизбежна.
Алгоритм на Си-подобном языке выглядит так:
int main()
{
int x, y, a[9] = {};
x = 8;
do {
int mask_lines = 0;
int mask_diags = 0;
for (y = 8; y > x; y--) {
mask_lines |= make_mask_lines(y, a[y]);
mask_diags |= make_mask_diags(y, a[y]);
}
if (a[x] == 0)
a[x] = 8;
int intersect = 0;
for (y = a[x]; y > 0; y--) {
a[x] = y;
intersect = (mask_lines & make_mask_lines(x, a[x])) |
(mask_diags & make_mask_diags(x, a[x]));
if (intersect == 0)
break;
}
if (intersect != 0) {
// расстановка не найдена, возврат к предыдущей вертикали
a[x] = 0;
do {
x++;
} while (--a[x] == 0);
}
else
x--;
print_result(a);
} while (x > 0);
print_result(a);
}
Ожидаемый результат: 8 4 1 3 6 2 7 5
Полученная программа использует все 15 регистров памяти, почти всю программную: 104 шага из 105.
Из очевидных оптимизаций: при возврате (backtrace) не пересчитывать маски для расставленных ферзей, а удалять маску последнего через операции последняя_маска Кинв ИПмаски К/\ Пмаски перед блоком на шаге 59, но потребуются дополнительные шаги для вызова подпрограмм пересчета масок. Поэтому тратится время на полный пересчет при изменении текущей вертикали.
00.ИПD 01.1 02.- 03.ПD 04.Fx=0 05.07 06.С/П 07.8 08.ПB 09.ПC
10.П0 11.ИП0 12.ПE 13.ИПD 14.- 15.Fx#0 16.28 17.KППA 18.ИПB 19.K\/
20.ПB 21.ПП 22.77 23.ИПC 24.K\/ 25.ПC 26.FL0 27.11 28.KИПD 29.Fx=0
30.33 31.8 32.KПD 33.ИПD 34.ПE 35.KИПD 36.П0 37.ИП0 38.KПE 39.KППA
40.ИПB 41.K/\ 42.K{x} 43.Fx=0 44.51 45.ПП 46.77 47.ИПC 48.K/\ 49.K{x}
50.Kx#09 51.FL0 52.37 53.0 54.KПD 55.ИПD 56.1 57.+ 58.ПD 59.KИПD
60.1 61.- 62.KПD 63.Fx#0 64.55 65.БП 66.07 67.KИПE 68.2 69.-
70.F10^x 71.2 72.KИПE 73.Fx^2 74.: 75.БП 76.99 77.ИПE 78.KИПE 79.-
80.F10^x 81.В^ 82.F1/x 83.8 84.x 85.+ 86.ИПE 87.KИПE 88.+ 89.9
90.- 91.F10^x 92.В^ 93.F1/x 94.2 95.x 96.+ 97.2 98.x 99.+
A0.K[x] A1.ИП9 A2.+ A3.В/О
Заполнение регистров:
- 7 F10^x П9
- 67 ПА
- Сх П1 П2 П3 П4 П5 П6 П7 П8
Запускаем 8 БП 03 С/П
После останова в регистрах 1-8 расстановка ферзей: в i-м регистре (номер вертикали) лежит номер горизонтали: 8 4 1 3 6 2 7 5.
Тестовый пример для быстрого прогона
- 8 П8 4 П7 1 П6 3 П5 6 П4 2 П3 7 П2 0 П1
- 1 БП 03 С/П
После останова в регистрах 1-8 расстановка 8 4 1 3 6 2 7 5.