Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Общие вопросы Delphi
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 16.06.2017, 19:04   #1
Armageddets
Форумчанин
 
Регистрация: 30.06.2012
Сообщений: 145
По умолчанию Алгоритм решения головоломки Акари (Akari LightUp Фонари)

Всем доброго времени суток, уважаемые эксперты. Передо мной стоит задача написать алгоритм решения головоломки Акари (Akari LightUp Фонари).

Правила игры. Загружается поле размера 7х7 или 10х10. Оно поделено на клетки. Есть пустые клетки, а есть клетки со стенками. Цифра внутри стены показывает сколько стоит вокруг нее фонарей (по вертикали и горизонтали). По диагонали фонари не учитываются цифрой. Каждый фонарь засвечивает вокруг себя прямую линию вниз, влево, вправо и вверх до того места где находится конец поля, другая лампа или стена. Задача состоит в том чтобы осветить все поле, расставив требуемое количество фонарей вокруг стен с цифрами.

Помогите реализовать (продумать) алгоритм решения. Заранее всем спасибо за советы.

Я создал динамический массив
Код:
mas:array of array of array of Integer;
Обнуляю и заполняю его по уровням (так сказать):
Код:
      for i:=1 to ii do
      begin
      mas[i-1,j,0]:=StrToInt(S[i]); //стенки
      mas[i-1,j,1]:=StrToInt(P[i]); //цифры в стенках
      mas[i-1,j,2]:=StrToInt(T[i]); //правильный ответ (теперь уже не нужен, так как просто подставлять нельзя)
      mas[i-1,j,3]:=0; //пользовательское поле (фонари и точки)
      end;
Начал писать алгоритм авторешения так:

Код:
for i:=0 to ii-1 do
  for j:=0 to jj-1 do
  begin
    //ishem tsifru
    if mas[i,j,1]>0 then
    begin
      //proveryaem skolko vokrug lamp
      //esli menshe to podbiraem kletku

      //stavim nuzhnoe kol-vo lamp
      k:=0;
      Randomize;
      while (k<mas[i,j,1]) do
      begin
        //vibiraem sluchaynoe napravlenie
        m:=Random(4);

        //v zavisimosti ot vibrannogo napravleniya probuem stavit lampu
        case m of
        0:begin
            //ne za granitsami  //net lamp         //net steni
            if ((i-1)>=0) and (mas[i-1,j,3]=0) and (mas[i-1,j,0]=0) then
            begin
            mas[i-1,j,3]:=1;
            Inc(k);
            end;
          end;
        1:begin
            //ne za granitsami  //net lamp         //net steni
            if ((i+1)<=ii-1) and (mas[i+1,j,3]=0) and (mas[i+1,j,0]=0) then
            begin
            mas[i+1,j,3]:=1;
            Inc(k);
            end;
          end;
        2:begin
            //ne za granitsami  //net lamp         //net steni
            if ((j-1)>=0) and (mas[i,j-1,3]=0) and (mas[i,j-1,0]=0) then
            begin
            mas[i,j-1,3]:=1;
            Inc(k);
            end;
          end;
        3:begin
            //ne za granitsami  //net lamp         //net steni
            if ((j+1)<=jj-1) and (mas[i,j+1,3]=0) and (mas[i,j+1,0]=0) then
            begin
            mas[i,j+1,3]:=1;
            Inc(k);
            end;
          end;
        end;

      end;

    end;
  end;
Но в данный момент просто ставится случайным образом воркгу стенок нужное количество фонарей. Причем, понятное дело, что возле некоторых их получается больше (поскольку от других стен фонари могут становиться рядом). Я понимаю, что нужно еще проверять возле места где мы ставим в радиусе одной клетки наличие цифр на стенках и у каждой такой клетки проверять сколько уже стоит вокруг. Можно отдельный уровень для хранения сколько уже стоит вокруг сделать. Помимо этого еще нужно контролировать освещенность всего поля. Мне сложно представить как лучше это реализовать. Помогите, кто чем может, ребята.
Изображения
Тип файла: png akari_logo.png (5.1 Кб, 111 просмотров)
Тип файла: png unnamed.png (9.2 Кб, 44 просмотров)
Тип файла: png unnamed1.png (30.8 Кб, 52 просмотров)
Armageddets вне форума Ответить с цитированием
Старый 16.06.2017, 19:48   #2
Cuprum5
Форумчанин
 
Регистрация: 09.05.2017
Сообщений: 729
По умолчанию

1)
Цитата:
Сообщение от Armageddets Посмотреть сообщение
Но в данный момент просто ставится случайным образом воркгу стенок нужное количество фонарей.
- Наверное, не случайным образом их нужно ставить, а так, чтобы были заполнены все строи и столбцы. Т.е. алгоритм примерно такой: проходим по всем строкам последовательно и расставляем фонари так, чтобы в каждой строке был хотя бы 1 фонарь, потом то же самое со столбцами. Повторяем так несколько раз. Если решение не было найдено в данной расстановке, то начинаем все сначала и расставляем как-то по другому.
2) В качестве пробы: 3D-массив - это как-то сложновато, бы попробовал 2D-массив байт. Число будет указывать на количество фонарей для стены причем стена это или не стена будет указывать старший бит в байте. Для фонаря нужно, чтобы было какое-то число. Придумайте его, пожалуйста. Расставляем фонари и обозначаем свет от них. Тоже свет можно назначить каким-то числом. Расставляем фонари по алгоритму, который я описал в 1-й части своего сообщения. И потом перемещаем фонари и смотрим как падает свет.

Последний раз редактировалось Cuprum5; 16.06.2017 в 19:53.
Cuprum5 вне форума Ответить с цитированием
Старый 17.06.2017, 00:10   #3
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

т.е. дано поле со стенками-цифрами,
задача расставить фонари?

а почему не воспользоваться банальным перебором?
решение не укладывается по времени?
Serge_Bliznykov вне форума Ответить с цитированием
Старый 17.06.2017, 10:49   #4
kropotkina-alice
Форумчанин
 
Аватар для kropotkina-alice
 
Регистрация: 27.10.2014
Сообщений: 594
По умолчанию

Вообще-то это всем известный "Минёр".
Почему не взять исходник и не убрать оттуда учет по диагоналям?
kropotkina-alice вне форума Ответить с цитированием
Старый 18.06.2017, 10:51   #5
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от kropotkina-alice Посмотреть сообщение
Вообще-то это всем известный "Минёр".
нет, это не совсем минёр(Сапёр, если уж переводить на русский).
точнее, совсем не Сапёр.

дело в том, что фонари нужно расставить так, чтобы они полностью осветили поле.
в Сапёре такая задача не возникает совсем.
Serge_Bliznykov вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Подскажите алгоритм решения Nickolay0512 Общие вопросы C/C++ 12 07.10.2014 23:26
Алгоритм решения задачи Amet13 Помощь студентам 1 21.04.2012 13:16
Алгоритм решения задачи snpccvs Помощь студентам 8 13.02.2012 22:50
Алгоритм решения Naruto63 Помощь студентам 6 20.09.2009 22:47
Подскажите алгоритм решения Blad47 Паскаль, Turbo Pascal, PascalABC.NET 1 10.11.2008 19:50