Пользовательская эвристика в ECLiPSe CLP

Question

Рассмотрим следующую головоломку:

Ячейка либо помечена, либо не помечена. Числа в правой и нижней части головоломки обозначают общую сумму для определенной строки или столбца. Ячейки вносят (если отмечены) в сумму в своей строке и столбце: ячейка в позиции (i,j) вносит i в сумму столбца, а j в сумму строки. Например, в первом ряду на рисунке выше отмечены 1-я, 2-я и 5-я ячейки. Они вносят 1 + 2 + 5 в сумму строки (таким образом, в сумме 8), и 1 каждый в их сумму столбца.

У меня есть решатель в ECLiPSe CLP для этой головоломки, и я пытаюсь написать собственную эвристику для нее.

Я думаю, что проще всего начинать с тех ячеек, для которых подсказки столбца и строки настолько низки, насколько это возможно. В общем, нижний N есть меньше возможностей для написания N как сумма натуральных чисел от 1 до N, В контексте этой головоломки это означает ячейку с самым низким column hint + row hint имеет самые низкие шансы ошибиться, поэтому меньше отступает.

В реализации у меня есть NxN массив, представляющий доску, и два списка размера N, которые представляют подсказки. (Цифры сбоку и снизу.)

Я вижу два варианта:

• Напишите пользовательский предикат выбора для поиска / 6. Однако, если я правильно понимаю, я могу дать только 2 параметра. Тогда нет способа вычислить сумму строки + столбца для данной переменной, потому что мне нужно иметь возможность передать ее предикату. Мне нужно 4 параметра.

• Игнорируйте search/6 и напишите собственный метод маркировки. Вот как у меня это сейчас, см. Код ниже.

Требуется доска (NxN массив, содержащий все переменные решения), оба списка подсказок и возвращает список, содержащий все переменные, теперь отсортированные по их строке + сумме столбца. Однако, как вы можете видеть, это, возможно, не может стать более громоздким. Чтобы иметь возможность сортировки, мне нужно прикрепить сумму к каждой переменной, но для этого мне сначала нужно преобразовать ее в термин, который также содержит координаты указанной переменной, чтобы я преобразовал обратно в переменную как как только сортировка сделана...

lowest_hints_first(Board,RowArr,ColArr,Out) :-
    dim(Board,[N,N]),
    dim(OutBoard,[N,N]),
    ( multifor([I,J],[1,1],[N,N]), foreach(Term,Terms), param(RowArr,ColArr) do
        RowHint is ColArr[I],
        ColHint is RowArr[J],
        TotalSum is RowHint + ColHint,
        Term = field(I,J,TotalSum)
    ),
    sort(3,<,Terms,SortedTerms), % Sort based on TotalSum
    terms_to_vars(SortedTerms,Board,Out), % Convert fields back to vars...
    ( foreach(Var,Out) do
         indomain(Var,max)
    ).

terms_to_vars([],_,[]).
terms_to_vars([field(I,J,TotalSum)|RestTerms],Vars,[Out|RestOut]) :-
    terms_to_vars(RestTerms,Vars,RestOut),
    Out is Vars[I,J].

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

Answer 1

Я вижу, вы уже довольны улучшением, предложенным Иоахимом; однако, когда вы просите о дальнейших улучшениях вашей эвристики, учтите, что есть только один способ получить 0 как сумму, а также только один способ получить 15. Существует только один способ получить 1 и 14, 2 и 13; два способа получить 3 и 12. В общем, если у вас есть K способов получить сумму N, у вас также есть K способов получить 15-N.

Таким образом, сложные суммы не большие, они средние.