Скрыпник Андрей : другие произведения.

Задача об N ферзях

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:
Школа кожевенного мастерства: сумки, ремни своими руками
 Ваша оценка:
  • Аннотация:
    ISBN 9780359959365; http://vixra.org/abs/1806.0330

1. Формулировка Задачи об N ферзях

   Исходная формулировка: Рассчитать алгоритм, позволяющий расставить N-ое количество ферзей на шахматном поле со сторонами, равными N, где N≥4 так, чтобы ни один из них не находился под боем другого.
  

2. Алгоритм решения Задачи об N ферзях

   2.1. Первая детализация условий
   Согласно условиям при последовательном решении задачи параметр N поочерёдно будет принимать чётные и нечётные значения:

N2м=2*M, где M≥2,

(01)

N2м+1=2*M+1, где M≥2.

(02)

   Пусть, кроме N, даны N2м (01), N2м+1 (02) и соответствующие им M.
  
   2.2. Вывод 1
   Согласно условиям в каждом ряду клеток, как по горизонтали, так и по вертикали, должен находиться один ферзь - то есть в задаче задействован каждый ряд клеток, как по горизонтали, так и по вертикали. Следовательно, расположение каждого ферзя по вертикали (X) и по горизонтали (Y) для всех ферзей можно представить в виде двух равных последовательностей натуральных чисел:

X∈{Xn | Xn∈ℕ, n∈ℕ, 1≤Xn≤N},

(03)

Y∈{Yn | Yn∈ℕ, n∈ℕ, 1≤Yn≤N}.

(04)

  
   Из выражений (03) и (04) можно сделать следующий вывод:
   Вывод 1: Так как последовательности натуральных чисел {Xn} (03) и {Yn} (04) совпадают, все вычисления можно выполнять с одной переменной Xn.
  
   2.3. Формулы для исходных условий
   Условия размещения ферзей на шахматном поле для последовательностей {Xn} (03) и {Yn} (04) можно представить так:

Xn1+Yn1≠Xn2+Yn2, где n1,n2∈{n | 1≤n≤N};

(05)

Xn1-Yn1≠Xn2-Yn2, где n1,n2∈{n | 1≤n≤N}.

(06)

  
   2.4. Новые понятия для расположения ферзей
   Согласно условиям (05) и (06) введём новые понятия для сравнения расположения ферзей на шахматном поле:

∑=X+Y,

(07)

S=X-Y.

(08)

  
   2.5. Выражение для ферзей
   С учётом выражений (07), (08) и условий размещения ферзей на шахматном поле, представленных в (2.3), для каждого ферзя из N-ого количества в условии задачи будет верно следующее выражение:

(∑)∧X=Y+S.

(09)

  
   2.6. Вторая формулировка задачи
   Согласно (2.2) одну из последовательностей натуральных чисел, характеризующих расположение ферзей по вертикали, {Xn} (03), можно представить заранее известной и перевести в условия задачи. В таком случае неизвестной остаётся только последовательность натуральных чисел, характеризующих расположение ферзей по горизонтали, {Yn} (04).
   Теперь можно уточнить Исходную формулировку:
   Вторая формулировка задачи: Расположить последовательность натуральных чисел {Yn} вдоль равной известной последовательности натуральных чисел {Xn} так, чтобы выполнялись условия (05) и (06).
   (Примечание ко второй формулировке: Расположение одной последовательности вдоль равной другой означает то, что если первые члены обеих последовательностей совпадают, то и последние их члены будут совпадать. Если первый член второй такой последовательности соответствует (N-Xn)-му члену первой последовательности, то последний член второй последовательности будет соответствовать (N-(Xn+1))-му члену первой последовательности, где 1≤Xn≤(N-2).)
  
   2.7. Вторая детализация условий
   Для решения этой задачи из-за неоднозначности условий (05) и (06) необходимо последовательности {Xn} (03) и {Yn} (04) разделить на равные подмножества. Чтобы избавиться от неоднозначности условий (05) и (06), для последовательностей {Xn} и {Yn} разделение на подмножества должны происходить по различным правилам.
  
   2.7.1. Деление поля по вертикали
   Последовательность натуральных чисел {Xn} (03) разделим на последовательность натуральных чисел до M и последовательность натуральных чисел от (М+1) до N:

X∈{X≤м | X≤м∈ℕ, 1≤X≤м≤M},

(10)

X∈{X>м | X>м∈ℕ, (М+1)≤X>м≤N}.

(11)

  
   2.7.2. Деление поля по горизонтали
   Последовательность натуральных чисел {Yn} (04) разделим на последовательность чётных чисел {Y2x} и последовательность нечётных чисел {Y2х-1}:

Y∈{2*Xn | n∈ℕ, 1≤X≤M},

(12)

Y∈{2*Xn-1 | n∈ℕ, где для N2м: 1≤Xn≤M; для N2м+1: 1≤Xn≤M+1 } .

(13)

  
   2.8. Особенность новых последовательностей
   По количеству членов как для N2м (01), так и для N2м+1 (02) последовательность {X≤м} (10) равна последовательности {Y2x} (12), а последовательность {X>м} (11) равна последовательности {Y2х-1} (13). Следовательно в нижней половине шахматного поля ферзи будут размещаться на чётных по горизонтали клетках. В верхней половине шахматного поля ферзи будут размещаться на нечётных по горизонтали клетках.
  
   2.9. Вывод 2
   Из выражения (09) следует, что только S (08) может принимать как отрицательные, так и положительные значения, а также может принимать значение S=0. Но, хотя, согласно (08), у N-ого количества ферзей количество значений Sn<0 может быть равно (N-1), условия (05) и (06) так ограничивают это количество, что позволяет сделать следующий вывод:
   Вывод 2: Для N-ого количества ферзей на шахматном поле со сторонами, равными N, количество значений Sn<0 должно быть равно или приблизительно равно количеству значений Sn≥0.
   Учитывая Вывод 2, значение первого члена и шаг последовательности чётных чисел {Y2x} (12), следует разместить или все значения Sn<0, или абсолютное большинство значений Sn<0 в выражения для ферзей (09), соответствующие известной последовательности натуральных чисел до М {X≤м} (10) или нижней половине шахматного поля. Тогда в выражениях для ферзей (09), соответствующих известной последовательности натуральных чисел от М до N {X>м} (11) или верхней половине шахматного поля, будут в основном значения Sn≥0.
   В соответствии с тем, что решение задачи начинается с малых величин (M≥2) (см. (01) и (02)), только два варианта распределения последовательности {Y2x} (12) вдоль последовательности {X≤м} (10) подходят для решения задачи: первый вариант - когда все выражения для ферзей (09) имеют Sn<0; второй вариант - когда выражение для одного ферзя имеет Sn≥0.
  
   2.10. Первый вариант
   В этом варианте в выражениях ферзей (09), расположенных в нижней половине шахматного поля, т. е. включающих последовательность {X≤м} (10), есть только значения Sn<0 (08).
   Чтобы разместить все значения Sn<0 в выражения для ферзей (09), включающие {X≤м} (10) и чтобы соблюдались условия (05) и (06), необходимо последовательность чётных чисел {Y2x} (12) расположить вдоль равной последовательности натуральных чисел {X≤м} (10) так, чтобы первые члены обеих последовательностей совпадали. Приведём последовательность расположения ферзей в виде выражения (09) в нижней половине шахматного поля, соответствующего последовательности {X≤м} (10). Это выражение и будет первым вариантом для решения задачи:

(3*Xn)∧Xn=2*Xn+(-Xn), где 1≤n≤М, 1≤Xn≤М.

(14)

  
   В выражении (14) есть следующая закономерность для всех ферзей этой последовательности:

∑n=3*Xn, где 1≤Xn≤M.

(15)

  
   Так как в данном алгоритме последовательность {Y2x} располагается вдоль последовательности {X≤м}, то для условия (05) достаточно, чтобы в случае одного выражения для ферзей (09) в решении задачи все ∑n принадлежали одному из приведённых ниже множеств:

∑n∈{3*Xn | Xn≥1},

(16)

∑n∈{3*Xn+1 | Xn≥1},

(17)

∑n∈{3*Xn+2 | Xn≥1}.

(18)

   В случае двух или трёх выражений для ферзей в одном решении задачи, для условия (05) достаточно, чтобы ∑n этих двух или трёх выражений для ферзей принадлежали разным множествам (16), (17) или (18).
  
   2.11. Второй вариант
   В этом варианте в выражениях для ферзей (09), расположенных в нижней половине шахматного поля, т. е. включающих последовательность {X≤м} (10), кроме значений Sn<0 (08) есть одно значение Sn>0.
   Чтобы соблюдались Вывод 2 и условия (05) и (06), необходимо последовательность чётных чисел {Y2x} (12) расположить вдоль равной последовательности натуральных чисел {X≤м} (10) так, чтобы первый член последовательности {Y2x} (12) совпадал с последним членом последовательности {X≤м} (10). Приведём последовательность расположения ферзей в нижней половине шахматного поля, соответствующего последовательности {X≤м} (10), теперь в двух выражениях, которые и будут вторым вариантом для решения задачи:

1) (3*Xn+2)∧Xn=(2*Xn+2)+(-(Xn+2)), где 1≤n≤М-1, 1≤Xn≤М-1;

2) (М+2)∧М=2+(М-2).

(19)

  
   2.12. Вывод 3
   В (19) в первом выражении есть примечательная закономерность для выражений со значениями Sn<0:

∑n=3*Xn+2 , где 1≤n≤ М-1, 1≤Xn≤ М-1.

(20)

  
   Следовательно, так как (М+2)<(3*Xn+2) при Xn=М-1, для выполнения условия (05) должно соблюдаться следующее неравенство:

М+2≠3*Xn+2 , где Xn≥1.

(21)

   Выразим из выражения (21) М:

М≠3*Xn, где Xn≥1.

(22)

   Из выражения (22) следует вывод:
   Вывод 3: Выражения (19) будут вторым вариантом для решения задачи для чётных и нечётных N (N2м и N2м+1) при М=3*Xn+1 и М=3*Xn-1, где Xn≥1.
  
   2.13. Вывод 4
   Неоднозначность условий (05) и (06), Вывод 3 и необходимость соблюдения непрерывности последовательностей {Xn} и {Yn} в выражениях для ферзей приводят к следующему выводу:
   Вывод 4. Для окончательного избавления от неоднозначности условий (05) и (06) при решении задачи натуральный ряд N≥4 необходимо разделить не только на последовательности чётных (N2м (01)) и нечётных (N2м+1 (02)) чисел, но и по следующим значениям М данного N:

М∈{3*Xn | Xn≥1},

(23)

М∈{3*Xn+1 | Xn≥1},

(24)

М∈{3*Xn-1 | Xn≥1}.

(25)

  
   2.14. Окончательная формулировка
   Из-за малого количества вариантов выражения (14) и (19) (при условии соответствия выражений (19) Выводу 3) можно перевести в условия задачи. То есть требуется следующее уточнение:
   Окончательная формулировка: При данных в (14) или (19) выражениях для ферзей в нижней половине шахматного поля до X=М расположить последовательность нечётных чисел {Y2х-1} (13) в верхней половине поля вдоль последовательности натуральных чисел от М+1 до N ({X>м}) так, чтобы выполнялись условия (05) и (06).
  
   2.15. Первое основное решение
   Теперь можно приступить к решению задачи согласно Вывода 4. Рассмотрим последовательность {X>м} (11) при условии первого варианта (14) для чётных N2м (01).
   В первом варианте (14) собраны все значения S<0. Чтобы в выражениях для ферзей (09) в верхней половине шахматного поля, т. е. с последовательностью {X>м}, были только S≥0, необходимо совпадение первых членов последовательностей {X>м} и {Y2х-1} (13).
   Приведём последовательность расположения ферзей в верхней половине шахматного поля в виде выражения для ферзей (09), соответствующего последовательности {X>м}:

(3*Xn-2*М-1)∧Xn=(2*Xn-2*М-1)+(2*М-Xn+1), где М+1≤n≤2*М, М+1≤Xn≤2*М.

(26)

  
   Так как в (14) ∑n=3*Xn , где 1≤Xn≤M, возможно совпадение ∑n у последних членов выражения для ферзей (14) с ∑n у первого члена выражения для ферзей (26). Следовательно, для выполнения условия (05) должно соблюдаться следующее неравенство:

(3*(М+1)-2*М-1)≠3*Xn, где 1≤Xn≤M .

(27)

   Выразим из (27) условие для М:

М≠3*Xn-2=3*(Xn-1)+1, где Xn≥2.

(28)

   Следовательно, М∈{3*Xn | Xn≥1} или М∈{3*Xn-1 | Xn≥1} (см. Вывод 4)
   При сложении выражений (26) и (14) получим выражения для ферзей для всего шахматного поля:

1) (3*Xn)∧Xn=2*Xn+(-Xn), где 1≤n≤М, 1≤Xn≤М,

2) (3*Xn-2*М-1)∧Xn=(2*Xn-2*М-1)+(2*М-Xn+1), где М+1≤n≤2*М, М+1≤Xn≤2*М.

(29)

  
   Убрав из выражений для ферзей (29) ∑n и Sn, получим Первое основное решение задачи для чётных N2м (01) с М∈{3*Xn | Xn≥1} или М∈{3*Xn-1 | Xn≥1}, где Xn - значение ферзей по вертикали, Yn - значение ферзей по горизонтали:

1) Yn=2*Xn, где 1≤n≤М, 1≤Xn≤М,

2) Yn =2*Xn-2*М-1, где М+1≤n≤2*М, М+1≤Xn≤2*М.

(30)

  
   2.16. Второе основное решение
   Теперь рассмотрим последовательность {X>м} (11) при условии первого варианта (14) для нечётных N2м+1 (02).
   Из-за условия только Sn≥0 в выражениях для ферзей снова необходимо, чтобы первые члены последовательностей {X>м} (11) и {Y2х-1} (13) совпадали.
   Приведём последовательность расположения ферзей в верхней половине шахматного поля в виде выражения для ферзей (09), соответствующего последовательности {X>м}:

(3*Xn-2*М-1)∧Xn=(2*(Xn-М)-1)+(2*М-Xn+1), где М+1≤n≤2*М+1, М+1≤Xn≤2*М+1.

(31)

  
   Выражение (31) отличается от (26) только добавлением последнего члена с X=2*М+1 и Y=2*М+1. У него S=0. Для выражения (31) также верно условие (28).
  
   При сложении выражений (31) и (14) получим выражения для ферзей для всего шахматного поля:

1) (3*Xn)∧Xn=2*Xn+(-Xn), где 1≤n≤М , 1≤Xn≤М;

2) (3*Xn-2*М-1)∧Xn=(2*Xn-2*М-1)+(2*М-Xn+1);

где М+1≤n≤2*М+1, М+1≤Xn≤2*М+1.

(32)

  
   Убрав из выражений для ферзей (32) ∑n и Sn, получим Второе основное решение задачи для нечётных N2м+1 (02) с М∈{3*Xn | Xn≥1} или М∈{3*Xn-1|Xn≥1}, где Xn - значение ферзей по вертикали, Yn - значение ферзей по горизонтали:

1) Yn=2*Xn, где 1≤n≤М , 1≤Xn≤М;

2) Yn=2*Xn-2*М-1, где М+1≤n≤2*М+1, М+1≤Xn≤2*М+1.

(33)

  
   2.17. Третье основное решение
   Из-за условия (28) и Вывода 3 для чётных N2м (01) и нечётных N2м+1 (02) с М∈{3*Xn+1 | Xn≥1} (24) условием решения задачи будет второй вариант (19).
   Рассмотрим выражения для ферзей (09) с последовательностью {X>м} (11) при условии (19) для чётных N2м.
   Так как в (19) есть одно выражение для ферзей с положительной Sn=М-2, а отрицательные Sn≤(-3), необходимо чтобы в выражениях для ферзей с последовательностью {X>м} были значения отрицательных 0>Sn>-3. Для максимального Y2х-1=2*М-1 есть лишь два варианта взаимного расположения последовательностей {X>м} (11) и {Y2х-1} (13).
  
   Приведём последовательность расположения ферзей в верхней половине шахматного поля в виде выражений для ферзей (09), соответствующих последовательности {X>м} с одним отрицательным значением Sn= -1:

1) (3*Xn-2*М+3)∧Xn=(2*Xn-2*М+3)+(2*М-Xn-3),

где М+1≤n≤2*М-2, М+1≤Xn≤2*М-2;

2) (3*Xn-2*М-5)∧Xn=(2*Xn-2*М-5)+(2*М-Xn+5),

где 2*М-1≤n≤2*М, 2*М-1≤Хn≤2*М.

(34)

  
   Наименьшие ∑n как первого, так и второго выражения (34), при замене Xn на М будут больше ∑n=М+2 последнего выражения (19):

3*Xn-2*М+3=3*М+3-2*М+3=М+6>М+2, где М≥4

(35)

3*Xn-2*М-5=6*М-3-2*М-5=4*М-8>М+2, где М≥4

(36)

  
   Обозначим здесь Xn выражений (19) как Xn1. Так как у первого выражения (19) ∑n=3*Xn1+2, выясним к какому из множеств (16), (17) или (18) принадлежат ∑n первого и второго выражений (34), подставив для этого в выражения ∑n (34) значение М=3*Xn1+1, где Xn1≥1, из условия (2.17):

3*Xn-2*М+3=3*(Xn-2*Xn1)+1, где М+1≤Xn≤2*М-2, Xn1≥1

(37)

3*Xn-2*М-5=3*(Xn-2*Xn1-3)+2, где 2*М-1≤Xn≤2*М, Xn1≥1

(38)

  
   ∑n первого выражения (19) и ∑n (38) принадлежит одному множеству (18). ∑n (37) принадлежат множеству (17). Сравним наименьший ∑n (38) и наибольший ∑n первого выражения (19), выразив их через М:

3*Xn-2*М-5=3*(2*М-1)-2*М-5=4*(М-2)<3*Xn1+2=3*(М-1)+2 где 4≤М≤7

(39)

  
   ∑n (38) при М<8 будут совпадать с ∑n первого выражения (19). Условие (5) не соблюдается и выражения (34) не могут быть решением задачи.
  
   Приведём последовательность расположения ферзей в верхней половине шахматного поля в виде выражений для ферзей (09), соответствующих последовательности {X>м} с двумя отрицательными значениями Sn≥-2:

1) (3*Xn-2*М+5)∧Xn=(2*Xn-2*М+5)+(2*М-Xn-5),

где М+1≤n≤2*М-3, М+1≤Xn≤2*М-3;

2) (3*Xn-2*М-3)∧Xn=(2*Xn-2*М-3)+(2*М-Xn+3),

где 2*М-2≤n≤2*М, 2*М-2≤Xn≤2*М.

(40)

  
   Наименьшие ∑n как первого, так и второго выражения (40), при замене Xn на М будут больше ∑n=М+2 последнего выражения (19):

3*Xn-2*М+5=3*М+3-2*М+5=М+8>М+2, где М≥4

(41)

3*Xn-2*М-3=6*М-6-2*М-3=4*М-9>М+2, где М≥4

(42)

  
   Обозначим здесь Xn выражений (19) как Xn1. Так как у первого выражения (19) ∑n=3*Xn1+2, выясним к какому из множеств (16), (17) или (18) принадлежат ∑n первого и второго выражений (40), подставив для этого в выражения ∑n значение М=3*Xn1+1, где Xn1≥1, из условия (2.17):

3*Xn-2*М+5=3*(Xn-2*Xn1+1), где М+1≤Xn≤2*М-3, Xn1≥1

(43)

3*Xn-2*М-3=3*(Xn-2*Xn1-2)+1, где 2*М-2≤Xn≤2*М, Xn1≥1

(44)

  
   ∑n первого выражения (19) принадлежат множеству (18), ∑n (43) принадлежат множеству (16), а ∑n (44) принадлежат множеству (17). То есть все условия для решения задачи соблюдаются.
  
   При сложении выражений (40) и (19) получим выражения для ферзей для всего шахматного поля:

1) (3*Xn+2)∧Xn=(2*Xn+2)+(-Xn-2), где 1≤n≤М-1, 1≤Xn≤М-1;

2) (М+2)∧М=2+(М-2);

3) (3*Xn-2*М+5)∧Xn=(2*Xn-2*М+5)+(2*М-Xn-5),

где М+1≤n≤2*М-3, М+1≤Xn≤2*М-3;

4) (3*Xn-2*М-3)∧Xn=(2*Xn-2*М-3)+(2*М-Xn+3);

где 2*М-2≤n≤2*М, 2*М-2≤Xn≤2*М.

(45)

  
   Убрав из выражений для ферзей (45) ∑n и Sn, получим Третье основное решение задачи для чётных N2м (01) с М∈{3*Xn+1 | Xn≥1} (24), где Xn - значение ферзей по вертикали, Yn - значение ферзей по горизонтали:

1) Yn=2*Xn+2, где 1≤n≤М-1, 1≤Xn≤М-1;

2) Yn=2 при Xn=М;

3) Yn=2*Xn-2*М+5, где М+1≤n≤2*М-3, М+1≤Xn≤2*М-3;

4) Yn =2*Xn-2*М-3, где 2*М-2≤n≤2*М, 2*М-2≤Xn≤2*М.

(46)

  
  
   2.18. Четвёртое основное решение
  
   Рассмотрим выражения для ферзей (09) с последовательностью {X>м} (11) при условии (19) для нечётных N2м+1 (02) с М∈{3*Xn+1 | Xn≥1}.
   Вычисление здесь такое же, как в (2.17). Необходимо, чтобы в выражениях для ферзей (09) с последовательностью {X>м} (11) были значения отрицательных 0>Sn>-3. Для максимального Y2х-1=2*М+1 есть лишь два варианта взаимного расположения последовательностей {X>м} (11) и {Y2х-1} (13).
  
   Приведём последовательность расположения ферзей в верхней половине шахматного поля в виде выражений для ферзей (09), соответствующих последовательности {X>м} с одним отрицательным значением Sn= -1:

1) (3*Xn-2*М+1)∧Xn=(2*Xn-2*М+1)+(2*М-Xn-1), где М+1≤n≤2*М, М+1≤Xn≤2*М;

2) (2*М+2)∧2*М+1=1+2*М.

(47)

  
   Наименьшее ∑n первого выражения (47) при замене Xn на М и ∑n второго выражения (47) будут больше ∑n=М+2 последнего выражения (19):

3*Xn-2*М+1=3*М+3-2*М+1=М+4>М+2,

(48)

2*М+2>М+2

(49)

  
   Обозначим здесь Xn (19) как Xn1. Так как у первого выражения (19) ∑n=3*Xn1+2, выясним к какому из множеств (16), (17) или (18) принадлежат ∑n первого и второго выражений (47), подставив для этого в выражения ∑n значение М=3*Xn1+1, где Xn1≥1, из условия (2.18):

3*Xn-2*М+1=3*(Xn-2*Xn1-1)+2, где М+1≤Xn≤2*М , Xn1≥1.

(50)

2*М+2=3*(2*Xn1+1)+1, где Xn1≥1.

(51)

   ∑n (50) и ∑n первого выражения (19) принадлежат одному множеству (18). Сравним наименьший ∑n (50) и наибольший ∑n первого выражения (19), выразив их через М:

3*Xn-2*М+1=3*(М+1)-2*М+1=М+4 < 3*Xn1+2=3(М-1)+2 где М≥4

(52)

   ∑n (50) всегда будут совпадать с ∑n первого выражения (19). Условие (5) не соблюдается и выражения для ферзей (47) не могут быть решением задачи.
  
   Приведём последовательность расположения ферзей в верхней половине шахматного поля в виде выражений для ферзей (09), соответствующих последовательности {X>м} с двумя отрицательными значениями Sn≥ -2:

1) (3*Xn-2*М+3)∧Xn=(2*Xn-2*М+3)+(2*М-Xn-3),

где М+1≤n≤2*М-1, М+1≤Xn≤2*М-1;

2) (3*Xn-2*М-7)∧Xn=(2*Xn-2*М-7)+(2*М-Xn+7),

где 2*М≤n≤2*М+1, 2*М≤Xn≤2*М+1.

(53)

  
   Наименьшее ∑n первого и второго выражения (53) при замене Xn на М будут больше ∑n=М+2 последнего выражения (19):

3*Xn-2*М+3=3*М+3-2*М+3=М+6>М+2,

(54)

3*Xn-2*М-7=3*2*М-2*М-7=4*М-7>М+2, где М≥4

(55)

  
   Обозначим здесь Xn выражений (19) как Xn1. Так как у первого выражения (19) ∑n=3*Xn1+2, выясним к какому из множеств (16), (17) или (18) принадлежат ∑n первого и второго выражений (53), подставив для этого в выражения ∑n значение М=3*Xn1+1, где Xn1≥1, из условия (2.18):

3*Xn-2*М+3=3*(Xn-2*Xn1)+1, где М+1≤Xn≤2*М-1, Xn1≥1

(56)

3*Xn-2*М-7=3*(Xn-2*Xn1-3), где 2*М≤Xn≤2*М+1, Xn1≥1

(57)

   ∑n первого выражения (19) принадлежат множеству (18), ∑n (56) принадлежат множеству (17), а ∑n (57) принадлежат множеству (16). То есть все условия для решения задачи соблюдаются.
  
   При сложении выражений (48) и (19) получим выражения для ферзей для всего шахматного поля:

1) (3*Xn+2)∧Xn=(2*Xn+2)+(-Xn-2), где 1≤n≤М-1, 1≤Xn≤М-1;

2) (М+2)∧М=2+(М-2);

3) (3*Xn-2*М+3)∧Xn=(2*Xn-2*М+3)+(2*М-Xn-3),

где М+1≤n≤2*М-1, М+1≤Xn≤2*М-1;

4) (3*Xn-2*М-7)∧Xn=(2*Xn-2*М-7)+(2*М-Xn+7),

где 2*М≤n≤2*М+1, 2*М≤Xn≤2*М+1.

(58)

  
   Убрав из выражений для ферзей (58) ∑n и Sn, получим Четвёртое основное решение задачи для нечётных N2м+1 (02) с М∈{3*Xn+1 | Xn≥1} (24), где Xn - значение ферзей по вертикали, Yn - значение ферзей по горизонтали:

1) Yn=2*Xn+2, где 1≤n≤М-1, 1≤Xn≤М-1;

2) Yn=2 при Xn=М;

3) Yn=2*Xn-2*М+3, где М+1≤n≤2*М-1, М+1≤Xn≤2*М-1;

4) Yn=2*Xn-2*М-7, где 2*М≤n≤2*М+1, 2*М≤Xn≤2*М+1.

(59)

  
   2.19. Основное решение для всех N>3
   N-ое количество ферзей на шахматном поле со сторонами, равными N, где N≥4 расставляется при помощи набора Четырёх основных решений:
   1) Для N=2*М с М∈{3*Xn | Xn≥1} или М∈{3*Xn-1 | Xn≥1}, где Xn - значение ферзей по вертикали, Yn - значение ферзей по горизонтали:
   1) Yn=2*Xn, где 1≤n≤М, 1≤Xn≤М,
   2) Yn =2*Xn-2*М-1, где М+1≤n≤2*М, М+1≤Xn≤2*М.

(30)

  
   2) Для N=2*М+1 с М∈{3*Xn | Xn≥1} или М∈{3*Xn-1 | Xn≥1}, где Xn - значение ферзей по вертикали, Yn - значение ферзей по горизонтали:
   1) Yn=2*Xn, где 1≤n≤М , 1≤Xn≤М;
   2) Yn=2*Xn-2*М-1, где М+1≤n≤2*М+1, М+1≤Xn≤2*М+1.

(33)

  
   3) Для N=2*М с М∈{3*Xn+1 | Xn≥1}, где Xn - значение ферзей по вертикали, Yn - значение ферзей по горизонтали:
   1) Yn=2*Xn+2, где 1≤n≤М-1, 1≤Xn≤М-1;
   2) Yn=2 при Xn=М;
   3) Yn=2*Xn-2*М+5, где М+1≤n≤2*М-3, М+1≤Xn≤2*М-3;
   4) Yn=2*Xn-2*М-3, где 2*М-2≤n≤2*М, 2*М-2≤Xn≤2*М.

(46)

  
   4) Для N=2*М+1 с М∈{3*Xn+1 | Xn≥1} (24), где Xn - значение ферзей по вертикали, Yn - значение ферзей по горизонтали:
   1) Yn=2*Xn+2, где 1≤n≤М-1, 1≤Xn≤М-1;
   2) Yn=2 при Xn=М;
   3) Yn=2*Xn-2*М+3, где М+1≤n≤2*М-1, М+1≤Xn≤2*М-1;
   4) Yn=2*Xn-2*М-7, где 2*М≤n≤2*М+1, 2*М≤Xn≤2*М+1.

(59)

  
   Таким образом, если необходимо решение Задачи об N ферзях для последовательности натуральных чисел N≥4, основное решение состоит в последовательном применении следующего алгоритма:

1.

Первое основное решение (30)

2.

Второе основное решение (33)

3.

Первое основное решение (30)

4.

Второе основное решение (33)

5.

Третье основное решение (46)

6.

Четвёртое основное решение (59)

  
   2.20. Дополнительные и производные решения
   Для решения Задачи об N ферзях для N≥4 набор Четырёх основных решений является самым простым и исчерпывающим алгоритмом.
   Но существуют ещё набор дополнительных решений, дублирующих более простые основные решения или имеющих дополнительные условия.
  
   2.20.1. Первое дополнительное решение
   В (2.12) в Выводе 3 сказано, что второй вариант (19) может быть условием решения задачи для N c М=3*Xn-1, где Xn≥1. Но для такого М подходят и более удобные Первое (30) и Второе (33) основные решения. Путём приведенных в (2.17) и (2.18) вычислений для Третьего (46) и Четвёртого (59) основных решений можно вычислить, что Третье основное решение задачи (46) для чётных N2м (01) с М∈{3*Xn+1 | Xn≥1} является ещё и Первым дополнительным решением задачи для чётных N2м (01) c М∈{3*Xn-1 | Xn≥1}.
  
   2.20.2. Второе дополнительное решение
   В (2.17). было сказано, что из-за условия (28) для чётных N2м (01) с М∈{3*Xn+1 | Xn≥1} условием решения задачи может быть только второй вариант (19).
   Но если к условию М∈{3*Xn+1 | Xn≥1} добавить условие М∈{2*Xn1 | Xn1≥2}, то можно вернуться к первому варианту (14). Вернёмся и к Первому основному решению задачи (30).
   Сначала вычислим дополнительное условие для этого решения:

М=2*Xn1=3*Xn2+1=3*(2*Xn-1)+1, где Xn≥1, Xn2=2*Xn-1.

(60)

  
   Последовательность нечётных чисел {Y2х-1} (13), первый член которой совпадает с первым членом последовательности натуральных чисел {X>м} (11), на всём протяжении разобьём на пары. Внутри каждой пары произведём размен Y(2х-1)1 и Y(2х-1)2.
   Приведём выражения для ферзей (09) в верхней половине шахматного поля, соответствующей последовательности {X>м} (11):

1) (3*Xn-2*М+1)∧Xn=(2*Xn-2*М+1)+(2*М-Xn-1),

где n∈{М+2*Xn3-1 | 1≤Xn3≤(М/2)}, Xn∈{М+2*Xn3-1 | 1≤Xn3≤(М/2)};

2) (3*Xn-2*М+3)∧Xn=(2*Xn-2*М-3)+(2*М-Xn+3),

где n∈{М+2*Xn3 | 1≤Xn3≤(М/2)}, Xn∈{М+2*Xn3 | 1≤X3≤(М/2)}.

(61)

  
   Значения ∑n в (61) совпадают со значениями в ранее проведенных вычислениях. Согласно (50), ∑n первого выражения (61) принадлежат множеству (18). Согласно (37), ∑n второго выражения (61) принадлежат множеству (17). ∑n (14) принадлежат множеству (16). То есть все условия для решения задачи соблюдаются.
  
   При сложении выражений (61) и (14) получим выражения для ферзей для всего шахматного поля:

1) (3*Xn)∧Xn=2*Xn+(-Xn), где 1≤n≤М , 1≤Xn≤М;

2) (3*Xn-2*М+1)∧Xn=(2*Xn-2*М+1)+(2*М-Xn-1),

где n∈{М+(2*Xn3-1) | 1≤Xn3≤(М/2)}, Xn∈{М+(2*Xn3-1) | 1≤Xn3≤(М/2)};

3) (3*Xn-2*М+3)∧Xn=(2*Xn-2*М-3)+(2*М-Xn+3),

где n∈{М+2*Xn3 | 1≤Xn3≤(М/2)}, Xn∈{М+2*Xn3 | 1≤Xn3≤(М/2)}.

(62)

  
   Убрав из выражений для ферзей (62) ∑n и Sn, получим Второе дополнительное решение задачи для чётных N2м (02) с М∈{3*(2*Xn-1)+1 | Xn≥1}, где Xn - значение ферзей по вертикали, Yn - значение ферзей по горизонтали:

1) Yn=2*Xn, где 1≤n≤М , 1≤Xn≤М;

2) Yn=2*Xn-2*М+1,

где n∈{М+2*Xn3-1 | 1≤Xn3≤(М/2)}, Xn∈{М+2*Xn3-1 | 1≤Xn3≤(М/2)};

3) Yn=2*Xn-2*М-3,

где n∈{М+2*Xn3 | 1≤Xn3≤(М/2)}, Xn∈{М+2*Xn3 | 1≤Xn3≤(М/2)}.

(63)

  
  
   Для нечётных N2м+1 (02) при этих условиях задача не имеет решения из-за приведенного в (2.16) условия только S≥0 в выражениях для ферзей, соответствующих последовательности {X>m} (11).
  
   2.20.3. Третье дополнительное решение
   В (2.17). было сказано, что последовательность расположения ферзей в верхней половине шахматного поля в виде выражений для ферзей (09), соответствующих последовательности {X>м} с одним отрицательным значением Sn= -1 из-за того что ∑n (38) при М<8 будут совпадать с ∑n первого выражения (19), не может быть решением задачи. Следовательно, при М≥8 условия для решения задачи будут соблюдаться.
   При сложении выражений (34) и (19) получим выражения для ферзей для всего шахматного поля:

1) (3*Xn+2)∧Xn=(2*Xn+2)+(-Xn-2)), где 1≤n≤М-1, 1≤Xn≤М-1;

2) (М+2)∧М=2+(М-2);

3) (3*Xn-2*М+3)∧Xn=(2*Xn-2М+3)+(2*М-Xn-3),

где М+1≤n≤2*М-2, М+1≤Xn≤2*М-2;

4) (3*Xn-2*М-5)∧Xn=(2*Xn-2М-5)+(2*М-Xn+5),

где 2*М-1≤n≤2*М, 2*М-1≤Хn≤2*М.

(64)

  
   Убрав из выражений для ферзей (64) ∑n и Sn, получим Третье дополнительное решение задачи для чётных N2м (01) с М∈{3*Xn+1 | Xn≥3} (24), где Xn - значение ферзей по вертикали, Yn - значение ферзей по горизонтали:

1) Yn=2*Xn+2, где 1≤n≤М-1, 1≤Xn≤М-1;

2) Yn=2 при Xn=М;

3) Yn=2*Xn-2*М+3, где М+1≤n≤2*М-2, М+1≤Xn≤2*М-2;

4) Yn =2*Xn-2*М-5, где 2*М-1≤n≤2*М, 2*М-1≤Kn≤2*М.

(65)

  
   2.20.4. Производные решения
   Решения названы так, потому что они являются производными от основных и дополнительных решений задачи. Основаны они на том, что при соответствии определённому Xn для соседних нечётных Yn одного из множеств ∑n (16), (17) и (18), верно выражение:

Yn1= Yn2 ± 6 .

(66)

  
   Следовательно, в готовых выражениях для ферзей основных или дополнительных решений можно выбрать такие Yn, разность между которыми будет равна 6, и разменять их. При этом необходимо выполнить дополнительные вычисления, чтобы у каждого выражения для ферзей (09) был уникальный набор ∑n, Xn, Yn и Sn. Так, для выражений (45) производное решение получится при размене Yn=9 и Yn=3. Для выражений (58) производное решение получится при размене Yn=7 и Yn=1 . Возможны более сложные размены с тремя и более Yn, затрагивающие выражения для ферзей, у которых в результате размена ∑n станет принадлежать другому множеству из (16), (17) или (18), если такой ∑n не будет равен любому ∑n из этого множества в выражениях для ферзей как для нижней, так и для верхней половины шахматного поля. С ростом N растёт количество возможных разменов Yn.
   Но это требует дополнительных вычислений при уже готовых основных и дополнительных решениях и ничего нового не добавляет к Алгоритму решения Задачи об N ферзях.
 Ваша оценка:
Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список

Кожевенное мастерство | Сайт "Художники" | Доска об'явлений "Книги"