Шахматы и математика

[Almansor]

Математические задачи на шахматной доске

[Almansor]

Задача о восьми ферзях.
Расставить на доске восемь ферзей так,чтобы они не угрожали друг другу. Число решений.
Решения представляются в виде (135...),где указываются номера горизонталей в вертикалях,следующих по порядку.

[Crocodile]

Тебе что именно надо? Хочется узнать, знает ли тут народ паскаль/си/бэйсик, чтобы написать программу или хочется узнать, обладает ли тут народ здравым смыслом?:)

PS Ушел терзать паскаль

[Crocodile]

15863724

[Vanish]

Математические задачи на шахматной доске

Было дело .. тратил вчемя в пустую 18x13!

[Clap]

В пустую ничего и не когда не бывает

[Almansor]

Crocodile писал:

Тебе что именно надо? Хочется узнать, знает ли тут народ паскаль/си/бэйсик, чтобы написать программу или хочется узнать, обладает ли тут народ здравым смыслом?

PS Ушел терзать паскаль

Вы сами и ответили на свой вопрос. Кстати, для прграммирования этой задачи лучше подойдет язык Prolog. Программа будет изящнее и быстрее,да и язык своеобразный. Рекомендую по Прологу книгу Бартко. Там приведено схематичное решение. Ваше решение верно. А сколько еще м.б. решений?

[Almansor]

Clap, Вы правы.

[Almansor]

Кстати, задачей о восьми ферзях занимался великий математик Карл Фридрих Гаусс. Наверное, ему нравилось тратить время впустую. Он и нашел все ... решения. Тогда компьютеров и паскалей еще не было.

[Almansor]

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

[Almansor]

Где же решения задач. Кроме одного решения, которое привел Crocodile, других решений пока не вижу. И потом,где обещанные программы на паскале, си и прочая! Слабо?

[AzazeL]

Almansor пишет:Слабо?

Совсем не слабо вопрос времени: 8 вложенных циклов по 64 -
примерно 281,474,976,710,656 переборов влоб, если оптимизировать будет примерно 167,961,600,000,000 переборов и так как много отсекается при постановке, то цикл будет минимальной вложенности, что ещё ускорит процесс. поехали

[Almansor]

AzazeL пишет:

Almansor пишет:Слабо?

Совсем не слабо вопрос времени: 8 вложенных циклов по 64 -
примерно 281,474,976,710,656 переборов влоб, если оптимизировать будет примерно 167,961,600,000,000 переборов и так как много отсекается при постановке, то цикл будет минимальной вложенности, что ещё ускорит процесс. поехали

О каком времени вы говорите, времени выполнения программы? Предлагаю посмотреть в книгах по искуственному интелекту. Там рассматриваются такие алгоритмы. А без программы пробовали найти решение?

[AzazeL]

написания; выполняться на современных компах будет моментально
3 часа работы программиста и 100мсек работы программы и готово
Ответ:Похоже что 4 - один из них такой

Код: Выделить всё

@ - положение ферзя
# - клетка под ударом
0 - клетка свободна
  1 2 3 4 5 6 7 8
a # # # # # @ # #
b @ # # # # # # #
c # # # # @ # # #
d # @ # # # # # #
e # # # # # # # @
f # # @ # # # # #
g # # # # # # @ #
h # # # @ # # # #

Так и не понял как оформляется ответ - решил нарисовать.

Almansor пишет:Задача о часовых

Ответ: Похоже что 7 (возможных решений 3*4=12) (решено программно)

Код: Выделить всё

  1 2 3 4 5 6 7 8
a X # # # # # # #
b X # # # # # # #
c X # # # # # # #
d X # # # # # # #
e X # # # # # # #
f X # # # # # # #
g X # # # # # # #
h # # # # # # # #

  1 2 3 4 5 6 7 8
a X X # # # # # #
b X # # # # # # #
c X # # # # # # #
d X # # # # # # #
e X # # # # # # #
f X # # # # # # #
g # # # # # # # #
h # # # # # # # #

  1 2 3 4 5 6 7 8
a X # # # # # # #
b X # # # # # # X
c X # # # # # # #
d X # # # # # # #
e X # # # # # # #
f X # # # # # # #
g # # # # # # # #
h # # # # # # # #


[Almansor]

AzazeL пишет:написания; выполняться на современных компах будет моментально
3 часа работы программиста и 100мсек работы программы и готово
Ответ: 4 - один из них такой... Так и не понял как оформляется ответ - решил нарисовать.

Вы привели 1 решение и утверждаете, что их 4? Правильно я Вас понял? Число решений не 4,а больше. Далее решение оформляется так: если считать положения ферзей как { (1,y1), (2,y2), ... }, где цифры означают номера вертикалей,а y1,y2,...y8 - номера горизонталей, то опустив номера вертикалей, которые всегда будут одинаковые, получаем следующее оформление решения: y1,y2,y3,y4,y5,y6,y7,y8. Можно через пробел или через запятую. Думаю, что вы быстро внесете соответствующие изменения в программу. Желаю успеха!
Программу еще не смотрел. Кстати,я писал когда-то программу на 486 машине и программа тоже выполнялась моментально и выдавала все решения.
Программу посмотрел. А не много ли ферзей в задаче о часовых?

[AzazeL]

Almansor
решений то больше, но они все зеркальные (поворот доски на 0,90,180,270 град; отображение слева направо и сверху вниз): если я ничего не перепутал, то мой ответ 16 [на каждую сторону по 4(номально состояние, отображение вертикальное, отображение горизонтальное, отображение горизонтально-вертикальное)]
Про часовых...ээээ мозг в 4 ночи не думает моё решение было преведено для для случая когда под ударом должы быть все клетки, потом переделаю для всех свободных

[Almansor]

Azazel
Решений больше! 16 каких? Независимых?

[AzazeL]

Almansor пишет:Azazel
Решений больше! 16 каких? Независимых?

Зависимых производных от первого

Надеюсь ферзи без номерков... если нет тогда решений ууу 8^8*16=1024
Других путей решения не вижу, даже если очень подумать, посему лучше сдаться

[Almansor]

AzazeL пишет:

Almansor пишет:Azazel
Решений больше! 16 каких? Независимых?

Зависимых производных от первого

Надеюсь ферзи без номерков... если нет тогда решений ууу 8^8*16=1024
Других путей решения не вижу, даже если очень подумать, посему лучше сдаться

Тут несколько независимых решений. Остальные получаются поворотами и отражениями. Всего менее 100 решений. Ферзи конечно без номерков. Рано сдаетесь. Попробуйте еще.

[AzazeL]

Переделал задачу о 8 ферзях получилось что вариантов - 92:
42736851,52473861,35286471,36428571,57138642,46831752,36814752,53847162
57413862,41586372,36418572,47531682,64285713,64718253,17468253,68241753
62714853,47185263,58417263,48157263,27581463,17582463,25741863,42751863
57142863,64158273,51468273,52617483,63728514,27368514,73168524,51863724
15863724,36815724,63175824,75316824,73825164,53172864,25713864,36258174
61528374,83162574,28613574,57263184,36275184,62713584,37286415,63724815
42736815,71386425,16837425,38471625,63741825,74286135,46827135,26174835
24683175,36824175,63184275,84136275,48136275,26831475,72631485,36271485
47382516,48531726,35841726,42857136,57248136,74258136,82417536,72418536
51842736,41582736,52814736,37285146,31758246,82531746,35281746,35714286
52468317,63581427,58413627,42586137,46152837,63185247,53168247,42861357
63571428,64713528,47526138,57263148
Программа получилась красивая и коротакая, но выполняется оч. долго ~35сек

Задача про часовых
решение: перебор со случайной расстановкой фигур (оказался достаточно эффективным)
для 5 фигур были получены решения интуиция подсказывает, что есть решение для 4 и скорее всего оно одно

[Almansor]

Отлично, Azazel, Вы полностью решили задачу о восьми ферзях. Число решений правильно. Проверил выборочно случайным образом несколько решений. Остался маленький штрих. Сколько из 92 решений независимых.
Задача о ферзях-часовых.В общем случае задача о ферзях часовых является очень сложной. Оценки для минимального числа P(n) ферзей-часовых,охраняющих все свободные поля доски nxn:
n/2 - 1/2 <= P(n) <= 5n/8 + 16 sqrt(n). Число решений для доски 8х8 более 4000.
А кто еще решит эти задачи?