Новый Морской бой Опции

[bLACK_wINGS]

В общем.. ига такая на логику... Весь инет облазил в поисках инфы, ничего не нашел.. попалась случайно вместе с журнальчиком 777. Суть игры:
Дано поле. По вертикали и горизонтали расположены числа 0..9. Каждое число предполагает наличие в в линии такого количества фрагментов кораблей. Набор кораблей стандартный. В общем прожка по идее должна выдать расстановку кораблей. Ваши соображения по поводу))))

[bLACK_wINGS]

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

А теперь выбираем следующую строку/столбец, в которой количество вариантов минимально, но уже учитываем поменявшуюся обстановку на поле. Например, если в строке записана сумма 8, но уже известно, что одна (определенная) клетка там - пустая, а другая - фрагмент корабля, то здесь у нас уже не С из 10 по 8, а С из 8 по 7.

допустим клетка уже определена, ну и как её при откате распознать, что не создана она была в течение этого хода? И еще, как использовать(распознать) такую ситуацию: на первом ходе вычислили клетку, вокруг которой в СТРОКЕ!!! пустые. Ведь это может быть н-палубник по вертикали))) и как тогда?

Перебирая варианты нужно, конечно, считать встретившиеся корабли, чтобы вовремя сделать откат противоречивого варианта.
Для удобства откатов лучше хранить не матрицу состояний (0 - не знаем, 1 - фрагмент, 2 - пусто), а матрицу целых чисел (0 - не знаем, -1 - фрагмент, K>0 - пусто, причем является результатом К выводов).
Тогда, когда мы в некоторую клетку ставим -1, мы должны просто инкрементировать всех соседей по диагонали, тем самым обозначая, что там - пусто (при этом проверяя отсутствие противоречий), а для отката достаточно будет просто декрементировать обратно, а не запоминать и восстанавливать все 8 соседей.

И вообще можешь поподробней об откате, а то вот с ним у меня будет косяк))
Уже написал действующий код, генерирующий поле автоматически.
Дааа... И еще, проблема памяти(глубины стека) возникает. Ведь функция, которая реашает задачу будет рекурсивной, или я ошибаюсь? Если ошибаюсь, то как иначе?

Сообщение отредактировано: bLACK_wINGS - 2.11.2006 19:37