Гораздо супрематичнее, чем у Малевича

Sam Sebe wrote:
Нет, внимательно наблюдаем.
На диаграммах, где змейка меняют направление, встречаются случаи углового касания.

Например, площадь 2Х2, где змея касается саму себя под углом, на рисунке имеет координаты a2a3b2b3 или e4e5f4f5.
Количество таких случаев разное. От 6 до 2-х. А может и вообще 0. Интересно, от чего зависит это количество?

В случаях с разомкнутыми змейками появляется закономерность. К каждому из четырёх боков примыкает одна фигура, состоящая из белых клеток. На рисунке это: с юга - линия из трёх клеток; с запада - одна клетка; с севера - тоже трёхклеточная линия; с востока - двухклетка.

Эти незакрашенные белые фигуры напоминают корабли в "Морском бое". Каково распределение "четырёхпалубных" и прочих кораблей в этом случае - тоже вопрос довольно интересный.

Возможно ли вывести общую формулу подсчёта максимально допустимых закрашенных клеток при другой размерности доски?
Доска 1*1 = 1 закрашенная клетка;
Доска 2*2 = 3 клетки;
Доска 3*3 = 7 клеток;
Доска 4*4 = 11, и т.д.

Andralex wrote:
На 1-й вопрос не знаю, как ответить. Надо подумать.
На вопрос про распределение "кораблей" ответить проще.
А насчет размерности больше восьми... думаю, моему компьютеру не под силу будет.

Andralex wrote:
Вот, нашел это распределение.



Эти 108 + 8 змеек (исчерпывающее число) максимальной длины (42 клетки) стартуют в 1-м квадранте, и 16 из них в нем же финишируют, т.е. 8 змеек учитываются дважды: в одном направлении и в другом. Случаев касания, оказывается, не от 2 до 6, а от 5 до 8.

Вот еще вдогонку распределение змеек по числу изломов.

Andralex wrote:
Кстати, хорошая наводка. Сколько существует различных начальных расстановок кораблей в классическом Морском бое?

Поле 10х10, один линкор (4-клеточный), два крейсера (3-кл.), три эсминца (2-кл.) и четыре катера (1-кл.). Касания и изломы не допускаются.

Sam Sebe wrote:
Вопрос оказался интересным. Ответить на него я пока не смог, зато возникли другие интересные вопросы.

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

Оставить половину можно, для этого надо постараться компактно втиснуть.

▄▄▄ ▄▄ ▄▄▄ 3+1+2+1+3=10
▄▄ ▄▄ ▄▄ ▄ 2+1+2+1+2+1+1=10
▄▄▄▄ ▄ ▄ ▄ 4+1+1+1+1+1+1=10

В игре такую расстановку не применять! Противник сходу просечёт поляну потопит все корабли.

Andralex wrote:
Нет, это было бы чересчур просто, это всегда 80 пустых клеток. В вопросе спрашивается про заполнение не только собственно корабельных клеток, но и зон вокруг них. Например, линкор - это не только 4 его клетки, но и, в худшем случае, еще 14 клеток вокруг.

Вот какого вида заполнения имеются в виду. Здесь незаполненными остались 1 клетка и 37 клеток.



А про выигрышные расстановки я еще скажу.

А вот какое распределение
1 миллиона случайных расстановок
соответствующее получилось.



Кстати, 37/100 - это 1/e, можно сказать.

Т.е. ТАКИ
1. точно - случайность - непознанная закономерность?
2. очевидно (объективно, трояко): есть начало таблицы, есть середина...
3. субъективно, жаль что
Число, которое считаю "моё" 23- в нижней половине получилось.
З павагай да неабыякавых
Зы. Целиком и полностью полагаясь на ваше усмотрение, ув. Sam Sebe, не вычислите ли сумму всех усеченных гармонических рядов (без 1, без 2-х, без ТРЕХ цифр) и не определите ли № конечного слагаемого ГР, обеспечивающего ТОЧНО ТАКУЮ ЖЕ СУММУ? А вдруг полученныое требуемое число слагаемых Гармонического ряда ТОЧНО совпадет с числом, которое называл СергеП для вселенсконатурального7. З павагай, паклонам

Оптимизировал программу, и она стала считать в 10 раз быстрее, так что тот же миллион случайных расстановок кораблей получился за 6 минут. Распределение по числу незаполненных (за вычетом кораблей и примыкающих к ним клеток) похожее.



Вот две крайние расстановки из найденных: одна полностью (о=0) заполняет игровое поле, а другая - по минимуму (о=38).



Кстати, 38 : 62 - это золотое сечение. Подозреваю, 62 заполненные клетки из 100 - это действительно минимум. Впрочем, теперь реально рассмотреть и целых 10 миллионов расстановок.

А если зеленый трехпалубник из центра (o=38) подвинуть вправо на край доски? Чёрных клеток станет больше.

Да, правильно, на 4 штуки. Значит, не золотое сечение. Очень жаль. Ладно, сейчас на 10 миллионах проверим.

А еще и одну-две красные можно подвинуть.

Sam Sebe wrote:


Чуть лучше (о=39), но все равно не минимум.

Интересную вещь заметил. Если уменьшить игровое поле до 9х9, то при последовательной (линкор - крейсера - эсминцы - катера), но случайной расстановке кораблей примерно в одном из 300-400 случаев осуществить ее не удается: не всем катерам хватает места (бывает даже, что только одному хватает). А вот на поле 10х10 такого не случается, т.е. набор кораблей для него как бы оптимален.

Sam Sebe wrote:
Посмотрел в Википедии про "Морской бой". Оказывается, привычный нам набор кораблей присутствует только в ее русскоязычной версии, а во всех других ее версиях, даже в хохляцкой, он другой (6х1 + 4х2 + 3х3 + 2х4 = 31 клетка) - под копирку с англоязычной версии, хотя игровое поле прежнее, 10х10. Но в таком виде случайную расстановку кораблей удается осуществить только 96-97 % случаев - в этом смысле такой набор кораблей для поля 10х10 является неестественным, избыточным. Чисто по-мерикански. Властелины морей океанов. ))

Andralex wrote: А если поменять его с левым угловым двухпалубником?

З павагай да неабыякавых

Sam Sebe wrote:
Дополнение.
В настоящее время, имея под рукой компьютеры, не составит труда рассчитать оптимальное количество кораблей на доске N*N. Так, чтобы было не тесно,-- тогда быстро игра закончится, но и не просторно,-- тогда игроки от постоянных бультыханий снарядов в воду просто впадут в унылость.
Но, игра морской бой известна ещё до начала повальной компьютеризации.
Возникает вопрос: как же так высчитали идеально?
Ответ: постепенно и опытным путём. Так же как и шахматы за тысячи лет обтесались др идеала.

инфолиократ wrote:
И вообще, если каждый корабль имеет вокруг себя нейтральную зону из клеток, то часть этой зоны (одного борта) можно просто убрать, поместив корабль на край доски. В итоге, высвободится лишнее место для свободных клеток.

Выигрышная стратегия в "Морской бой" описана в Википедии. Если коротно, то все корабли, кроме катеров, надо собрать в одну кучу, чтобы оставить для катеров площадь побольше, где их трудно будет найти. Правда, мне это несколько сомнительно: вдруг противник быстренько (коль скоро ход не передается) перебьет всю кучу и возьмется за катера, а я еще ничего не успею.

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



Получилось, что max = 60, но расстановка такая нашлась всего одна. И она "полукомпактная", т.е. 3 корабля прижаты к одному краю и 3 к противоположному, а 60 клеток в центре остаются незанятыми (чтобы равномерно разместить там катера).

Для таких случаев особо хитрые игроки в начале рисуют не десять, а девять кораблей, и одноклеточный катер в самом конце игры, в последний момент.

Нашел еще несколько расстановок с о=60, некоторые их них совпадают. Все они такие: корабли прижимаются или к одному краю игрового поля, или к двум противоположным краям, или к двум смежным, что неудивительно, поскольку всякий раз корабли расставлялись хоть и случайно, но так, чтобы примыкать к зонам уже расставленных кораблей и/или к краям игрового поля, а иначе достичь о=60 не удается.

Andralex wrote:
Ну это как бы для школьников, которым важно победить, а не просто убить время.

Получил-таки 7 расстановок с о=44, все разные.
Это для набора из 10 кораблей, с катерами.

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

Сам алгоритм случайного обстрела по функции определения координат F(X,Y)=10*rand() можно заменить известным алгоритмом обхода коня доски.
Возможно, результаты такого просеивания будут лучше.

Andralex wrote:
Но и случайность, и регулярность обхода должны постоянно сбиваться, поскольку при ранении корабля его всегда добивают.