Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Задачка про ферзей в кв. матрице

1.8K
12 декабря 2006 года
dEBuch
95 / / 21.10.2005
Нужно раставить N ферзей на шахматной доске NxN клеток, так чтоб они не били друг-друга. Напомню ферзь бьет по горизонтали, вертикали и диогоналям.
Я создал две A,B матрицы, чтоб одна входила в цикл и каждый эл. проверяла, я вторая матрица(B) для записи ферзей, также с помощю ее идет проверка кадого ферзя, на то, он проверяемую клетку матрицы A или нет, потом я вывожу саму матрицу B. Обе матрицы ог. типа, если клетка матрицы B с ферзем то она true и печатает 1, если нет то печатается 0. Я зделал проверкуследущю тоесть по вертикали и горизонтали ясно как проверить, по диагоналям я проверял если столбец проверяемой клетки минус столбец ферзя из матрицы B равен разности сталбцов, тоесть abs(i1-i2)=abs(j1-j2) то проверяемая клетка стоит на диогонали. Также проверачную матрицу(B) я пускал в цикл на проверку ферзей, если клетка была ферзь то начинал проверку если нет, то нифига :). Короче, вот так вот, мой алгоритм грубо говоря. Его я могу щас учлучшить, но фигня он не срабатывает. Вот код, мне лижбы заработал а так я сам сделаю дальше.
-------------------------------------------------------------------------
program n1;
Uses Crt;
const m=100;
var
A:array[1..m,1..m] of boolean;
B:array[1..m,1..m] of boolean;
s:boolean;
n,i,e,c,k:integer;
begin
Write('Vvedite porydok shaxmatnoy doski n:');
Readln(n);
for i:=1 to n do
for e:=1 to n do
begin
for c:=1 to n do
for k:=1 to n do
if B[c,k]=true then
if (c=i)or(e=k)or(abs(i-c)=abs(e-k)) then
s:=true;
if s<>true then
B[i,e]:=true;
end;
for c:=1 to n do
for k:=1 to n do
begin
if B[c,k]=true then
Write('1')
else
Write('0');
if k=n then
Writeln(' ');
end;
Readln
end.
-------------------------------------------------------------------------
Где то тут у меня грубая ошибка :( т.к. показывается всего лиж один ферзь. плизз помогите устронить. Программы после пива писать нельзя.
13K
16 декабря 2006 года
Spirale
21 / / 17.03.2006
Цитата: dEBuch
Программы после пива писать нельзя.

[SIZE=4][FONT=Comic Sans MS]:):rolleyes::eek:
Итак будем использовать поиск с возвратом.
[/FONT][/SIZE] [FONT=&quot][FONT=Comic Sans MS][SIZE=4]Общая схема алгоритма поиска всех возможных решений:[/SIZE][/FONT][/FONT]

Код:
[FONT=Comic Sans MS][SIZE=4]procedure Queen ( i : integer );[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]   {Ставим i-го ферзя в i-ую вертикаль}[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]   begin[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]    инициировать выбор позиции для i-го ферзя;[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]    repeat[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]     выбрать позицию;[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]     if  безопасно then[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]      begin[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]       поставить ферзя;[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]       if i < N then Queen ( i+1 )[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]                else записать решение;[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]       убрать ферзя;[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]      end[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]    until нет больше позиций;[/SIZE][/FONT]
  [FONT=Comic Sans MS][SIZE=4]   end;[/SIZE][/FONT]
[SIZE=4][FONT=Comic Sans MS]Есть два пути решения этой задачи и зависят они от того,[/FONT][/SIZE][FONT=&quot][FONT=Comic Sans MS][SIZE=4]как представить данные о том, куда можно поставить очередного ферзя, а куда - нельзя![COLOR=Red]

Первый алгам:
[/COLOR][/SIZE][/FONT][/FONT] [FONT=Comic Sans MS][SIZE=4][FONT=&quot][SIZE=4]Хранит на каждом шаге одну границу S [1..N] (т.е. ферзя можно попытаться поставить на горизонталь от S до N) и поднимает ее, пока не получит S=N, тогда происходит возврат.[/SIZE][/FONT][/SIZE][/FONT]
[FONT=&quot][FONT=Comic Sans MS][SIZE=4]В этом случае для того, чтобы проверить, можно ли поставить очередного ферзя, нужно вернутся ко всем уже поставленным.[/SIZE][/FONT][/FONT]
[COLOR=Red][SIZE=4][FONT=Comic Sans MS]И второй алгам:
[/FONT][/SIZE][/COLOR] [FONT=Comic Sans MS][SIZE=4][FONT=&quot]Хранит множество возможных позиций в явном виде тремя массивами[/FONT][/SIZE][/FONT]
[FONT=Comic Sans MS][SIZE=4][FONT=&quot] H [1..N] занята(false) горизонталь[/FONT][/SIZE][/FONT]
[FONT=Comic Sans MS][SIZE=4][FONT=&quot] D1[2..2*N] занята(false) /-диагональ[/FONT][/SIZE][/FONT]
[FONT=Comic Sans MS][SIZE=4][FONT=&quot] D2[1-N..N-1] занята(false) \-диагональ[/FONT][/SIZE][/FONT]
[FONT=Comic Sans MS][SIZE=4][FONT=&quot]В этом случае проверка того, можно ли поставить нового ферзя, достаточно проста.:)[/FONT][/SIZE][/FONT]
[FONT=&quot][FONT=Comic Sans MS][SIZE=4]Замечу, что среди полученных решений есть много симметричных, некоторые из них можно отсечь, если начинать заполнять первую вертикаль со второй горизонтали и заполнять только до середины.[/SIZE][/FONT][/FONT]
23K
16 декабря 2006 года
prednizolon
10 / / 16.12.2006
dEBuch
у меня есть работающая прога, могу исходник дать
(потому что это проще чем разбираться в чужом коде, sorry)
если что, могу обьяснить код
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог