Здрасти, нужно написать прогу, которая на шахматной доске раставит 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 коней, но как их не ставь остануться свободные клетки. среди не угловых