2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Knights Tours
Сообщение02.04.2015, 03:45 
Аватара пользователя


01/06/12
787
Adelaide, Australia
Решил разобраться как результаты выглядят. Вот результаты для закрытых туров для min(m,n)<=15:
http://picpaste.com/closedResults-onfhAOzc.png

А вот для открытых туров:
http://picpaste.com/openResults-2ggAV0AS.png

Закономерность между площадью доски и лучшей длиной тура вполне линейная и регулярная:
http://picpaste.com/openAnalysis-EMRD3S4r.png

Похоже что результаты "гладкие" и я не вижу очевидных пробелов. Всё это говорит что ваши результаты уже хорошие.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение02.04.2015, 08:31 


02/05/10
26
dimkadimon в сообщении #999178 писал(а):
Если у вас есть результаты полного перебора для квадратных досок (до n=31), то почему нельзя сделать полный перебор для остальных досок? Или для квадратных досок задачу легче решить?

Извините, не точно выразился. Белым для прямоугольных досок и желтым для квадратных. Дальше там просто диагональ выделена светло серым цветом. Так что для квадратных досок проверено не дальше чем в OEIS.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение05.04.2015, 10:59 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Новый шедевр от Bernard Lemaire.
Замкнутый маршрут на доске 12х12.
В БД есть 13 маршрутов на этой доске, все они длиной 86 ходов, кроме одного (неизвестного автора) принадлежат alexBlack. Чёртова дюжина маршрутов и ни одного симметричного! Самого красивого тура и нет :-)

Bernard прислал мне тур в такой записи:
a1-b3-a5-c4-b6-a8-c7-b9-d8-f7-e9-g8-h10-f9-g11-e10-c9-d11-b10-a12

Здесь первые 19 ходов, которые затем повторяются трижды с поворотом на 90 градусов.
Великолепный тур! Хотя длина его всего 76 ходов.

Изображение

Я отправила ему этот рисунок и спросила, хочет ли он, чтобы это было внесено в БД. Жду ответ.
Как я понимаю, он не сам оцифровывает свои маршруты и вносит их в БД.

Восхищаюсь, как люди могут придумывать такие замысловатые конфигурации без всяких программ.

Да, чуть не забыла: а форумчане могут сочинить нечто подобное? :wink:
Может быть, на доске 12х12 можно сделать замкнутый симметричный маршрут и подлиннее, чем 76 ходов.
А что сказал бы в ответ господин компьютер? :D

-- Вс апр 05, 2015 12:20:09 --

А замкнутый симметричный маршрут на доске 19х19 от Bernard Lemaire уже внесён в БД сегодня.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение05.04.2015, 19:15 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Улучшать так улучшать :D

На доске 9х9 Bernard Lemaire что-то плохо нарисовал, наверное, это у него была разминка.
Такой малюсенький маршрутик, всего 16 ходов. Улучшила с ходу, не задумываясь, аналогично его туру, точно такая же симметрия (трижды поворот начального пути на 90 градусов).
Сверху тур Bernard Lemaire, внизу - мой (32 хода).

Изображение

Может быть, ещё кто-нибудь улучшит.

-- Вс апр 05, 2015 20:41:45 --

Хе-х... конечно, это у него была разминка, вот тут он хорошо нарисовал :lol:

Изображение

(с сайта http://www.mayhematics.com/t/2nq.htm )

Здесь 40 ходов, а в БД alexBlack представлено такое смешное решение в 16 ходов.
Ну, есть уже и чуть-чуть получше, моё в 32 хода.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение05.04.2015, 20:54 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Для доски 12х12 на указанном сайте представлено аж 5 вариантов решения, все они длиной 76 ходов (один из вариантов показан тут, чуть выше). Это всё симметричные замкнутые маршруты.
Автор сайта пишет в комментарии к этим турам:

Цитата:
Could an 84-move solution still be possible?

Хорошая задача, господа :wink:

 Профиль  
                  
 
 Re: Knights Tours
Сообщение06.04.2015, 05:46 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Bernard Lemaire прислал список своих замкнутых симметричных маршрутов, которые любезно разрешил внести в БД alexBlack.
Я не буду приводить весь список, маршруты скоро появятся в БД, смотрите их там.
Отмечу только те маршруты, которые по мнению автора подлежат улучшению:

Цитата:
such tour for the 17x17 board with L=176 ,e=0.61 <=
such tour for the 20x20 board with L=244, e=0.61 <=
such tour for the 24x24 board with L=380, e=0.66 <=

Это важная информация.
Ну, и выше был отмечен ещё маршрут на доске 12х12 (L=76), который по мнению автора сайта может иметь лучшее решение в 84 хода.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение11.04.2015, 08:53 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Bernard Lemaire прислал открытку музыкальную - поздравляет с наступающим праздником :D и новый вариант замкнутого симметричного маршрута на доске 13х13 (L=96):

Код:
a1-b3-a5-c4-b6-d5-c7-a6-b8-a10-c11-b9-d10-c8-e9-d7-f6-e8-f10-d9-e11-c10-d12-b11-a13

Я ещё не нарисовала этот маршрут.
Ну, думаю, alexBlack введёт его в БД (он тоже получил эту запись маршрута).

Кстати, если у кого есть вопросы по оцифровке решений, не стесняйтесь, спрашивайте. Там вроде всё очень просто, но это для тех, кто уже десятки маршрутов нарисовал и оцифровал.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение13.04.2015, 08:03 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nataly-Mak в сообщении #1002544 писал(а):
Код:
a1-b3-a5-c4-b6-d5-c7-a6-b8-a10-c11-b9-d10-c8-e9-d7-f6-e8-f10-d9-e11-c10-d12-b11-a13

Я ещё не нарисовала этот маршрут.

Этот маршрут нарисовала и ввела в БД, смотррите
тут.
Красивый вариант, мне этот больше нравится, чем первый.

Но Bernard неутомим! Прислал ещё варианты маршрутов на досках 14х14 и 23х23.
Ну, на доске 14х14 просто вариант без увеличения длины, а вот на доске 23х23 с улучшением, аж 376 ходов (было 344). Здорово!
Но рисовать это долго, он, как всегда, запись прислал:

Код:
a1-c3-a5-c4-b6-a8-c7-b9-a11-c10-b12-a14-c1"-b15-a17-c16-b18-a20-c21-b19-d20-f21-e19-g20-i21-h19-j20-L21-k19-m20-o21-n19-p20-o18-n16-p17-r16-s14-q15-r13-s11-q12-r10-p11-n12-o10m11-L9-k7-m8-L6-n7-m9-o8-n10-p9-o11-q10-s9-r11-t10-s12-r14-t13-s15-r17-t16-s18-r20-t19-s21-q20-p18-r19-s17-q18-o17-p19-q21-o20-p22-n21-L20-m22-k21-i20-j22-h21-f20-g22-e21-c20-d22-b21-a23

Подождать надо, когда Джордж на своём сайте нарисует :D

 Профиль  
                  
 
 Re: Knights Tours
Сообщение14.04.2015, 09:02 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nataly-Mak в сообщении #1003278 писал(а):

...а вот на доске 23х23 с улучшением, аж 376 ходов (было 344). Здорово!
Но рисовать это долго, он, как всегда, запись прислал:

Код:
a1-c3-a5-c4-b6-a8-c7-b9-a11-c10-b12-a14-c1"-b15-a17-c16-b18-a20-c21-b19-d20-f21-e19-g20-i21-h19-j20-L21-k19-m20-o21-n19-p20-o18-n16-p17-r16-s14-q15-r13-s11-q12-r10-p11-n12-o10m11-L9-k7-m8-L6-n7-m9-o8-n10-p9-o11-q10-s9-r11-t10-s12-r14-t13-s15-r17-t16-s18-r20-t19-s21-q20-p18-r19-s17-q18-o17-p19-q21-o20-p22-n21-L20-m22-k21-i20-j22-h21-f20-g22-e21-c20-d22-b21-a23


Всё-таки нарисовала, было очень интересно. До конца не верилось, что это всё повернётся три раза на 90 градусов. Но повернулось! Фантастичный маршрут! Такие невероятные вложения!
Попробуйте заставить компьютер нарисовать такой маршрут :wink:

Изображение

В записи начального пути, присланной Бернаром, есть неточности (опечатки).

Джордж уже тоже поместил маршрут на своей страничке.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу Пред.  1, 2

Модераторы: maxal, Karan, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group