Перечислить все расстановки N ферзей на шахматной доске NxX, при которых они не бьют друг друга

@Teylor · Регистрация: 01.12.2017

Студворк — интернет-сервис помощи студентам

Задача: Перечислить все расстановки N ферзей на шахматной доске NxX, при которых они не бьют друг друга

Есть на Paskal решение, как бы выглядело это на С++, т.к. слабо знаком с Paskal'ем

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
program Queens;
   const N=8;
   type Index=1..N;
    Rasstanovka=array [Index] of 0..N;
   var X:Rasstanovka;
       Count:word;
   function P(var X:Rasstanovka;k,y:Index):boolean;
     var i:Index;
   begin
     i:=1;
     while (i<k)and(y<>X[i])and(abs(k-i)<>abs(y-X[i])) do inc(i);
     P:=i=k
   end;
   procedure Backtracking(k:Index);
     var i,y:Index;
   begin
     for y:=1 to N do
       if P(X,k,y) then
     begin
       X[k]:=y;
       if k=N then
         begin
           for i:=1 to N do write(X[i]);writeln;inc(Count)
         end;
       Backtracking(k+1)
     end
   end;
 begin
   Count:=0;
   writeln('Расстановки ',N,' ферзей:');
   Backtracking(1);
   writeln('Всего ',Count,' расстановок')
 end.

@sty4ent · 26.10.2018, 00:19

Сообщение от Teylor

int rows[N];
* * int Count;
* * bool columns[N];
* * bool Adiags[N * 2 - 1];//?
* * bool Bdiags[N * 2 - 1];//?

rows зачем?

Добавлено через 2 минуты
ещё в задании надо сделать для доски N*X, а не N*N

Nishen · 26.10.2018, 01:14

sty4ent, новый аккаунт создал?

@Kuzia domovenok · 26.10.2018, 03:18

Отметим следующее. Все возможные способы расстановки ферзей -С^N_N*N около4400000000 для N=8. Каждый столбец содержит самое большее одного ферзя, что даёт только N^N расстановок (17000000 для N=8) накакие два ферзя нельзя поставить в одну строку, а поэтому для того чтовы вектор (a₁, a₂, ...a_N) был решением, он должен быть перестановкой элементов 1,2,...,N что даёт только N!(40000 для N=8) возможностей. Никакие два ферзя не могут находиться на одной диагонали, это сокращает дерево возможностей ещё больше(для N=8 в дереве остаётся 2056 узлов). Итак, с помощью ряда наблюдений мы исключили из рассмотрения большое число возможных расстановок ферзей на доске размером N*N. Использование подобного анализа для сокращения процесса перебора называется поиском с ограничениями или отсечением ветвей в связи с тем, что при этом удаляются поддеревья из дерева.
Вторым усовершенствованием является слияние, или склеивание ветвей. Идея состоит в том, чтобы избежать выполнения дважды одной и той же работы: если два или более поддеревьев данного дерева изоморфны, мы хотим исследовать только одно из них. В задаче о ферзях мы можем использовать склевание, заметив, что если a₁>N/2, то найденное решение можно отразить и получить решение, для которого a₁<N/2. Следовательно, деревья, соответствующие, например случаям a₁=0 и a₁=N-1 изоморфны.
Следующие рисунки иллюстрируют сказанное и поясняют ввод используемых структур данных.

@Kuzia domovenok · 26.10.2018, 04:04

Перечислить все расстановки N ферзей на шахматной доске NxX, при которых они не бьют друг друга

@Teylor · 26.10.2018, 08:22 **[ТС]**

Nishen, По-моему, вы неадекватный

Добавлено через 8 минут
Kuzia domovenok, а Вам огромное спасибо. Все стало понятным

Новые блоги и статьи Все статьи Все блоги /
[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .
попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .	Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .

Nishen 1359 / 857 / 366 Регистрация: 26.02.2015 Сообщений: 3,824
	26.10.2018, 01:14
	sty4ent, новый аккаунт создал? 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,537 Записей в блоге: 1
	26.10.2018, 03:18
	Сообщение было отмечено Teylor как решение Решение Отметим следующее. Все возможные способы расстановки ферзей -С^N_NN около4400000000 для N=8. Каждый столбец содержит самое большее одного ферзя, что даёт только N^N расстановок (17000000 для N=8) накакие два ферзя нельзя поставить в одну строку, а поэтому для того чтовы вектор (a₁, a₂, ...a_N) был решением, он должен быть перестановкой элементов 1,2,...,N что даёт только N!(40000 для N=8) возможностей. Никакие два ферзя не могут находиться на одной диагонали, это сокращает дерево возможностей ещё больше(для N=8 в дереве остаётся 2056 узлов). Итак, с помощью ряда наблюдений мы исключили из рассмотрения большое число возможных расстановок ферзей на доске размером NN. Использование подобного анализа для сокращения процесса перебора называется поиском с ограничениями или отсечением ветвей в связи с тем, что при этом удаляются поддеревья из дерева. Вторым усовершенствованием является слияние, или склеивание ветвей. Идея состоит в том, чтобы избежать выполнения дважды одной и той же работы: если два или более поддеревьев данного дерева изоморфны, мы хотим исследовать только одно из них. В задаче о ферзях мы можем использовать склевание, заметив, что если a₁>N/2, то найденное решение можно отразить и получить решение, для которого a₁<N/2. Следовательно, деревья, соответствующие, например случаям a₁=0 и a₁=N-1 изоморфны. Следующие рисунки иллюстрируют сказанное и поясняют ввод используемых структур данных. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,537 Записей в блоге: 1
	26.10.2018, 04:04
	1

@Teylor 14 / 14 / 0 Регистрация: 01.12.2017 Сообщений: 577
	26.10.2018, 08:22 [ТС]
	Nishen, По-моему, вы неадекватный Добавлено через 8 минут Kuzia domovenok, а Вам огромное спасибо. Все стало понятным 0

Опции темы

Перечислить все расстановки N ферзей на шахматной доске NxX, при которых они не бьют друг друга

Решение