Восемь небьющихся ферзей

Однажды, я поспорил с товарищем на работе, предложив ему решить задачку: расставить на шахматной доске восемь ферзей так, чтобы ни один ферзь не бил другого. Товарищ честно упирался целый день в промежутках между работой. Потом сказал, что дома решит. На следующий день он ко мне не пришёл с решением. И потом тоже. А в конце недели, когда по работе мы с ним встретились, он между делом сказал: не решается.

- Решается. - Ответил я.
- А ты сам можешь решить?
- Наверное, надо попробовать.
- А давай на спор? Если ты решишь, то я тебе бутылку водки. И наоборот. Не решишь - ты мне.
- А если я не одно решение найду? - Спрашиваю я.
Товарищ обалдел от такой наглости постановки вопроса:
- Ну тогда я тебе столько бутылок отдам, сколько решений ты найдёшь!
- Согласен. - Сказал я. - По рукам?
- По рукам!
И мы пожали руки.

На следующей неделе я вручил товарищу вот эту самую картинку. Уникальных решений всего 12 штук. Все остальные позиции получаются поворотом доски.

Таким образом, товарищ проспорил мне 12 бутылок водки. Это как минимум. Можно было конечно распечатать все позиции (92 шт.), но я побоялся, что его инфаркт хватит. Впрочем, он мне мой выигрыш так и не отдал. Полностью. Всё очень просто. Он ограничился одной бутылкой.

Впрочем, я и не настаивал. Но честно скажу, что все позиции я нашёл сам. Опять же, не тупо подбирая путём прикладывания к доске фигурок. А с помощью компьютера и Бейсика. Написал программку. И получил все возможные решения в течение нескольких часов расчёта. А потом свёл их к 12-ти уникальным.

Ай да Мудman! Ай да сукин сын!



P.S.

Опять же, проникнитесь содержанием! Попробуйте найти решение сами. Хотя бы одно. И посмотрите, сколько это у вас займёт времени. Хотя, вы можете его вообще не найти… А я на компьютере получил за несколько часов ВСЕ!!! И было их 96 штук. Правда, четыре из них оказались совершенно одинаковыми и совпали с предыдущими. Если их найти и удалить, то останется 92 шт. Это и послужило толчком к пониманию, что позиции можно "вертеть" и "переворачивать". И тогда получатся дополнительные совпадения. А потом прикинул, что выгоднее по времени: писать ещё одну программу для вычёркивания одинаковых? Или просто наложить полиэтиленовую плёнку на экран, пометить фломастером точки, на которых стоят ферзи, и начать крутить во всех возможных поворотах доски по осям симметрии, и на глаз искать среди найденных 96 решений подходящие, чтобы вычеркнуть?

Я остановился тогда на втором решении.

Я поторопился. Ведь никогда заранее не знаешь, сколько потребуется времени на создание новой программы. И сколько уйдёт на её отладку. Каждый раз это загадка: как для самого программиста, так и для тех руководителей, которые возглавляют коллективы программистов, и должны планировать работу на многие месяцы вперёд.

Мозг человека, лежащий в основе создания этой тонкой материи – ПРОГРАММЫ, которая, тем не менее, приравнивается к промышленному продукту, такой непостоянный и ненадёжный инструмент, так подвержен любым воздействиям извне! Просто удивительно, что люди смогли развить промышленность до сегодняшнего состояния.

Это как спортивная форма игрока в снукере. Вчера он обыграл в матче чемпиона, а сегодня сам на себя не похож: всё валится из рук.

Извини, Господи. Но тебе следовало бы позаботиться о более надёжном проводнике и исполнителе твоего промысла. Правда, человек выкрутился. Создал механизмы, увеличивающие его мускульную силу. А затем по аналогии принялся за создание усилителя мозга.

Кто знает, если бы не слабость человеческая, не превратился ли бы человек в самодовольного ограниченного обезьяна. И может быть именно такая уязвимость человека заставляет его изобретать всё новые и новые усилители своих возможностей?

Но тогда у меня не было времени на такие размышления. И я пошло изрезал примитивный прозрачный пакетик на кусочки, и занимался верчением плёнки с отметками и сравнением на глаз подходящих диаграммок.

А сейчас я бы написал ещё одну программку. Я уже мысленно вижу, как она должна работать. Это просто. И нужно было сразу её вставить в первую программу, чтобы результатом работы были только уникальные позиции.

Теперь про повороты доски: разделите мысленно шахматную доску на четыре равных квадрата 4х4, и представьте, что через центр доски между клеток проходят оси координат Декартовой системы. Это обычная прямоугольная система, известная нам со времён средней школы, не надо пугаться умного названия. Вы не знали, что её придумал Рене Декарт? Вам забыли сказать в школе? Теперь знайте.

Хорошо бы ещё, чтобы вы знали, что Рене Декарт был мушкетёром в Нидерландах и воевал против Испании за независимость страны. Хотя летописцы уверяют, что он был больше озабочен математикой, чем военными действиями. И одним из развлечений молодых офицеров было разгадывание трудных задачек и каверзных загадок, которые они писали на городской стене нидерландского города Берды, и предлагали прохожим их решить!

Вот так раньше (более 400 лет назад) работал аналог местного Интернета в Нидерландах. А дату 10 ноября 1619 года весь мир считает моментом рождения современной математики. Именно в этот день Рене Декарт осознал свой метод, объединив геометрию с буквенной алгеброй, т.е. построение двух перпендикулярных координатных осей и задание положения любой точки на плоскости двумя числами от центральной точки начала координат. 10 ноября 2019 года исполнится ровно 400 лет со дня рождения современной математики. Слава Рене Декарту, мушкетёру и математику. Ура, товарищи!   

Однако продолжим.

Если мы пронумеруем квадраты в порядке слева направо и снизу вверх, то шахматная доска будет описана четырьмя числами так:

34
12

Теперь можно поворачивать доску по осям симметрии: по горизонтали, по вертикали, и вдоль обеих диагоналей. А затем добавить к ним ещё три позиции путём последовательного поворота первоначальной по часовой стрелке на 90 градусов. Как видно, получается 8 позиций из одной первоначальной.

34  12  43  24  31  13  21  42
12  34  21  13  42  24  43  31

Не следует заниматься расстановкой чисел в произвольном порядке, ибо число возможных сочетаний из четырёх цифр 1, 2, 3, 4 равно не восьми, а 24.

4 * 3 * 2 * 1 = 24

Но остальные варианты представляют из себя «поломанную доску». И нам не подходят.

Получается, что из 12 уникальных позиций, которые мною приведены на картинке, поворотами можно получить в восемь раз больше, т.е. 96 шт.

12 * 8 = 96

Опять я веду вас к той же мысли, что и в прошлый раз. Программирование – это огромный резерв увеличения производительности труда. Вы могли бы потратить годы, если бы искали вручную решение этой задачи. И так бы и умерли, не решив её до конца. А при помощи самого примитивного языка программирования и любого компьютера, вам (при наличии умения писать программы) удалось бы решить задачу в общем виде за очень непродолжительное время. Я думаю, что при упорстве, вам хватило бы нескольких дней. Плюс ещё несколько дней на сами вычисления компьютера. Я беру с запасом, поскольку мы по определению договорились, что задача должна быть решена на любом компьютере. То есть даже на первом IBM PC.

Вот и сравните: годы и неделю! Коэффициент получается: (5 лет * 365 дней + 1) / 7 дней = 260

Это значит, что производительность труда человека повышается на 26 000% . Двадцать шесть тысяч процентов! Это как Слон против Муравья. Именно поэтому я называю людей, которые не понимают этой простой истины – варварами XXI века.

Представьте, сколько радости получил бы Рене Декарт, если бы мы из нашего времени закинули ему на 400 лет назад ноутбук на солнечных батареях, снабженный хотя бы Free DOS и Бейсиком с подробным описанием, как им пользоваться. Боюсь только, что его бы святая инквизиция сожгла на костре, вместе с «бесовской машинкой».

Впрочем, Рене Декарта и так взялись преследовать тёмные церковные служители. (Клянусь. Я не переправлял ему ноутбука. Это кто-то другой!) И ему пришлось бежать. Хорошо, что в то время шведская королева Христина увлеклась математикой. И решила, что ей нужен самый лучший учитель. И ей посоветовали нашего героя мушкетёра. Тут летописи умалчивают подробности жизни Декарта при дворе Христины. Известно лишь, что в 1650 году зимой Рене сильно простудился и 9 февраля того же года умер от простуды. Вероятнее всего это был грипп, с его осложнениями.

Товарищи, теплее одевайтесь в холодную погоду. Держите ноги в тепле. И если что, пейте горячий сладкий чай с лимоном и малиновым вареньем. Простуда – это коварная зараза. Особенно, если вы не привыкли к суровому местному климату северной широты.



7:38:23 02.04.2019          1CF3787CFD0



P.S. Поскольку соловья баснями не кормят, то я решил написать заново (только для вас!) программу для решения задачки расстановки восьми ферзей. Вот что у меня вышло на Бейсике в самых примитивных конструкциях. Язык использован в диалекте Qbasic.exe (MS-DOS QBasic Version 1.1 Microsoft, 1987-1992). И хотя 150 лет ещё не прошло с момента создания этого чуда инженерной мысли XX-века! Но я рискну предположить, что данная программа уже является собственностью всего человечества. Поэтому, надеюсь, что именитая фирма (с её богатейшим владельцем) не потащит меня в турма, и не станет пытать электрическим током, и утоплением в тазу. За то, что я имел наглость использовать их продукт без их согласия. И признался в этом публично. Да ещё и призвал всех читателей присоединиться ко мне.

А окрылён я такой надеждой по причине простого логического рассуждения. Всё созданное фирмой Microsoft (да и всеми остальными фирмами на Земле), всё это (и всё, что будет создано ими в будущем!) создано на деньги их пользователей. Поэтому, по меньшей мере странно, что всё это принадлежит не этим самым пользователям. Не находите? А?


ЛИСТИНГ ПРОГРАММЫ

DIM A(8, 8) AS INTEGER
DIM B(8, 2) AS INTEGER
DIM T(8, 2) AS INTEGER
DIM C(100, 8, 2) AS INTEGER

CLS
PRINT DATE$, TIME$

'Initializaciy baz&
PRINT "Initializaciy baz&"
FOR k% = 1 TO 100
FOR i% = 1 TO 8
FOR j% = 1 TO 2
C(k%, i%, j%) = 0
NEXT j%
NEXT i%
NEXT k%

m% = 0 'Shethik kolihestva zapisei v baze
n% = 0 'Shethik kolihestva naidenn&x rewenii

'Initializaciy koordinat
PRINT "Initializaciy koordinat"
FOR i% = 1 TO 8
FOR j% = 1 TO 2
B(i%, j%) = 0
T(i%, j%) = 0
NEXT j%
NEXT i%

'Initializaciy doski
PRINT "Initializaciy doski"
FOR i% = 1 TO 8
FOR j% = 1 TO 8
A(i%, j%) = 0
NEXT j%
NEXT i%

'Osnovnoi cikl poiska reweniy
FOR k% = 1 TO 8
i% = k%
FOR j% = 1 TO 8
IF A(i%, j%) = 0 THEN
R1% = i%
R2% = j%
GOSUB Proverka
IF R3% = 0 THEN
A(i%, j%) = 1 'Postavit` figuru
B(k%, 1) = i% 'Soxranit` koordinatu figur& k%
B(k%, 2) = j%
GOTO Temp00
END IF
END IF
Obratka:
NEXT j%

'Na doske net mesta dly figur& k%
Oherednoi:
k% = k% - 1
IF k% = 0 THEN GOTO Konec
i% = B(k%, 1)
j% = B(k%, 2)
A(i%, j%) = 0
B(k%, 1) = 0
B(k%, 2) = 0
GOTO Obratka

Temp00:
NEXT k%

'Vse figur& rasstavlen&
'=======================
n% = n% + 1 'Naideno ewe odno rewenie

FOR R0% = 1 TO 8 'Soxranit` koordinat&
T(R0%, 1) = B(R0%, 1)
T(R0%, 2) = B(R0%, 2)
NEXT R0%
R4% = 0

IF m% > 0 THEN
FOR R5% = 1 TO 7 'Proverit` na nalihie v baze poluhennogo varianta reweniy

FOR R1% = 1 TO m% 'Perebor vsex zapisei baz&
R4% = 0
FOR R2% = 1 TO 8 'Sravnenie s kajdoi
x% = C(R1%, R2%, 1)
y% = C(R1%, R2%, 2)
IF A(x%, y%) = 1 THEN
R4% = R4% + 1
IF R4% = 8 THEN
PRINT "Rewenie"; n%; " Povorot ="; R5% - 1; " => Baza(m%) ="; R1%
GOTO Metka
END IF
END IF
NEXT R2%
NEXT R1%

FOR R0% = 1 TO 8 'Ubrat` Q s doski
x% = B(R0%, 1)
y% = B(R0%, 2)
A(x%, y%) = 0
NEXT R0%

IF R5% = 1 THEN 'Povernut` koordinat& po gorizontali
   FOR R0% = 1 TO 8
   B(R0%, 1) = 9 - T(R0%, 1)
   B(R0%, 2) = T(R0%, 2)
   NEXT R0%
ELSEIF R5% = 2 THEN 'Povernut` koordinat& po vertikali
   FOR R0% = 1 TO 8
   B(R0%, 1) = T(R0%, 1)
   B(R0%, 2) = 9 - T(R0%, 2)
   NEXT R0%
ELSEIF R5% = 3 THEN 'Povernut` koordinat& po glavnoi diagonali
   FOR R0% = 1 TO 8
   B(R0%, 1) = T(R0%, 2)
   B(R0%, 2) = T(R0%, 1)
   NEXT R0%
ELSEIF R5% = 4 THEN 'Povernut` koordinat& po vtoroi diagonali
   FOR R0% = 1 TO 8
   B(R0%, 1) = 9 - T(R0%, 2)
   B(R0%, 2) = 9 - T(R0%, 1)
   NEXT R0%
ELSEIF R5% = 5 THEN 'Povernut` koordinat& na 90 gradusov po hasovoi
   FOR R0% = 1 TO 8
   B(R0%, 1) = T(R0%, 2)
   B(R0%, 2) = 9 - T(R0%, 1)
   NEXT R0%
ELSEIF R5% = 6 THEN 'Povernut` koordinat& na 180 gradusov po hasovoi
   FOR R0% = 1 TO 8
   B(R0%, 1) = 9 - T(R0%, 1)
   B(R0%, 2) = 9 - T(R0%, 2)
   NEXT R0%
ELSEIF R5% = 7 THEN 'Povernut` koordinat& na 270 gradusov po hasovoi
   FOR R0% = 1 TO 8
   B(R0%, 1) = 9 - T(R0%, 2)
   B(R0%, 2) = T(R0%, 1)
   NEXT R0%
END IF

FOR R0% = 1 TO 8 'Rasstavit` Q po doske
x% = B(R0%, 1)
y% = B(R0%, 2)
A(x%, y%) = 1
NEXT R0%

NEXT R5%

FOR R1% = 1 TO m% 'Perebor vsex zapisei baz&
R4% = 0
FOR R2% = 1 TO 8 'Sravnenie s kajdoi
x% = C(R1%, R2%, 1)
y% = C(R1%, R2%, 2)
IF A(x%, y%) = 1 THEN
R4% = R4% + 1
IF R4% = 8 THEN
PRINT "Rewenie"; n%; " Povorot ="; R5% - 1; " => Baza(m%) ="; R1%
GOTO Metka
END IF
END IF
NEXT R2%
NEXT R1%

Metka:
FOR R0% = 1 TO 8 'Vosstanovit` koordinat& i Q na doske
x% = B(R0%, 1)
y% = B(R0%, 2)
A(x%, y%) = 0
NEXT R0%

FOR R0% = 1 TO 8
B(R0%, 1) = T(R0%, 1)
B(R0%, 2) = T(R0%, 2)
NEXT R0%

FOR R0% = 1 TO 8
x% = T(R0%, 1)
y% = T(R0%, 2)
A(x%, y%) = 1
NEXT R0%

'Uiti na perebor i rasstanovku Q po doske
IF R4% = 8 THEN
GOTO Oherednoi
END IF
END IF

m% = m% + 1 'Sdvinut` shethik zapisei vpered
IF m% > 100 THEN GOTO Konec

PRINT "N'";
PRINT USING "##"; n%;
PRINT " M'";
PRINT USING "##"; m%;
FOR k% = 1 TO 8
C(m%, k%, 1) = B(k%, 1) 'Zanesti zapis` v bazu
C(m%, k%, 2) = B(k%, 2)
PRINT " Q";
PRINT USING "#"; k%;
PRINT "(";
PRINT USING "#"; B(k%, 1);
PRINT ",";
PRINT USING "#"; B(k%, 2);
PRINT ")";
NEXT k%
PRINT
GOTO Oherednoi 'Uiti na perebor i rasstanovku Q po doske

'Perebor okonhen
Konec:
PRINT
PRINT n%, m%, DATE$, TIME$
PRINT
PRINT "-----------------   T H E   E N D   -----------------"
PRINT
SYSTEM

'Poisk pereseceniy figur
Proverka:
R3% = 0 'Zanulit` priznak pereseceniy

'Perebor verxnei casti vertikali
FOR R4% = 1 TO R1% - 1
IF A(R4%, R2%) <> 0 THEN 'Esli naideno peresecenie
R3% = 1 'Ustanovit` priznak pereseceniy
GOTO Temp01
END IF
NEXT R4%

'Perebor nijnei casti vertikali
FOR R4% = R1% + 1 TO 8
IF A(R4%, R2%) <> 0 THEN 'Esli naideno peresecenie
R3% = 1 'Ustanovit` priznak pereseceniy
GOTO Temp01
END IF
NEXT R4%

'Perebor levoi casti gorizontali
FOR R5% = 1 TO R2% - 1
IF A(R1%, R5%) <> 0 THEN 'Esli naideno peresecenie
R3% = 1 'Ustanovit` priznak pereseceniy
GOTO Temp01
END IF
NEXT R5%

'Perebor pravoi casti gorizontali
FOR R5% = R2% + 1 TO 8
IF A(R1%, R5%) <> 0 THEN 'Esli naideno peresecenie
R3% = 1 'Ustanovit` priznak pereseceniy
GOTO Temp01
END IF
NEXT R5%

'Perebor verxnei levoi casti pervoi diagonali
R4% = R1%
R5% = R2%
DO UNTIL R4% = 0 OR R5% = 0
IF A(R4%, R5%) <> 0 THEN 'Esli naideno peresecenie
R3% = 1 'Ustanovit` priznak pereseceniy
GOTO Temp01
END IF
R4% = R4% - 1
R5% = R5% - 1
LOOP

'Perebor nijnei pravoi casti pervoi diagonali
R4% = R1%
R5% = R2%
DO UNTIL R4% = 9 OR R5% = 9
IF A(R4%, R5%) <> 0 THEN 'Esli naideno peresecenie
R3% = 1 'Ustanovit` priznak pereseceniy
GOTO Temp01
END IF
R4% = R4% + 1
R5% = R5% + 1
LOOP

'Perebor verxnei pravoi casti vtoroi diagonali
R4% = R1%
R5% = R2%
DO UNTIL R4% = 0 OR R5% = 9
IF A(R4%, R5%) <> 0 THEN 'Esli naideno peresecenie
R3% = 1 'Ustanovit` priznak pereseceniy
GOTO Temp01
END IF
R4% = R4% - 1
R5% = R5% + 1
LOOP

'Perebor nijnei levoi casti vtoroi diagonali
R4% = R1%
R5% = R2%
DO UNTIL R4% = 9 OR R5% = 0
IF A(R4%, R5%) <> 0 THEN 'Esli naideno peresecenie
R3% = 1 'Ustanovit` priznak pereseceniy
GOTO Temp01
END IF
R4% = R4% + 1
R5% = R5% - 1
LOOP

Temp01:
RETURN

END