Здрасти, нужно написать прогу, которая на шахматной доске раставит 12 коней так, чтобы все клетки доски были "битые" (под ударом).
Надо использовать двухмерный массив!
Результат должен быть примерно таким:
| 0 | 0 | * | * | k | 0 | * | k
| k | * | * | * | k | k | * | 0
| * | 0 | * | k | * | * | * | *
| 0 | * | k | * | * | * | * | 0
| * | 0 | * | * | * | 0 | k | *
| 0 | * | 0 | * | * | k | 0 | *
| * | 0 | * | * | * | * | 0 | *
| k | 0 | k | 0 | * | 0 | k | 0

Где * - поле под ударом, k - конь, 0 - не битое поле (их не должно быть!)
Спасибо!

По-моему, надо сначала составить схему удара одним конём и "протаскивать" её по полю. Насчёт расположения: кони не должны быть рядом с краем доски (тк бьют на расстояние в клетку от себя) и, скорее всего, должны быть группами. Наверняка будет симметрия, т.е. можно сделать только часть работы и отразить через плоскость симметрии.
Вы уверены, что это возможно?
Вот "заливка" одним конём:


Это сообщение отредактировал(а) III.nfo - 25.2.2006, 19:18

А потом перебором коней по всей доске проставь.

на, например, перебором...
правда, придется перебирать 64^12 (ну чуть меньше из-за того, что два коня на одной клетке стоять не могут), а отсечений тут пока не видно...
...
ага... можно попробовать разделить задачу на две: растановка коней, которые бьют черные клетки, и тех, которые - белые...
тогда будет что-то вроде 2*(32^6), что уже обозримо...

Модератор: пользуемся кнопкой Код - тогда и подсветка будет, и отступы сохранятся...

Добавлено @ 20:51
Довольно эффективный алгоритм.Предполагается, что расположение коней в квадратах одинаково с точностью до поворота на 90 градусов по часовой стрелке. Значения заносятся в двумерный массив. Находим все сочетания из 16 по 3 и для каждого ставим сразу 4 коня, т.е. всего 560 комбинаций. Доска разбивается на четыре части.

Это сообщение отредактировал(а) maxim1000 - 25.2.2006, 22:49

и как, находит? (не запускал, под рукой Паскаля нету)
вообще-то из симметрии доски совсем не следует, что расположение коней будет симметричным
из этого следует, что если какое-торешение есть, то будутеще три решения - повороты на 90 градусов
а то, что все они совпадут, т.е. оно будетсимметричным относительно такого поворота, может быть, а может и не быть
если какое-то решение так находится - прекрасно
просто могут быть пропущены асимметричные решения...

Ну во-первых просто 32*31*30*29*28*27 = 652 458 240 (что уже сносно) - потому как потом любой вариант расстановки по черным полям комбинируется с любым вариантом расстановки по белым полям (которые получаем любым способом, например отразить относительно любой оси).
Во-вторых, отсечения все-таки будут (например обработка проверки что осталось полей менее чем 8 * число оставшихся к расстановке коней, и еще кой-какие мелочи) - проверять программно быстрее, чем считать заведомо тухлые варианты (при условии что надо найти все расстановки).

maxim1000,
Вот сделал клетки какие бьет конь!

Моя прога работает. Не парьте мозги. Вычисляет расположение коней.

Кстати, я кандидат в мастера спорта по шахматам. Про поворачивание доски всё у меня правильно, maxim1000.

Забейте, задача решена.

пойдем от конца. Нам надо чтоб все клетки были битые. Начнем с cамых трудных - ето угловые клетки(a1,а2,b1,b2 и симетричные им)

Так как нельзя поставить коня так чтоб он бил сразу две угловые клетки, мы вынуждены разделить коней (для каждого угла).
Теперь у нас получилось три коня на угол.

чтоб перекрыть 4 клетки 3-мя конями, надо чтоб как минимум две клетки были в битой зоне одного коня.
Такая позиция только одна(а3) на каждый угол. т.е 4 коня из 8 имеют однозначно единственое положение.

Oсталось по два на угол и по две клетки(такие как а1,b2) Для каждой из етих клеток существует три позиции коня (например для клетки а1 ето а1,c2,b3). т.е. когда поле занято конём или когда оно битое.

можно расмотреть следующее поле.(а3) Тогда мы узнаем что возможных позиций только 2 для каждого коня.

Осталось перебрать в каких из етих позиций перекрываются все остальные клетки.

ДобренькийПапаша,
А у тебя в углах не битые клетки остались и у тебя не видно где кони стоят! МОжешь помочь исправить это?

mes,
Нарисуй визуально если тебе не трудно!

задача не решаема это не сложно доказать.


для того чтобы закрыть четыре четверки, состоящии из четырех угловых клеток нужно 16 коней

esperant0, это ты сказал не подумавши. Погорячился.

нужно 12 коней, но как их не ставь остануться свободные клетки. среди не угловых

B3, C3, C4, C6, C7, D6, E3, F2, F3, F5, F6, G6

[QUOTE=Dov,27.2.2006, 23:42]


Решение у этой задачи есть. Если расставить три коня так что они бьют все четыре угловые клетки, то из 3х возможных вариантов,два (зеркальных) являются решением. При заполнение трех оставшихся углов нужно учитывая правило поворота, расставить коней в те же позиции.
Сейчас нет времени для более подробного обяснения.
Попозже постараюсь более подробно.

да промазал я.

Dov,
Вот теперь прогу надо написать, которая так раставит!
Добавлено @ 08:58
Dov,
У тебя не все клетки под ударом!

интересно какие??

Алгоритм программы такой:
1. Раставляешь коней (любое кол-во) так, чтобы 4 угловые клетки
во всех 4-х углах были биты.
Получится следуещее:
Потом убираешь последователно в каждом углу одного "лишнего" ( того, при убирании которого, все клетки всего поля будут биты)

В конце концов получится "рисунок" как у Dova
При таком алгоритме кол-во проверок минимально (в удачном случае находит решение после 8 хода, при неудачном с 20 хода)

Конечно, не все. На некоторых 'лошади' стоят(8 штук). Если хочешь поставить их под бой тоже, прийдётся добавить ущё 2 коника.


Ну, так дерзай, proger. Видишь, и ник у тебя подходящий.

Proger, я написал прогу, там на первой странице. Если немного не так, тогда подправь.

ДобренькийПапаша, плагиатом занимаешься, нехорошо. А может быть тебя зовут А.К.Сахаров из Барнаула?

Dov, Спасибо за помощь!

mes, А прогу нАПИСАТЬ МОЖЕШЬ, А ТО У МЕНЯ НЕ ПОЛУЧАЕТСЯ!

proger, вот, тупо перевёл на С++ ту прогу, которая на паскале.
Видок у неё ещё тот, но зато работает. А красоту сам наведёш, если захочешь.

Вариантов для написания проги очень много. В зависимости от того что тебе надо.
Думаю, что тебе важно, чтоб компьютер перебрал все возможные варианты независимо от того являются ли они симметричными.

Чтоб проверять только те позиции, которые имеет смысл, я разбил задачу на две части.
Первая: Как известно конь не может бить угловые клетки в разных углах. Таких клеток 16. (4*4)
Вопрос: Могут ли бить 12 коней ети 16 клеток?


Каждая клетка может бить "бита" не более чем с девяти позиций: (8 битых +1 когда клетка занята конём)
Конь может бить две соседние клетки, только если они рассположены по диагонали




По результату программы видно, что минимальное кол-во коней для перекрытия угловых клеток нужно 12 (нас это устраивает)
4 Коня имеют 5 позиций,
другие 4 - 3позиции,
и еше 4 Коня могут находится только в 1 положении, значит расставлять нужно только 8 коней.

На основе етих данных я создал, список позиций, и методом перебора проверил есть ли среди вариантов такие,
которые бы били бы все клетки.



В результате два варианта (зеркальных) где группа из трех коней, симметрична относительно поворота.
При проверке во второй части перебираются 50625 позиций.

Если учитывать симметрию относительно поворота, (т.е для одного угла) , то сократится приблизительно до 15 позиций.

Надеюсь тебе ето поможет.


P.S. Прошу прощение за малое кол-во комментариев и неформатированный код.

Это сообщение отредактировал(а) mes - 9.3.2006, 18:37

Присоединённый файл ( Кол-во скачиваний: 29 )
 Koni.zip 46,76 Kb

Спасибо!