Снова задачка по языку Pascal

[Yurij]

Доброе время суток Гуру Pascalя.
Очень бы хотелось найти вот такую задачку:
Надо написать функцию, которая на шахматной доске расставит 12 коней так, чтобы они покрывали все другие клетки.
Как расставить фигуры, я знаю:
b6
c2
c3
c5
c6
d3
e6
f3
f4
f6
f7
g3
Проблема - это запрограмить как можно легче... без графики и других наворотов.
Большое спасибо!

[Novoross]

Без графики, это только если представить шахматную доску в виде двумерной матрицы размером 8х8. Только не пойму почему функцию, а не процедуру, функция после своего выполнения должна возвращать какое то значение: например функция сложения двух чисел A+B возвращает значение С-сумма. Если писать процедуру, то приблизительно код тела процедуры выглядит так:
for i:=1 to 8 do begin
for j:=1 to 8 do begin
doska[i,j]:=0;
end;
end;
doska[2,6]:=1;
doska[3,2]:=1;
...и т.д.

массив типа Boolean
только сначала обнуляешь весь массив, а затем проставляешь единички в нужных местах doska[2,6]:=1; где в квадратных скобках: 2-значение по Х(в нашем случае это буква B на доске), а 6-значение по Y.
P.S. в свое время писал программу на Pascale в графическом режиме-шахматная доска, при щелке мыши по клетке, ставится ферзь, и показываються все поля находящиеся под боем, если интересует, исходный код остался.

[dr-evil]

Novoross
раскрою тайну, понятие процедуры условно, это фактически та же функция, но возвращающая нулевое значение (null, nil, etc)

Не совсем верно описанна задача, тоесть известно положение коней на доске, но нужен алгоритм перебора который мог бы его найти.
Сама идея такая:
в одной четверти доски расстовляются фигуры(кони) по 3, причём крайние ряды можно "отбросить"
* * * *
* * х х
* * х *
* * * *
это если брать левый нижний угол как а-1.
Затем необходимо эту часть доски скопировать на другие три четверти, предварительно повернув относительно правого верхнего угла на 90 градусов. Таким образом получится вся доска и перебор соответственно можно ограничить только одной четвертью. Вся проблема как это реализовать на паскале.
Спасибо

[XPEHOMETP]

1. Если возиться только с одной четвертью, пропускается возможность "закрыть" некоторые клетки с соседней четверти.

2. А без этой возможности задача не решается. На отдельно взятую четверть доски, чтобы накрыть все свободные клетки, нужно ЧЕТЫРЕ коня. И на всю доску - 16.

[topknot]

Очевидно, преподаватель хочет, чтобы ты решил задачу с помощью рекурсии.

[Naked]

Погодь, слушай, а можно вот так:
* * * *
* * * *
K * * K
K * * K
На этой картинке побиты все поля...четыре раза повторяем картинку и получаем все поле... единственно - не побиты ТЕ поля, на которых стоят кони...
Если это правильно - то не понимаю задачи, может нужно указать все существующие кобинации? тогда берем матрицу 4*4, делаем там всевозможные комбинации, при которых побиты все поля (можно и перебором - это будет не долго), реализовывать это можно например так: ставим в клетку значение 2, все которые побиты ей - 1, оставшиеся - 0, в оставшиеся в любое место ставим соответственно опять 2 и т.д....В итоге получаем набор таких полей размера 4*4 со всеми побитыми полями, тогда чтобы воспроизвести поле достаточно склеить все мелкие поля, одновременно их крутя-вертя, тогда получатся все-возможные комбинации... Либо я что-то не так понял

[topknot]

The_naked:
Либо я что-то не так понял

а каким конем побить правую верхнюю клетку твоего рисунка. И коней будет не 12 если сложить четыре таких куска как у тебя, это уже в теме обсуждалось. Это, имхо, хрестоматийный пример задачи, которая решается рекурсией. Можно поискать материал по ключевым словам "задача про 8 ферзей" если "12 коней" не помогают.

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

[Naked]

вот, кстати про 8 ферзей:
__http://recursio.narod.ru/quins.htm
Вообще в яндексе по запросу 8 ферзей кучу всего выдает, а реализация твоих 12 коней такая же будет (приблизительно, как и 8 ферзей )
таксь, а про коней читаем здесь:
__http://www.sciteclibrary.ru/cgi-bin/yabb/Printpage.cgi?board=golovolomki&num=1141055727

[leon534]

Перебор ИМХО штука несложная, но завершения работы такой проги долго ждать. Первого коня можно разместить 64 способами. Если он размещен, то 2-го уже 63 способами, третьего 62-мя и т.д.
Игого получается 64*63*62*61*60*...*53 вариантов. Так сказать Це из 64 по 12. Нехилое число получится И считать эти варианты машина долго будет ...
А какие поля пробивает конь, стоящий на клетке (x,y) определить тоже несложно. Кони ходят буквой Г, следовательно подойдут клетки с координатами:
(x-1,y-2), (x-2,y-1),(x+1,y-2),(x+2,y-1),
(x+2,y+1), (x+1,y+2),(x-1,y+2),(x-2,y+1)
при условии, что все координаты принадлежат шахматной доске, т.е. больше нуля и меньше 9.
Количество переборов можно, наверное сократить, учитывая, что поскольку каждого коня должен бить какой-нибудь другой, то выбирать очередного достаточно лишь из клеток с координатами этой восьмерки.
Ну и сократить перебор на первом шаге (не просматривать все 64 комбинации) можно, используя следующее соображение - клетку а1 должен кто-либо пробивать. А это может быть конь либо b3 либо c2.

Задачка понравилась, решил просто написать всю программу поиска вариантов.
Вот что получилось на Delphi7.
Находит ваш вариант за несколько секунд, методом перебора вариантов и выбора наилучшего.