Uncrossed knight's tours.

open knight's tour of length 287 on chessboard 20x19

Author: Makarova
Date (d/m/y): 08/08/2011
Path: 1616161613 2475252546 1616161616 1745252525 2525247616 1616161616 1613867525 2525252525 2525252525 2835461616 1616161616 1616161616 1616167425 2525252525 2525252525 2525252524 7616161616 1616161616 1616161616 1645382525 2525252525 2525252525 7683161616 1616161616 7425252525 2525471616 1616161645 2525742316 1616161
invariants
M=(n-2)(m-2)-C = 19
k=C/nm = 0.755
Q=C-[(n-3)(m-3)+10] = 5
symmetric

n=19; m=	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
C	20	35	52	67	84	99	114	129	146	159	176	191	205	221	237	253	268	287	302	317	334	351	366	385	402	416	436	453	467
M	-3	-1	-1	1	1	3	5	7	7	11	11	13	16	17	18	19	21	19	21	23	23	23	25	23	23	26	23	23	26
k	.35	.46	.55	.59	.63	.65	.67	.68	.70	.70	.71	.72	.72	.73	.73	.74	.74	.76	.76	.76	.76	.77	.77	.78	.78	.78	.79	.79	.79
Q	10	9	10	9	10	9	8	7	8	5	6	5	3	3	3	3	2	5	4	3	4	5	4	7	8	6	10	11	9

2 paths for chessboard 20x19

length	author	date (d/m/y)		path
287	Makarova	08/08/2011		1616161613 2475252546 1616161616 1745252525 2525247616 1616161616 1613867525 2525252525 2525252525 2835461616 1616161616 1616161616 1616167425 2525252525 2525252525 2525252524 7616161616 1616161616 1616161616 1645382525 2525252525 2525252525 7683161616 1616161616 7425252525 2525471616 1616161645 2525742316 1616161
285	Makarova	03/10/2011		7474742316 8317477474 7461838383 3831674774 7474747425 7683838383 8383833838 3835281747 4747474774 7474747474 7474761383 8383838383 8383383838 3838383816 4747474747 4747747474 7474747474 7182538383 8383838338 3838383838 3867524747 4747477474 7474761383 8383833838 3816474747 7474747471 8253838338 3838674775 23383

Uncrossed closed knight's tours

m\n	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
3			4	6	6	6	6	10	10	10	10	14	14	14	14	18	18	18	18	22	22	22	22	26	26	26	26	30	30
4		4	6	8	10	12	14	16	18	20	22	24	26	28	30	32	34	36	38	40	42	44	46	48	50	52	54	56	58
5	4	6	8	12	14	18	20	22	24	28	30	34	34	38	40	44	46	48	50	54	56	60	60	64	66	70	72	74	76
6	6	8	12	12	18	22	24	28	32	36	38	42	46	50	54	58	62	66	70	74	78	82	86	90	94	98	102	106	110
7	6	10	14	18	24	26	32	36	42	44	48	54	58	62	66	72	74	80	84	88	94	98	100	106	112	114	118	124	128
8	6	12	18	22	26	32	36	42	46	52	58	64	70	76	80	88	92	100	106	112	116	124	128	136	142	148	152	160	164
9	6	14	20	24	32	36	42	50	56	60	68	74	80	86	94	98	106	114	118	126	132	136	144	150	156	162	168	174	180
10	10	16	22	28	36	42	50	54	64	70	78	84	92	100	104	110	116	124	132	140	146	152	160	166	172	180	186	194	200
11	10	18	24	32	42	46	56	64	70	80	86	94	102	110	114	118	132	140	142	150	152	160	176	184	190	198	204	212	216
12	10	20	28	36	44	52	60	70	80	86	96	104	114	124	130	138	150	158	164	178	184	192	202	208	216	230	232	238	256
13	10	22	30	38	48	58	68	78	86	96	106	112	124	136	142	154	166	168	174	194	192	200	224	222	228	254	252	260	282
14	14	24	34	42	54	64	74	84	94	104	112	124	134	148	158	166	180	190	198	190	214	230	218	238	244	248	266	272	278
15	14	26	34	46	58	70	80	92	102	114	124	134	148	156	172	182	194	190	204	230	220	238	248	254	270	280	282	296	304
16	14	28	38	50	62	76	86	100	110	124	136	148	156	172	182	188	208	220	218	240	258	250	272	296	288	302	336	318	342
17	14	30	40	54	66	80	94	104	114	130	142	158	172	182	200	210	214	230	248	252
18	18	32	44	58	72	88	98	110	118	138	154	166	182	188	210	228	236
19	18	34	46	62	74	92	106	116	132	150	166	180	194	208	214	236	256	270
20	18	36	48	66	80	100	114	124	140	158	168	190	190	220	230		270	288	300
21	18	38	50	70	84	106	118	132	142	164	174	198	204	218	248			300	322	332
22	22	40	54	74	88	112	126	140	150	178	194	190	230	240	252				332	360	370
23	22	42	56	78	94	116	132	146	152	184	192	214	220	258						370	396	406
24	22	44	60	82	98	124	136	152	160	192	200	230	238	250							406	434
25	22	46	60	86	100	128	144	160	176	202	224	218	248	272									476
26	26	48	64	90	106	136	150	166	184	208	222	238	254	296										520
27	26	50	66	94	112	142	156	172	190	216	228	244	270	288											564	568	600
28	26	52	70	98	114	148	162	180	198	230	254	248	280	302											568	612
29	26	54	72	102	118	152	168	186	204	232	252	266	282	336											600		662
30	30	56	74	106	124	160	174	194	212	238	260	272	296	318														714
31	30	58	76	110	128	164	180	200	216	256	282	278	304	342															768

Uncrossed open knight's tours

m\n	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
3	2	4	5	6	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
4	4	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59
5	5	7	10	14	16	19	22	25	28	31	34	37	40	43	45	49	52	55	58	61	63	67	70	73	76	79	81	85	88
6	6	9	14	17	21	25	29	32	35	39	43	47	51	55	59	63	67	71	75	79	83	87	91	95	99	103	107	111	115
7	8	11	16	21	24	30	35	39	44	49	54	59	64	69	74	79	84	89	94	99	104	109	114	119	124	129	134	139	144
8	9	13	19	25	30	35	42	47	53	59	63	69	75	81	87	93	99	105	111	117	123	129	135	141	147	153	159	165	171
9	10	15	22	29	35	42	47	55	61	67	74	81	87	93	102	108	114	123	129	135	144	150	156	165	171	177	186	192	198
10	11	17	25	32	39	47	55	61	69	76	83	92	101	105	113	122	129	136	143	153	160	167	177	184	191	201	208	215	225
11	12	19	28	35	44	53	61	69	76	87	94	101	110	119	126	137	146	153	164	173	180	191	200	207	218	227	234	245	254
12	13	21	31	39	49	59	67	76	87	94	103	113	121	129	141	151	159	169	178	188	199	206	218	229	235	248	259	265	278
13	14	23	34	43	54	63	74	83	94	103	113	125	134	145	154	165	176	185	195	209	216	228	242	249	261	275	282	294	308
14	15	25	37	47	59	69	81	92	101	113	125	135	144	156	170	178	191	202	213	222	237	249	258	273	285	294	309	321	330
15	16	27	40	51	64	75	87	101	110	121	134	144	158	169	181	193	205	218	230	243	256	269	282	295	308	321	334	347	360
16	17	29	43	55	69	81	93	105	119	129	145	156	169	183	195	207	221	235	247	261	275	289	303	317	331	342	359	373	382
17	18	31	45	59	74	87	102	113	126	141	154	170	181	195	211	223	237	253	265	281	295	309	326	340	354	371	385	399	416
18	19	33	49	63	79	93	108	122	137	151	165	178	193	207	223	238	253	268	282	300	317	328	345	362	375	391	407	420	439
19	20	35	52	67	84	99	114	129	146	159	176	191	205	221	237	253	268	287	302	317	334	351	366	385	402	416	436	453	467
20	21	37	55	71	89	105	123	136	153	169	185	202	218	235	253	268	287	302	319	337	353	369	388	407	423	441	457	476	495
21	22	39	58	75	94	111	129	143	164	178	195	213	230	247	265	282	302	319	337	357	374	393	410	429	448	465	483	505	520
22	23	41	61	79	99	117	135	153	173	188	209	222	243	261	281	300	317	337	357	375	392	412	433	450	471	484	507	528	544
23	24	43	63	83	104	123	144	160	180	199	216	237	256	275	295	317	334	353	374	392	414	432	452	473	492	513	534	555	576
24	25	45	67	87	109	129	150	167	191	206	228	249	269	289	309	328	351	369	393	412	432	455	475	495	517	537	559	577	603
25	26	47	70	91	114	135	156	177	200	218	242	258	282	303	326	345	366	388	410	433	452	475	499	519	541	564	584	609	630
26	27	49	73	95	119	141	165	184	207	229	249	273	295	317	340	362	385	407	429	450	473	495	519	542	561	586	607	631	661
27	28	51	76	99	124	147	171	191	218	235	261	285	308	331	354	375	402	423	448	471	492	517	541	561	588	615	635	659	686
28	29	53	79	103	129	153	177	201	227	248	275	294	321	342	371	391	416	441	465	484	513	537	564	586	615	638	662	687	711
29	30	55	81	107	134	159	186	208	234	259	282	309	334	359	385	407	436	457	483	507	534	559	584	607	635	662	689	717	740
30	31	57	85	111	139	165	192	215	245	265	294	321	347	373	399	420	453	476	505	528	555	577	609	631	659	687	717	743	768
31	32	59	88	115	144	171	198	225	254	278	308	330	360	382	416	439	467	495	520	544	576	603	630	661	686	711	740	768	798

Last changes

author	date (d/m/y)	size	path
Scott Z. Zhang	04/07/2016	14x12 (104) closed	2325225225 2552552547 1611611616 6166167425 2252252552 5525783161 1616616616 4383382525 6524761174 5683161746 1818
Scott Z. Zhang	04/07/2016	15x13 (124) closed	2325225225 2525525525 4716116116 1616616616 7425225225 2525525525 7831611616 1661661643 8252252525 6524761116 1646164257 4761381647 1818
Scott Z. Zhang	04/07/2016	15x13 (124) closed	2325225225 2525525525 4716116116 1616616616 7425225225 2525525525 7831611616 1661661643 8252252525 6524761747 4761383832 1616574747 1818
Scott Z. Zhang	04/07/2016	20x12 (156) closed	2325225225 2252252552 5525471611 6116166166 1661661674 2522522522 5225255255 2578316116 1661661661 6616438252 2522522525 6524761116 5611661646 1642125522 5676857217 461818
Scott Z. Zhang	04/07/2016	16x14 (144) closed	2325225225 2255255255 2547161161 1611661661 6616742522 5225225525 5255257831 6116116616 6166164382 5225225525 6524761111 6561165617 4522522558 6164257618 1818
Scott Z. Zhang	04/07/2016	20x12 (158) closed	2325225225 2252252552 5525471611 6116166166 1661661674 2522522522 5225255255 2578316116 1661661661 6616438252 2522522525 6524767613 2116616616 4616421252 2567568572 17461818
Scott Z. Zhang	04/07/2016	18x13 (154) closed	2325225225 2252525525 5254716116 1161616616 6166167425 2252252252 5255255257 8316116161 6616616616 4382522522 5252565247 6111616616 5742225255 7476123161 6657471386 1818
Scott Z. Zhang	04/07/2016	16x14 (148) closed	2325225225 2255255255 2547161161 1611661661 6616742522 5225225525 5255257831 6116116616 6166164382 5225225525 6524761111 6616561745 2222555858 2411666524 76181818
Scott Z. Zhang	04/07/2016	17x15 (172) closed	2325225225 2252552552 5525471611 6116116166 1661661674 2522522522 5255255255 2578316116 1161661661 6616438252 2522525525 6524761111 6166165617 4522225255 5882541161 6665252835 2576161818 18
Scott Z. Zhang	04/07/2016	19x14 (180) closed	2325225225 2252255255 2552547161 1611611661 6616616616 7425225225 2252255255 2552578316 1161166166 1661661643 8252252252 2552565247 6111166166 1656174522 2252255561 6164782252 4116616665 2476181818
Scott Z. Zhang	04/07/2016	19x14 (180) closed	2325225225 2252255255 2552547161 1611611661 6616616616 7425225225 2252255255 2552578316 1161166166 1661661643 8252252252 2552565247 6111166166 1656174522 2252255574 7164782522 4116661665 2476181818
Derek Kisman	01/06/2018	18x18 (228) closed	1611611611 6183525525 5255252252 2522523861 6616616616 1161161116 1647161325 2555255255 2522522522 3866166166 1611611611 1422525525 7525211611 3461752554 6166161161 3161655255 2522522528 8247446616 6166161161 1855255255 2522522522 4574256761 66166166

new knight's tour

Author:

to 10 comma-separated paths:

You can specify up to 10 paths, separated by commas

Each character in path is the direction from the last waypoint:

Sample path: 7531:

In parentheses are given by recurrence. The number after the closing parenthesis indicates the number of repetitions. For example 75 (85)9 3 (14)9 1 is translated into 75 858585858585858585 3 141414141414141414 1.

For symmetric open tours:

a) If the last character of the path is an asterisk, the path is repeated again in reverse order. For example 74774761383* is translated into 74774761383 38316747747.

b) If the last character of the path it is '>', the path is repeated again in reverse order without the last character. For example 1661661835225> is translated into 166166183522 5 225381661661.

Links:

Downloads

p:19032 05/04/2015 Off-line version of this base (Windows only) (knighttoursbase.zip) (712.8 Кб, loaded: 12996 )

Comments

12.09.2011 09:53 Наталия

К симметричным маршрутам на полях 9х9 и 13х13 нужно приписать: ext. from R. Merson 15x15.
Маршрут на поле 12х16 введён как ext. from svb 20x24, нет автора (не умещается всё в поле для ввода). То же самое в маршруте на поле 19х27, введён как ext. from A. Chernov 11x19.

12.09.2011 10:21 alexBlack

Исправил ...

13.09.2011 09:49 Наталия

Я не попыталась всё ввести в поле для автора...
К несимметричным маршрутам 15х15, 23х23 и 31х31 надо добавить: ext. from Eric Bainville 7x7.
Может быть, вы расширите поле для ввода автора?.. Если это возможно.

13.09.2011 07:39 svb

Мне кажется, что до тех пор, пока нет программной реализации получения нового полученного кем-то маршрута, лучше ставить имя последнего \"реализатора\". В противном случае мы рискуем окончательно запутаться.

13.09.2011 08:04 alexBlack

Для 15х15, 23х23 и 31х31 информацию в скобках добавил.

Давайте придерживаться формата для имени, который уже есть в базе: указываем свое имя и, если нужно, в скобках описание маршрута, от которого получен результат. Например, Makarova (ext.from R.Merson 15x15).
Поле для ввода я увеличил, 40 символов должно хватить.

Выложил новую версию off-лайн базы. В этой версии в таблицах заголовки (где указаны m и n) являются переключателями. Щелчок мышки переключает отображение в таблицах количества/коэффициентов k и M.

13.09.2011 09:54 svb

Спасибо за новую версию off-лайн базы! Стало очень наглядно.

13.09.2011 11:39 Наталия

Алексей, вы видели все маршруты, которые я вводила сегодня как ext.from svb ...? Их было несколько, два или три, не помню точно.
По поводу \"реализотора\". У меня нет никакой путаницы. Если я делаю простой перенос маршрута с шагом 8 и ничего при этом не дорабатываю, то пишу, что маршрут получен от такого-то маршрута. Если же далаю доработки угловых фрагментов, то пишу своё имя. Всё очень просто.

14.09.2011 12:52 Наталия

Базу скачала. Спасибо. Все коэффициенты теперь видно.
Вот нашла один маршрут: поле 24х31, введён как ext.from svb 16x23, без имени автора. Ещё вроде один был. Если вы не увидите его, я позже найду.

14.09.2011 07:59 alexBlack

Исправил 24x31, 20x25, 12x17

15.09.2011 03:07 Наталия

Алексей, никак не могу ввести маршрут с таким авторством:
Makarova (ext.from svb 15x22)
Выходит ошибка:
Error: Invalid characters in name. Allowed only \"0-9 a-z . _ \"
Пробовала скопировать имя автора в вашем примере и ввести, ничего не дало, та же ошибка.

15.09.2011 03:15 Наталия

Ввела этот маршрут (поле 23х30) со своим авторством, без добавки на маршрут svb. Так сразу ввелось. Что я пишу в добавке не так?
Добавьте, пожалуйста, ссылку на маршрут svb (15х22).

15.09.2011 07:15 alexBlack

Забыл добавить скобочки в список допустимых символов. 23x30 исправил.

17.09.2011 09:05 Наталия

Алексей, я задала на форуме вопрос о тривиальных маршрутах. Сложно работать, когда на вопросы не отвечают. Вводить или нет тривиальные несимметричные маршруты?

17.09.2011 02:59 alexBlack

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

17.09.2011 05:02 Наталия

Но откуда же мне знать, почему вы не отвечаете? Вы вчера вечером были на форуме. Нельзя было высказать своё мнение (вот это, которое вы высказали здесь) в теме? Или это тоже рабочий момент, который не следует обсуждать на форуме? Тогда, может быть, следует закрыть на форуме тему?

17.09.2011 05:07 Наталия

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

17.09.2011 06:10 alexBlack

Я не вижу, что здесь обсуждать (но это мое мнение и возможно кто-то из форумчан еще отпишется). Давайте вспомним изначальную постановку задачи - поиск максимального непересекающегося маршрута. Представляют ли интерес немаксимальные маршруты мне неизвестно. Можно ли вносить ? Да, модуль проверки пропустит такие маршруты, нужно лишь чтобы длины была не менее, чем у маршрута, уже имеющегося в базе. Нужно ли вносить ? Я не знаю.

02.10.2011 10:29 Наталия

Алексей, что означает ошибка:
502 Bad Gateway
У меня уже однажды была такая ошибка, но тогда я так и не выяснила, что она означает.
Сегодня уже ввела маршруты, всё нормально было. А потом при вводе очередного маршрута выдалась эта ошибка.

02.10.2011 10:31 Наталия

Может быть, эта информация поможет:
перед этим я ошибочно ввела не тот маршрут, он уже есть в БД. Выдалась ошибка, что маршрут уже существует. А после этого стала вводить новый маршрут и вылетела в ошибку 502.

02.10.2011 10:35 Наталия

Попробовала ещё раз после комментариев, и ввелось.
Да, ещё: после того, как выдалось сообщение об уже существующем маршруте, я не смогла удалить путь из окошка. Тут явно где-то застопорилось в программе! Посмотрите, пожалуйста.

02.10.2011 11:05 alexBlack

502 Bad Gateway - браузер получил недопустимый ответ от сервера. У меня тоже изредка бывает. Техподдержка объясняет причину DoS атаками на сервер и приносит извинения за перерывы в работе. Единственый вариант здесь - немного подождать. Будем надеяться, что в дальнешем все наладится.
По поводу \"не смогла удалить путь из окошка\" - это явно проблемы Вашего компьютера или браузера. Серверные скрипты только обрабатывают запрос (грубо говоря строку) и возвращают ответ.

02.10.2011 02:25 Наталия

А нельзя сделать так, чтобы после вывода ошибки о некорректности маршрута поле для ввода очищалось?

02.10.2011 02:26 Наталия

Поле для ввода пути имеется в виду.

02.10.2011 03:29 alexBlack

Я думаю это будет неправильно. Допустим, случайно в поле введен некорректный символ. В этом случае после сообщения об ошибке можно будет исправить введенное значение. А если поле очистить, придется вносить заново и не будет видно в чем была ошибка.

02.10.2011 07:25 Наталия

Да, но у меня после ошибки в поле для ввода уже ничего не удаётся сделать. Просто оно ни на что не реагирует. Даже удалить весь путь не получилось. Вы говорите, что причина в моём компьютере. но я в этом сомневаюсь. Вы попробуйте сами. Введите некорректный маршрут, а после вывода ошибки проверьте поле для ввода.

02.10.2011 07:42 alexBlack

Попробовал, нормально работает. Понимаете, в этом смысле очистка поля ничего не меняет. Обработка полей осуществляется браузером и нет разницы пустое оно или заполненное.

02.10.2011 08:45 Наталия

Сейчас ещё раз попробую ввести существующий маршрут.

02.10.2011 08:51 Наталия

Да, вот сейчас нормально работает. Видимо, в прошлый раз я уже влетела в ошибку сервера, поэтому ничего не могла сделать с полем для ввода.

26.08.2012 04:38 Наталия

Здравствуйте, Алексей!
Почему исчезли некоторые изображения маршрутов?

26.08.2012 11:32 alexBlack

Временные проблемы хостинга.
Не только с изображениями проблема. Иногда вместо странички
появляется сообщение "503 Service Temporarily Unavailable"
Время от времени это у них бывает.

24.11.2013 06:48 Наталия

Алексей, где вы?
Я дала ссылку на БД в дискуссионной группе Al Zimmermann.
Может быть, кто-нибудь заинтересуется задачей и подбросит новые решения :)

31.12.2013 10:53 Наталия

Вот есть же такие идиоты - совать сюда рекламу!
Алексей, закройте эту возможность комментариев. Дайте где-нибудь в уголочке мелким шрифтом ваш контакт. А можно и этого не делать. Кому надо, тот найдёт. С наступающим вас!

05.03.2015 03:27 Bernard Lemaire

Hello

I am a French specialist of recreational mathematics . I found 30 years ago : L=212 for the open knight'stour on the 17x17 board, L=500 for 25x25, 906 for 33x33 : send me your email address . here is my email address : bernard.lemaire@cnam.fr Also, my other best tours have the same length as yours but most are different from yours

bernard.lemaire@cnam.fr, so that i can send you these tours

07.03.2015 03:39 alexBlack

Bernard, thank you

13.03.2015 02:40 alexBlack

Coefficient Q added in properties of tours.
Q = L-{(n-3)(m-3)+10} (was proposed by Bernard Lemaire)

26.03.2015 09:49 alexBlack

Наталия, спасибо. Нашел таки ошибку.
Отдельное "спасибо" разработчикам php изменившим кодировку по умолчанию в вызове htmlspecialchars().

26.03.2015 11:35 Наталия

Браво, Бернар!

30.03.2015 10:47 Наталия

Алексей, почему закрытый маршрут 16х16 R. Merson в 172 хода (кажется, совершенно одинаковый) приведён дважды с разными датами?

30.03.2015 11:06 alexBlack

Наталия, спасибо. Исправил.

05.04.2015 12:30 Наталия

Алексей, в списке замкнутых маршрутов на доске 9х9 нет маршрута Bernard Lemaire.

05.04.2015 04:50 alexBlack

В базе он есть, просто отображаются не все маршруты. Там ниже приписка "полный список маршрутов можно посмотреть...". Это ограничение введено чтобы не показывать слишком длинные списки маршрутов. Переместил маршрут на первое место.

05.04.2015 05:51 Наталия

Поняла, Алексей, спасибо. Теперь на первое место претендует моё решение :)

05.04.2015 10:00 alexBlack

done. Пожалуй я увеличу отображаемое количество маршрутов до 20-ти.

16.04.2015 01:16 Наталия

Алексей, что это значит?
Notice: Use of undefined constant Ymd - assumed 'Ymd' in /var/www/user18613/data/www/ukt.alex-black.ru/paths.php on line 8

17.04.2015 01:23 alexBlack

Кавычки пропущены. Исправил, спасибо.

Send comments