2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Путешествие коня по 64 клеткам
Сообщение13.11.2009, 17:20 
Может ли конь, побывать на каждой клетке шахматной доски размером 8x8 ровно один раз и последним ходом возвратиться в исходную позицию? Решить такую же задачу для доски 7x7.
_______________________
Есть идея что с каждой парой ходов кол-во черных и белых клеток уменьшается.

 
 
 
 Re: Путишествие коня по 64 клеткам
Сообщение13.11.2009, 17:37 
Аватара пользователя
Идея неплохая. Чётным или нечётным ходом возвращается конь на исходную клетку? Это для второй задачи.
Наверное, каждый программер писал такую программу.

 
 
 
 Re: Путишествие коня по 64 клеткам
Сообщение13.11.2009, 18:49 
Аватара пользователя
usersname в сообщении #261642 писал(а):
Может ли конь, побывать на каждой клетке шахматной доски размером 8x8 ровно один раз и последним ходом возвратиться в исходную позицию? Решить такую же задачу для доски 7x7.
_______________________
Есть идея что с каждой парой ходов кол-во черных и белых клеток уменьшается.
Идея верная.

Пусть изначальная позиция коня - белое поле. Посчитайте, сколько должно остаться незатоптанных конём клеток каждого цвета после 63 ходов в первом случае и после 48 ходов во втором случае.

 
 
 
 Re: Путишествие коня по 64 клеткам
Сообщение13.11.2009, 18:59 
Чётное количество ходов в замкнутом пути - это только необходимое условие существования решения. Другими словами, мы точно можем сказать, что задача неразрешима для доски 7х7, а разрешима ли она для доски 8х8 - вопрос отдельный.

 
 
 
 Re: Путишествие коня по 64 клеткам
Сообщение13.11.2009, 19:19 
Аватара пользователя
Maslov в сообщении #261670 писал(а):
а разрешима ли она для доски 8х8 - вопрос отдельный.

http://mathworld.wolfram.com/KnightsTour.html
http://en.wikipedia.org/wiki/Knight's_t ... 7s_Theorem
:)

 
 
 
 Re: Путишествие коня по 64 клеткам
Сообщение13.11.2009, 19:25 
Да все прекрасно знают, что доска 8х8 таким образом обходится :) - хотелось просто обратить внимание на то, что чётного количества клеток для существования решения не достаточно.

 
 
 
 Re: Путишествие коня по 64 клеткам
Сообщение13.11.2009, 19:47 
Аватара пользователя
Просто в случае $8 \times 8$ проще явно найти замкнутый маршрут, чем доказать его существование.

А вообще для существования замкнутого маршрута на доске $m \times n$, где $m \leqslant n$, необходимым и достаточным является выполнение следующих трёх условий:
1) $mn$ не является нечётным числом, большим $1$;
2) при $1<m<5$ обязательно $m=3$, $n>9$
3) при $m=1$ обязательно $n=1$

Разбор некоторых отдельных случаев см. по второй ссылке выше.

 
 
 
 Re: Путишествие коня по 64 клеткам
Сообщение13.11.2009, 20:00 
Droog_Andrey в сообщении #261696 писал(а):
Просто в случае $8 \times 8$ проще явно найти замкнутый маршрут, чем доказать его существование.
А как его найти? :)
Мы же в разделе "Математика", а не "Программирование".

 
 
 
 Re: Путишествие коня по 64 клеткам
Сообщение13.11.2009, 20:30 
Идея простая - шагайте пока шагается и метки ставьте с номерами ходов на те клетки, где были - если не куда шагать и маршрут не завершен - возвращайтесь на шаг назад - там делайте другой ход (всего вариантов ходов 8 для клеток центре доски, занумеруйте ходы, чтоб не повторяться) и тд. Рекурсивная процедура описана в интернете - поищите.

 
 
 
 Re: Путишествие коня по 64 клеткам
Сообщение13.11.2009, 22:17 
Yu_K в сообщении #261718 писал(а):
Идея простая - ... Рекурсивная процедура описана в интернете - поищите.
Спасибо, я знаком с этой простой идеей. Но мне кажется, что когда задача предлагается в разделе "Математика", то предполагается не компьютерный перебор, а какой-то другой способ решения. Может быть, я ошибаюсь.

 
 
 
 Re: Путишествие коня по 64 клеткам
Сообщение13.11.2009, 22:29 
Так или иначе шахматная доска рассматривается как граф. А шагать по доске как в темноте не имеет смысла.

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group