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

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу (вариант №3) Maks 15.11.2026 Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .	Транслитерация текста с кириллицы на латиницу (вариант №2) Maks 13.11.2026 Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .	Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .

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

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

Решение