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

[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

[Michael_Rybak]

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

Глубины более чем достаточно, потому что
1) глубина вложенности - не больше 20 (каждый уровень рекурсии соответствует одной строке/стобцу, где мы перебираем 2^x вариантов одним циклом - перебираем значения клеток, для которых ничего не известно)
2) всё поле передавать в стек не нужно; вообще в стек передавать ничего не нужно

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

В такой ситуации в любом случае считаем, что эта клетка принадлежит вертикальному кораблю (возможно и однопалубному). Всё, что можно при этом сказать - что 4 соседя по диагонали обязательно пусты.

допустим клетка уже определена, ну и как её при откате распознать, что не создана она была в течение этого хода?

Именно об этом я говорю вот здесь:

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

Итак, значения клеток у нас такие:

-1 - там корабль
0 - пока что ничего не известно
>0 - там вода

Давай рассмотрим такой пример. Пусть в строке уже все известно, кроме двух клеток. И пусть в первой (А) из этих клеток мы предполагаем наличие фрагмента корабля, а во второй (В) - отсутствие.

Выглядеть это будет так:

if (field[Ay][Ax] = 0) then // в клетке А значение неизвестно 
  if (field[By][Bx] >= 0) then // в клетке B не стоит корабль
  begin 
    //делаем предположение
    field[Ay][Ax] := -1; //корабль
    field[By][Bx] := field[By][Bx] + 1; //увеличиваем, чтобы сказать, что там точно пусто (*)
  
    Search(...);//рекурсивный вызов
 
    //отменяем предположение - восстанавливаем ситуацию
    field[By][Bx] := field[By][Bx] - 1; //уменьшаем, забирая только текущий вывод. 
                                        //Т.е. если там пусто из других, более 
                                        //ранних соображений, то останется 
                                        //положительное число, то же, которое было 
                                        //до вызова этого уровня рекурсии
    field[Ay][Ax] := 0; //убрали корабль
  end;

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

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


В этом примере я не учитываю влияния изменений на соседние строки (на самом деле, изменив что-то в строке, надо пройти по ней, распознать корабли, и понаставлять вокруг них воды в соседних строках). Это просто чтоб объяснить, как откатывать.


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