IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Новый Морской бой
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 9
Пол: Мужской

Репутация: -  0  +


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


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


А по форуму поискать? морской бой (растановка кораблей)


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 9
Пол: Мужской

Репутация: -  0  +


2Bokul:
Нее.. это я уже смотрел... там чисто генерация расстановки, это слишком просто. Ты предлагаешь генерировать расстановки пока одна из них не подойдет??? а не много ли будет операций)))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


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


Да не то. Это я сначала не правильно задание понял...
Цитата
Набор кораблей стандартный


А поточней можно, давно не играл.


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 9
Пол: Мужской

Репутация: -  0  +


2Bokul:
Да набор такой: 4-однопалубников 3-двухпалубных 2-трёхпалубных 1-четырехпалубный. Корабли не касаются друг друга даже углами. В принципе у мня есть процедуры готовые на некоторые действия, но просто хотелось бы выслушать подсказки)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


Еще одно:
Какой размер доски и может ли повторятся количество фрагментов по вертикали или горизонтали?


--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Я бы попробовал такой перебор.

Рассмотрим пустую строку, для которой сумма, например, равна 2.
Существует С из 10 по 2 = 10*9/2 = 45 способов закрасить строку таким способом.

Вообще, из N клеток закрасить К всегда можно С из N по К способами.

Так вот, выбираем строку/столбец, для которой количество вариантов минимально.
Перебираем все варианты, и для каждого из них делаем выводы, а именно: если, например, в горизонтальной строке встречаются 2 подряд фрагмента, обрамленные пустыми клетками, то это - не что иное, как двухпалубный корабль. Обрамляем его пустыми клетками сверху и снизу. Если же встречается один фрагмент, то это - либо 1-палубный, либо вертикальный, поэтому в любом случае ставим прочерк в соседние по диагонали клетки.

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

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

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

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


Должно работать быстро. Если будут проблемы с реализацией - маякни, если будет время, было бы интересно закодить smile.gif

Сообщение отредактировано: Michael_Rybak -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8





Группа: Пользователи
Сообщений: 9
Пол: Мужской

Репутация: -  0  +


2Michael_Rybak
Ё-моё.. а не будет ли много мороки с этим... там в начале книжицы этой был такой неплохой алгоритмик... просто че то не могу закодить...
Ну да ладно... короче нужно еще подумать над тем, а сколько вариантов этих расстановок... по идеи она всегда одна?))
И вообще... проще было бы комбинировать два варианта.. тот который описан и этот...
Давай я в течение недли отсканю тот вариант и подумаем как лучше будет)))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Давай smile.gif

EDIT:
>Ё-моё.. а не будет ли много мороки с этим...
много smile.gif
>а сколько вариантов этих расстановок... по идеи она всегда одна?))
скорее всего, совсем не обязательно одна.


Сообщение отредактировано: Michael_Rybak -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10





Группа: Пользователи
Сообщений: 9
Пол: Мужской

Репутация: -  0  +


Прикрепленное изображение
Вот отсканенный типа алгоритм... Но как программу заставить думать и выбирать-загадка...
Тем более что могут быть тупиковые ситуации. И человек интуицией обладает, а прога-нет))))) Но этот алгоритм вродь как лучше чем перебор)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(bLACK_wINGS @ 28.10.2006 10:42) *

этот алгоритм вродь как лучше чем перебор


Как сказать.

На самом деле, этот "алгоритм" - это набор эвристик, уловок, которыми мы пользуемся, решая вручную.

Я не уверен, что все эти уловки имеет смысл объяснять машине. Главное - передать идею. А идея - выжимать из текущей позиции максимум информации. Человек это делает изощренно, а машина может и "в лоб" - она быстрая, поэтому ей достаточно объяснить правила в целом, и сказать, где лучше искать "узкие места". А искать их лучше там, где меньше вариантов.

Один из методов я предложил - считать варианты в каждой строке. Это, в некоторой степени, геморрой, но совсем не такой страшный, как изучение и кодирование всевозможных эвристик.

Кстати, у нас газета "Кроссворды и Головоломки" уже много лет регулярно публикует такие (и многие другие) головоломки. Только там поле 11х11, и набор кораблей больше. Вот, например, сентябрьский номер: http://www.kig.tvpark.ua/_ARC/2006/KG_06_37.PDF. 10я страница, снизу.

Для 11х11, возможно, нужен более глубокий анализ задачи. Возможно, плясать уже нужно не от строк, а совместить такие подходы: 1) куда можно поставить каждый из оставшихся кораблей, 2) какой корабль можно поставить в каждую из оставшихся клеток, 3) сколькими способами можно *оставшимися* кораблями заполнить каждую строку и, главное, 4) в каком месте поля перебор ответов на эти вопросы отсечет как можно больше вариантов.

Это уже посложнее, но тоже не смертельно.

Так что, карты в руки. Если хочешь - начинай пробовать (это входило в твои планы? ;). Если не совсем понятно, с чего начать - спрашивай, будем вместе делать. Для начала напиши проверялку на дельфях - чтоб файлы грузила, сохраняла, генерила рандомом, и вызывала решение из модуля. А там, пока что - заглушка.

P.S. А я вот сижу тут и думаю... 6 курс... не развернуть ли мне все это по полной на диплом? Очень даже ничего получится smile.gif

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12





Группа: Пользователи
Сообщений: 9
Пол: Мужской

Репутация: -  0  +


Прикрепленный файл  MB.rar ( 3.88 килобайт ) Кол-во скачиваний: 533
2Michael_Rybak
Да решал я эти головоломки, ну алгоритмизируется там всё.... Только пока не могу написать, как кораблики расставить. скинул то что накорябал, но сразу говорю, оно не тестено !!!!воообще!!!!! просто голый код. Кста, это мой курсач, напросился так сказать на него)))

Сообщение отредактировано: bLACK_wINGS -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Да решал я эти головоломки, ну алгоритмизируется там всё....


Вот оно как? Ну и замечательно!

Цитата
Только пока не могу написать, как кораблики расставить


Что именно ты не можешь написать?

Цитата
скинул то что накорябал, но сразу говорю, оно не тестено !!!!воообще!!!!! просто голый код.


А зачем скинул, если не тестено, ничего не делает и не компилится?

Цитата
Кста, это мой курсач, напросился так сказать на него)))


Удачи good.gif

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14





Группа: Пользователи
Сообщений: 9
Пол: Мужской

Репутация: -  0  +


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

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

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

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

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

Сообщение отредактировано: bLACK_wINGS -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

Глубины более чем достаточно, потому что
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;



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

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


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


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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16





Группа: Пользователи
Сообщений: 9
Пол: Мужской

Репутация: -  0  +


В принципе с твоей функцией понятно. Однако у меня она будет работать немного по другому.
1. Получаем максимальнок кол-во фрагментов в линии
2. Получаем массив из 0 и 1 для порождения перестановок, где сумма 1=кол-во фрагментов на шаге 1
3. Записываем его в строку поля
4. Убираем эту линию, что бы не использовать на последующих шагах
5. Вызов рекурсии
Специально не включил проверку на законченность поля, что бы убедится что стека хватит. Выдает сообщение о переполнении стека wink.gif
Код
Код

const n=10;
type t_mas=array[0..n] of 0..1;
     type t_matr=array[0..n] of t_mas;
function pr(const q:t_mas;s:byte):boolean; //проверка, что кол-во единиц и кол-во фрагментов совпадает
var i:byte;
    k:byte;
begin
  k:=0;
  for i:=1 to n do k:=k+q[i];
  if k=s then pr:=true
  else pr:=false;
end;
function findmaxfrag(const a:t_matr):byte; //находим-макс. фрагментов из линии
var i,max:byte;
begin
  max:=0;
  for i:=0 to n-1 do
    if a[i,n] > max then max:=i;
  for i:=0 to n-1 do if a[n,i]>max then
    max:=i+n;
  findmaxfrag:=max;
end;

var a:t_matr;
    j,i:byte;
    q1:boolean;
function rekurs:byte; //сама рекурсия
var i,j,t:-1 ..n;
    r:1..n;
    h,coun,l,z:byte;
    s:array[0..n] of 1..n;
    q:t_mas;
begin
t:=0;
h:=findmaxfrag(a);
if h-10 >0 then
begin
for j:=n downto 1 do
  begin
    q[j]:=0;
    t:=t+1;
    s[t]:=j;
  end;
  while t>=0 do
  begin
    if pr(q,a[n,h-10]) then
    begin
      for l:=0 to n-1 do a[l,h-10]:=q[l+1];
      a[n,h-10]:=0;
      z:=rekurs;
    end;
    i:=s[t];
    t:=t-1;
    q[i]:=1 xor q[i];
    for j:=i-1 downto 1 do
    begin
      t:=t+1;
      s[t]:=j;
    end;
  end
end
else
  begin
  for j:=n downto 1 do
  begin
    q[j]:=0;
    t:=t+1;
    s[t]:=j;
  end;
  while t>=0 do
  begin
    q1:=pr(q,a[n,h]);
    if pr(q,a[n,h]) then
    begin
      for l:=0 to n-1 do a[h,l]:=q[l+1];
      a[h,n]:=0;
      z:=rekurs;
    end;
    i:=s[t];
    t:=t-1;
    q[i]:=1 xor q[i];
    for j:=i-1 downto 1 do
    begin
      t:=t+1;
      s[t]:=j;
    end;
  end
  end;
end;
begin
  for i:=0 to n do
    for j:=0 to n do
      a[i,j]:=0;
  for j:=0 to n-1 do a[n,j]:=STRTOINT(Form1.StringGrid1.Cells[1,j+1]);
  for j:=0 to n-1 do a[j,n]:=STRTOINT(Form1.StringGrid1.Cells[j+1,1]);
  rekurs;
end;

Дело даже не в передаче параметров. Просто на нижнем уровне стек переполняется.
Стек самого проца.
Да и переполнения на 2 шаге при пошаговом просмотре!!!

Сообщение отредактировано: bLACK_wINGS -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
2. Получаем массив из 0 и 1 для порождения перестановок, где сумма 1=кол-во фрагментов на шаге 1


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


Цитата
Дело даже не в передаче параметров. Просто на нижнем уровне стек переполняется.
Стек самого проца.
Да и переполнения на 2 шаге при пошаговом просмотре!!!


Выложи проект, я ж не буду StringGridы рисовать smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18





Группа: Пользователи
Сообщений: 9
Пол: Мужской

Репутация: -  0  +


ВСЁЁЁ rolleyes.gif rolleyes.gif
Дописал... Всего то 430 строк кода.... Надо будет почитстить правда и его)))

2Michael_Rybak
Почти по твоему способу однако перестановки идут в линиях, а число фрагментов в вертикалях - проверочное.
Работает на удивление быстро))) Однако есть некоторые косяки. Вот например пользователь вводит число кораблей для расстановки, а ведь иногда не работает из-за того что корабли с таким кол-вом палуб использованы. И еще: Не мог бы описать, как графически это всё на Стринг гриде графически обрисовать, а то не красиво всё 0 и -1 представлять)))

Сообщение отредактировано: bLACK_wINGS -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 6.10.2024 7:37
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name