Benchmark 8 ферзей

Поиск расстановки 8 ферзей на шахматной доске используется для измерения скорости вычислений ПМК. Результаты зарубежных моделей можно увидеть, например, здесь Calculator Benchmark.

В журнале "НиЖ" в свое время был даже объявлен конкурс на создание подобной программы. Найти оригинал статьи мне пока не удалось, помню только, что время счета измерялось часами, альтернативой перебору вариантов предлагался метод Монте-Карло. Впрочем, на времени ожидания результата это сказывалось незначительно.

Нас же интересует, насколько быстро справится с задачей новый МК-152

Пишем программу

Поскольку готовой программы найти не удалось, за основу был взять вариант на Паскале по упомянутой ссылке.

Немного об алгоритме, который уже оптимизирован по числу вариантов перебора. Задачу решил больше 200 лет тому назад Леонард Эйлер. При отсутствии компьютера, он, тем не менее, нашел все 92 расстановки. Перед ПМК стоит задача попроще - найти первую подходящую расстановку.

Очевидно, на каждой из 8 вертикалей должно стоять по ферзю. Каждую такую расстановку можно закодировать одномерным массивом
X[1],...,X[8],
где X[i] - номер горизонтали для i-го ферзя.

Поскольку никакие два ферзя не могут стоять на одной горизонтали (тогда они бьют друг друга), то все X[i] различны, т.е. образуют перестановку из чисел 1..8.

 procedure qbench;
 var
   a: array[1..8] of integer;
   r, s, t, x, y: integer;
 begin
   r := 8;
   s := 0;
   x := 0;
   repeat
     inc(x);
     a[x] := r;
     repeat
       inc(s);
       y := x;
       while y > 1 do begin
         dec(y);
         t := a[x] - a[y];
         if (t = 0) or (x - y = abs(t)) then begin
           y := 0;
           dec(a[x]);
           while a[x] = 0 do begin
             dec(x);
             dec(a[x]);
           end;
         end;
       end;
     until y = 1;
   until x = r;
   writeln(s);
 end;

Если добавить процедуру вывода, то получаем найденную позицию:

a8 b4 c1 d3 e6 f2 g7 h5

Скачать исходный текст программы для среды Delphi (файл NQueens.dpr) вы можете ниже в списке.

Хотя Паскаль хорош тем, что алгоритм "читается", но к сожалению, перевод паскаль-кода в ПМК-шный совершенно неоднозначен, поэтому пришлось создать промежуточный вариант на "неструктурированном псевдопаскале".
Вот он (надеюсь, профессор Вирт сейчас крепко сидит на стуле)

 begin
   RA := 8;
   RB := 0;
   RC := 0;
   repeat
     inc(RC);
     a[RC] := RA;
     repeat
       inc(RB);
       RD := RC;
       L2:
       if RD - 1 <= 0 goto L1;
         dec(RD);
         R9 := a[RC] - a[RD];
         if (R9 <> 0) and (RC - RD <> abs(R9)) goto L2;
           RB := 0;
           dec(a[RC]);
           L5:
           if a[RC] <> 0 goto L2;
             dec(RC);
             dec(a[RC]);
           goto L5;
       L1:
     until RB = 1;
   until RC = RA;
   stop;
 end;

Теперь достаточно легко перейти к программе для МК-61/52, не претендующей на краткость. На эмуляторе МК-52 счет в реальном масштабе времени занял около получаса, после чего ПМК "завис". К счастью, у эмулятора есть "быстрый" режим, позволяющий получить результат практически мгновенно. Программа подойдет и для старых моделей МК-54/56 и Б3-34. Файл с программой для эмулятора можно скачать по ссылке в конце статьи.

00.Cx 10.ПВ  20.ИПВ  30.64   40.К|х|  50.1    60.1    70.ИПА 
01.ПО 11.ПС  21.1    31.Fx≥O 41.ИПС   51.-    61.-    71.-   
02.П1 12.8   22.+    32.64   42.ИПД   52.КПС  62.БП   72.Fx=0
03.П2 13.ПА  23.ПВ   33.ПД   43.-     53.Fx=0 63.52   73.14  
04.ПЗ 14.ИПС 24.ИПС  34.КИПС 44.-     54.26   64.ИПВ  74.С/П 
05.П4 15.1   25.ПД   35.КИПД 45.Fx=0  55.ИПС  65.1   
06.П5 16.+   26.ИПД  36.-    46.26    56.1    66.-    
07.П6 17.ПС  27.1    37.П9   47.0     57.-    67.Fx=0
08.П7 18.ИПА 28.-    38.Fx≠0 48.ПВ    58.ПС   68.20  
09.П8 19.КПС 29.Fx≠0 39.47   49.КИПС  59.КИПС 69.ИПС 

Инструкции по запуску: В/0, С/П

После останова в регистрах Р1..Р8 координаты по вертикали i-го ферзя (стоящего на i-й горизонтали).

Контрольный запуск на эмуляторе выдает следующую комбинацию:
Р1=8, Р2=4, Р3=1, Р4=3, Р5=6, Р6=2, Р7=7, Р8=5,
что соответствует расстановке на шахматной доске:
Фa8, Фb4, Фc1, Фd3, Фe6, Фf2, Фg7, Фh5

Программу, видимо, можно подсократить в теле циклов, но вряд ли это заметно скажется на времени счета для МК-52.

Тестируем МК-152

Испытания провел ув. AtH на своём МК-152.

Вышеприведенная программа для ПМК без изменений выполняется на МК-152 ровно 9 секунд.
Любопытно было бы её переписать с учётом особенностей компактного языка (циклы по FL0/FL1, автоинкремент по КИП5/6) и огромного количества регистров памяти в МК-152...

А пока AtH подсократил программу на восемь шагов (с регистром B также имеет смысл разобраться, он из счётчика превратился во флаг) и вот, что получилось:

00.Cx   01.ПB   02.9   03.П0   04.Cx   05.КП0  06.ИП0 07.Fx=0 08.04   09.ПС
10.ИПС  11.1    12.+   13.ПС   14.8    15.КПС  16.ИПВ 17.1    18.+    19.ПВ
20.ИПС  21.ПД   22.ИПД 23.1    24.-    25.Fx≠0 26.56  27.Fx≥0 28.56   29.ПД
30.КИПС 31.КИПД 32.-   33.Fx≠0 34.42   35.К|x| 36.ИПС 37.ИПД  38.-    39.-
40.Fx=0 41.22   42.0   43.ПВ   44.КИПС 45.1    46.-   47.КПС  48.Fx=0 49.22
50.ИПС  51.1    52.-   53.ПС   54.БП   55.44   56.ИПВ 57.1    58.-    59.Fx=0
60.16   61.ИПС  62.8   63.-    64.Fx=0 65.10   66.С/П

Время счёта по новой версии программы на МК-152 — 8 секунд.
Соответствующий файл для эмулятора называется 8queens2.c3.

Буквальный перевод кода для калькулятора Casio FX-4500PA (программа по первой ссылке, переменные S, Y и X хранятся в регистрах 9, A и B) без оптимизации под МК-152 даёт результат 876 (количество перебранных узлов дерева вариантов, это же число показывает и программа на бейсике - самая первая в списке программ по упомянутой в начале ссылке) и требует 13 секунд:

00.Cx   01.1  02. 2   03.П0   04.Cx   05.КП0  06.ИП0 07.Fx=0 08.04   09.8
10.ИПB  11.-  12.Fx≠0 13.56   14.ИПB  15.1    16.+   17.ПB   18.8    19.КПB
20.ИП9  21.1  22.+    23.П9   24.ИПB  25.ПA   26.ИПA 27.1    28.-    29.ПA
30.Fx≠0 31.09 32.КИПB 33.КИПA 34.-    35.Fx≠0 36.44  37.K|x| 38.ИПB  39.ИПA
40.-    41.-  42.Fx=0 43.26   44.КИПB 45.1    46.-   47.КПB  48.Fx=0 49.20
50.ИПB  51.1  52.-    53.ПB   54.Fx=0 55.44   56.ИП9 57.С/П

Но на этом тесты не закончились. AtH воспользовался своим старинным другом - ПМК МК-56, заменил в нашей первой программе для МК-52 оператор K|x| на Fx<0 nn /—/ и запустил программу. ПМК так надолго "ушел в себя", что даже появились опасения, не зациклился ли он? Но вот и всё, ПМК досчитал! Три часа девять минут (189 минут, то есть 11340 секунд).

Получается, что МК-152 быстрее МК-56 примерно в 1300 раз (та же версия программы выполнялась на МК-152 за девять секунд). То же самое можно сказать и относительно всех старых моделей.

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

File attachments: 
Прикрепленный файлРазмер
Binary Data 8queens.c34.67 KB
Binary Data 8queens2.c34.58 KB
Binary Data NQueens.dpr820 байтов

Комментарии

Мне тут в руки попалась жгучая мечта из начала 90-х годов: palmptop HP100LX, под управлением MS-DOS 5.0
Тест 8 ферзей на GW Basic-е занял аж целых 18 секунд :)

Однако многовато даже для того времени, паскаль-программа на более слабом ДВК-2М выполнялась в пределах 1 секунды. GW-basic, как я понимаю - классический интерпретатор.

Угу, многовато. Но это один из старых бейсиков для MS-DOS:

"One other aspect of GWBASIC.EXE needs to be mentioned here: It is an assembly language program written for an 8086 microcomputer running the DOS operating system on a PC. No, it does not depend on an 8087 math co-processor. It has no idea what a co-processor is, or whether one is even present--it does its own math, the old-fashioned way. In fact, its method of storing floating point numbers is unique unto itself. QuickBASIC--a compiler from Microsoft--was the only other language that tried to emulate that methodology. (It also may oftentimes produce different arithmetic results. Caveat.)"

Хотя на HP100LX можно и быстрее: 16 бит CPU 80816 7.91 MHz

HP-35s за 4 с лишним минуты считает. Если я правильно помню изредка оживаемый сайт Calculator Benchmark