Перечислить все расстановки 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, а Вам огромное спасибо. Все стало понятным

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

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

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,536 Записей в блоге: 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,536 Записей в блоге: 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, при которых они не бьют друг друга

Решение