Изучение Пролога, Решатель Судоку

Моя проблема: во время изучения Пролога я хотел сделать решатель судоку NxN. Этот решатель получит ввод вроде

    [[1,2,3,4],[3,4,1,2],[2,3,4,1],[4,1,2,3]]

Где некоторые из них могут быть переменными. Решатель должен решить эту судоку. Проблема намного меньше:

    firstElementsOf([],_).
    firstElementsOf([[X|_]|Rest2],Y) :-
      firstElementsOf(Rest2,Y2),
      append([X],[Y2],NotFlat),
      flatten(NotFlat,Y).

Это должно быть началом проверки, если в каждом столбце есть разные числа. Y из firstElementsOf должен содержать только первые элементы заданных строк. В примере:

    [1,3,2,4]

К сожалению, благодаря append он всегда добавляет еще одно пустое место в список Y. Это дает:

    [1,3,2,4,_1320]

Вопрос1: Есть ли способ избавиться от этого _1320?

Вопрос2: Это вообще правильно? Будет ли способ получить с его помощью 2-й и 3-й элементы ввода?


constraint-satisfaction sudoku prolog
person Shuumi    schedule 26.12.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

На вопрос 1: я полагаю, что ошибка в

firstElementsOf([],_).

Я думаю должен быть

firstElementsOf([],[]).

Не по теме: вы уверены, что не можете просто написать другой пункт следующим образом?

firstElementsOf([[X|_]|Rest2],[X|Y]) :-
  firstElementsOf(Rest2,Y).

На вопрос 2: я предлагаю более общий предикат: следующее getPosList/3 с поддержкой getPosElem/3

getPosElem([H | _], 1, H).

getPosElem([_ | T], Pos, H) :-
  Pos > 1,
  Pm1 is Pos - 1,
  getPosElem(T, Pm1, H).

getPosList([], _, []).

getPosList([H | T], Pos, [E | L]) :-
  getPosElem(H, Pos, E),
  getPosList(T, Pos, L).

Он извлекает список всех элементов в позиции Pos, поэтому

getPosList([[1,2,3,4],[3,4,1,2],[2,3,4,1],[4,1,2,3]], 1, L),

это эквивалент firstElementOf([[1,2,3,4],[3,4,1,2],[2,3,4,1],[4,1,2,3]], L) и извлечение [1, 3, 2, 4],

getPosList([[1,2,3,4],[3,4,1,2],[2,3,4,1],[4,1,2,3]], 2, L),

извлечь [2, 4, 3, 1],

getPosList([[1,2,3,4],[3,4,1,2],[2,3,4,1],[4,1,2,3]], 3, L),

извлечь [3, 1, 4, 2],

getPosList([[1,2,3,4],[3,4,1,2],[2,3,4,1],[4,1,2,3]], 4, L),

извлечь [4, 2, 1, 3] и

getPosList([[1,2,3,4],[3,4,1,2],[2,3,4,1],[4,1,2,3]], 5, L),

или число больше 5, вернуть false

person max66    schedule 26.12.2016
comment
Во-первых ... действительно работает ... даже не понимаю почему. - person Shuumi; 26.12.2016
comment
На второй ... я тоже могу это сделать ... но я тоже этого не понимаю :) Дай я посмотрю позже :) - person Shuumi; 26.12.2016
comment
@Shuumi; ответ улучшен (с предложением по пункту (2); в качестве причины в пункте (1) учтите, что [] является пустым списком, а _ является значением; если вы пишете firstElementsOf([],_), вы вводите извлечение значения (так что неограниченная переменная , _1320 в вашем примере) из пустого списка - person max66; 26.12.2016
comment
Это прекрасно! Конечно, я постараюсь понять каждый кусочек написанного вами текста, но с первого взгляда я вижу, что ваша работа - это именно то, что мне нужно, чтобы закончить этот решатель. Большое тебе спасибо! - person Shuumi; 26.12.2016
comment
@shuumi - немного по теме: судоку - типичная проблема удовлетворения ограничений; в некоторых средах пролога (например, gprolog и swi-prolog) доступна библиотека CLP; Предлагаю поискать и взглянуть на него. - person max66; 26.12.2016