Ход конём

← →
Sha © (2004-10-13 11:25) [40]

> lehich © (13.10.04 11:00) [39]
> в моем решении 10х10 сотая цифра почти в самом центре
> оказывается, следовательно 1000*1000 не разбить по десяткам...

Как правило, для разбиения достаточно иметь замкнутый маршрут.
Если у тебя такой, то дело в шляпе.

← →
lehich © (2004-10-13 12:34) [41]

у меня он замыкается в самом центре, а до него минимум по 3-4 замкнутых круга ВНЕШНИХ

← →
Sha © (2004-10-13 13:24) [42]

> lehich © (13.10.04 12:34) [41]
> у меня он замыкается в самом центре, а до него минимум по 3-4 замкнутых круга ВНЕШНИХ

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

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

Например, маршрут [27] - замкнутый:
27 24 1 50 41 22 43 48 39 20 2 51 26 23 66 49 40 21 44 47 25 28 67 0 57 42 65 46 19 38 52 3 56 89 68 87 58 77 64 45 29 84 53 86 99 90 69 62 37 18 4 55 98 91 88 61 76 59 78 63 83 30 85 54 97 80 95 70 17 36 8 5 92 81 94 75 60 79 14 71 31 82 7 10 33 96 73 12 35 16 6 9 32 93 74 11 34 15 72 13
Для того чтобы замостить поле 1000*1000 маршрутом [27] достаточно в нем разомкнуть некоторые из переходов: 10-11,30-31,40-41,71-72.
Для связи с соседями по горизонтали можно образовать переходы: 30-71,31-72.
Для связи с соседями по вертикали можно образовать переходы: 10-41,11-40.
Соседние паркетины соединим змейкой:
0 1 2 3 4 5 6 7 8 9 19 18 17 16 15 14 13 12 11 10 20 21 22 23 24 25 26 27 28 29 39 38 37 36 35 34 33 32 31 30 40 41 42 43 44 45 46 47 48 49 59 58 57 56 55 54 53 52 51 50 60 61 62 63 64 65 66 67 68 69 79 78 77 76 75 74 73 72 71 70 80 81 82 83 84 85 86 87 88 89 99 98 97 96 95 94 93 92 91 90
Мы снова получаем замкнутый маршрут.

← →
Sha © (2004-10-13 13:26) [43]

Опять 27-ой уехал:
27 24 1 50 41 22 43 48 39 20 2 51 26 23 66 49 40 21 44 47 25 28 67 0 57 42 65 46 19 38 52 3 56 89 68 87 58 77 64 45 29 84 53 86 99 90 69 62 37 18 4 55 98 91 88 61 76 59 78 63 83 30 85 54 97 80 95 70 17 36 8 5 92 81 94 75 60 79 14 71 31 82 7 10 33 96 73 12 35 16 6 9 32 93 74 11 34 15 72 13

> 2Defunct пари? чтож вы боитесь? вы же уверены в сложности задачи и ее нерешаемости!!!

Был уверен, уже нет ;)

Ход конём Найти похожие ветки