Алгоритм решения головоломки Акари (Akari LightUp Фонари)

[Armageddets]

Всем доброго времени суток, уважаемые эксперты. Передо мной стоит задача написать алгоритм решения головоломки Акари (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;

Но в данный момент просто ставится случайным образом воркгу стенок нужное количество фонарей. Причем, понятное дело, что возле некоторых их получается больше (поскольку от других стен фонари могут становиться рядом). Я понимаю, что нужно еще проверять возле места где мы ставим в радиусе одной клетки наличие цифр на стенках и у каждой такой клетки проверять сколько уже стоит вокруг. Можно отдельный уровень для хранения сколько уже стоит вокруг сделать. Помимо этого еще нужно контролировать освещенность всего поля. Мне сложно представить как лучше это реализовать. Помогите, кто чем может, ребята.

[Cuprum5]

1)

Сообщение от Armageddets

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

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

[Serge_Bliznykov]

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

а почему не воспользоваться банальным перебором?
решение не укладывается по времени?

[kropotkina-alice]

Вообще-то это всем известный "Минёр".
Почему не взять исходник и не убрать оттуда учет по диагоналям?

[Serge_Bliznykov]

Сообщение от kropotkina-alice

Вообще-то это всем известный "Минёр".

нет, это не совсем минёр(Сапёр, если уж переводить на русский).
точнее, совсем не Сапёр.

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