Перебор: Обход ферзём всех полей доски

[Nicholas]

Помогите, пожалуйста, с алгоритмом программы: нужно найти минимальное количество ходов, за которое ферзь может обойти все поля шахматной доски.
(имеется ввиду, что за один ход из a в b ферзь пробегает и по всем клеткам между a и b)
Само собой тут рекурсия, ибо полный перебор.
Если записывать все ходы из каждой точки - очень долго получится, должен же быть способ быстрее.


Вот тут рисунок (в самом низу).

[Nerazumovskiy]

а начальное положение ферзя задано?

[Nicholas]

В общем неважно, но пусть будет как на картинке -- левый нижний угол.

[Nerazumovskiy]

Ну вот мне лично кажется что если задачка написать программку то надо так или иначе использовать перебор достаточно большого количества вариантов.
Запоминать все ходи естественно нет надобности.
Можно полагать что когда ми делаем ход по какому то направлению то нужно дойти до конца строчки. (тоесть ходи должны бить длинными).
Так как квадрат фигура симетричная то можна запоминать только половину вариантов.

На первом ходу у ты можеш пойти двумя вариантами либо по диагонали либо вправо(причом до упора). Оказываешся в следующем угле. По диагонали смысл идти врятли есть(я полагаю што самопересечений не должно бить, я думаю што ето можно допустить если сказать что за пределы доски мы не имеем права вилазить) тогда надо опять двигатса снова куда то в сторону и снова искать путь без самопересечений. и.т.д.
Тоесть надо запоминать варианти ходов и прорабативать их рекурсивно. Ветку рекурсии стоит обривать если ти не можеш двигатся без самопересечений. Потом просто сравнить все результаты. Думаю их будет не очень много.
Правда тут возникают проблемы с тем что может случится так что ти заполниш ровно половину квадрата (как на том ресунке, но решение етой проблемы там нарисовано).
З.Ы. мысли вслух.

[Фома]

Nerazumovskiy писал(а):

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

Интересно мыслите. Пишите еще.

З.Ы. Предлагаю новый оператор: gotoкуда-то;

[Nerazumovskiy]

Будете смеятсо но я так и ниразу не смог написать goto (в С) чтоб не получить похвалы от компилятора. Как результат всегда пишу без него (хороший вкус програмиривания так сказать).

[Фома]

Nerazumovskiy писал(а):

Будете смеятсо

Не буду. Больше не могу.

[Pavia]

Nicholas
Полный перебор это куча вариантов. 8^64.
Лучше возьмем жадный алгоритм будем делать наимболее большии ходы не в плане длины а в плане пройденных еще не помеченных клеток..
Допустим ферзь стоит в начале координат тогда заполним по спирали.
получим 14 ходов.
Если ферзь стоит не в начале координат, а где либы. то тут тоже идем к стенки и заполняем по спирали делая наибольшии ходы перебирая по часовой стрелке. опять 14. Это будет наименьшее число ходов остается даказать это. Мы можем сделать только один ход по 8 клеток 2 хода по 7 клеток 2 по 6 и тд. до 3 по три и два по три.
8+7*2+6*2+5*2+4*2+3*2+2*3=64 клетки

[Nicholas]

По спирали 15 получается.

[Nerazumovskiy]

если хочеш написать таки програму то можеш писать перебором(с учотом всех приведущих, идей которие тебе понравятся ) но теперь ти знаеш что у тебя потолок ето 15 ходов а значит перебор будет не таким уже и большим 2^{45} ходов(и ето если делать в лоб,
а можна и меньше(если учесть преведущие мысли)