Информационно-развлекательный портал Глазова

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

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

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

15863724

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

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

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

Crocodile писал:

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

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

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

Clap, Вы правы.

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

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

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

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

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

AzazeL пишет:

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

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

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

написания; выполняться на современных компах будет моментально
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 # # # # # # # #


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

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

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

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

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

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

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

AzazeL пишет:

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

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

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

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

Переделал задачу о 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 и скорее всего оно одно

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