|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rustam Gadeyev 2:5008/14 11 Oct 2001 22:36:29
To : All
Subject : 8 мирных ферзей
--------------------------------------------------------------------------------
Мне сегодня один товарищ сказал, что когда он был студентом, то его рекурсивная
программа находила все 92 варианта расстановки не бьющих друг друга ферзей на
шахматной доске за 45 минут. Что-то меня задело такое долгое время счета и
где-то за полчаса родил программу, которая идет ниже в письме.
Эти 92 позиции на доске 8х8 без вывода на экран считаются на P3-450 0.11сек,
а 14х14 считаются 22.5сек.
Вопрос: можно ли сделать лучше? :) Пусть я давно уже не студент, но написать
нетривиальную программку за полчаса мне не слабо.
//--- 8pherz.pas ---\\
uses crt; {written by Rustam G. 11.10.01}
const num=14; {14 за 22.5 сек без вывода на экран}
var
a:array[1..num] of byte; {позиции ферзей}
p,d1,d2:array[1..num*2-1] of boolean;
n,i,j,kol:byte;
begin
clrscr;
for i:=1 to num*2-1 do
begin
p[i]:=true;
d1[i]:=true;
d2[i]:=true;
end;
for i:=1 to num do a[i]:=num+1; {чтобы при выводе лишние ф. не мешались}
n:=1;a[n]:=1;kol:=0;
while n>0 do
begin
{если сюда можно поставить ферзя}
if p[a[n]] and d1[a[n]+n-1] and d2[num-a[n]+n] then
begin
{вывод на экран}
{
for i:=1 to num do
for j:=1 to num do
begin
gotoxy(j*2,i);
if a[j]=i then write(j) else write('* ');
end;
{ if readkey=#27 then exit;{пошагово}
if n=num then {если встал последний ферзь, комбинация достигнута }
begin
kol:=kol+1;
{ if readkey=#27 then exit;{по позициям}
end;
if n<num then {если это не последний ферзь, попробуем поставить еще}
begin
p[a[n]]:=false; {запрет горизонтали}
d1[a[n]+n-1]:=false; {запрет диагонали1}
d2[num-a[n]+n]:=false; {запрет диагонали2}
inc(n); {к следующем ферзю}
a[n]:=1; {начиная с позиции 1}
continue; {летим пробовать поставить еще один ферзь}
end;
end;
{идем на новую позицию}
while true do
begin
inc(a[n]);
if a[n]<=num then break {еще есть позиции для перебора в столбце}
else {этот столбик уже весь перебрали}
begin
dec(n); {отступаем}
if n<1 then break; {больше некуда?}
p[a[n]]:=true; {разрешить горизонталь}
d1[a[n]+n-1]:=true; {разрешить диагональ1}
d2[num-a[n]+n]:=true; {разрешить диагональ2}
end;
end;
end;
writeln;
writeln(kol,' вариантов');
end.
\\--- 8pherz.pas ---//
Good Bye.
--- ---
* Origin: Ulan-Ude. Buryatia. (2:5008/14)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
