Верен ли мой эвристический алгоритм? (решатель судоку)

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

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

1. Select an empty cell. 
  1a. If there are no empty cells and there is a solution return solution.
      Else return No.
2. Find all possible values it can hold. %% It can't take values currently assigned to cells on the same line/column/box.
3. Set to all those values a heuristic number starting from 1.
4. Pick the value whose heuristic number is the lowest && you haven't checked yet.
   4a. If there are no more values return no.
5. If a solution is not found: GoTo 1.
   Else Return Solution.

// I am sorry for errors in this "pseudo code." If you want any clarification let me know.

Так я правильно делаю или есть другой способ, а мой неверный? Заранее спасибо.


algorithm sudoku heuristics prolog
person Theocharis K.    schedule 12.04.2012    source источник
comment
Что произойдет, если алгоритм выберет неправильное значение на шаге 4? Что произойдет, если головоломка еще не собрана, но остались пустые ячейки без вариантов на шаге 2?   -  person wildplasser    schedule 13.04.2012
comment
@wildplasser Это просто псевдокод эвристической функции, функции, которая просто помещает значения в разные пути, которые может выбрать программа. Ошибки и т. д. будут обработаны в основной программе, если вы это имеете в виду. Этот алгоритм не решит судоку, он просто подскажет, что делать дальше.   -  person Theocharis K.    schedule 13.04.2012
comment
В дополнение к другим ответам, вот некоторые тактики, которые вы можете использовать, чтобы максимально избежать догадок: /а>   -  person Dialecticus    schedule 13.04.2012

Ответы (3)


arrow_upward
1
arrow_downward

Эвристика, которую я бы использовал, такова:

  1. Несколько раз найдите все пустые места, где есть только одно возможное число, которое вы можете вставить. Заполните их числом 1-9, которое подходит.
  2. Если у каждого пустого места есть две или более возможностей, поместите состояние игры в стек, затем выберите случайный квадрат, чтобы заполнить его случайным значением.
  3. Перейти к шагу 1.

Если вам удастся заполнить каждый квадрат, вы нашли верное решение.

Если вы дойдете до точки, где нет допустимых вариантов, извлеките последнее игровое состояние из стека (т. е. вернитесь к тому моменту, когда вы в последний раз делали случайный выбор). Сделайте другой выбор и повторите попытку.

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

person Li-aung Yip    schedule 13.04.2012
comment
Это действительно кажется намного лучше, чем у меня. Но считается ли моя функция эвристической? Просто интересуюсь... - person Theocharis K.; 13.04.2012
comment
@Aposperite: эвристика - это просто правило или практическое правило. Я бы сказал, что ваш имеет значение, даже если он указан неточно / спецификация слишком сложна. - person Li-aung Yip; 13.04.2012
comment
Я бы добавил, что когда вы вынуждены угадывать квадрат, хорошей эвристикой было бы выбрать квадрат, который имеет только два возможных варианта (в отличие от девяти возможных вариантов). Шансы на правильное предположение выше, если у вас меньше вариантов. - person Li-aung Yip; 13.04.2012

arrow_upward
1
arrow_downward

Когда я сам написал решатель судоку на Прологе, я использовал следующий алгоритм:

  1. отфильтровать уже решенные ячейки (т.е. заданные значения в начале)
  2. для каждой ячейки создайте список, содержащий всех ее соседей (это 20 ячеек).
  3. для каждой ячейки создайте список, содержащий все возможные значения, которые она может принимать (это легко сделать после выполнения вышеуказанного)
  4. в списке, содержащем все ячейки для решения, поместите вверху ту, у которой минимальное количество доступных значений
  5. если в верхней ячейке осталось 0 вариантов, перейдите к 7, иначе перейдите к 6, если список пуст, у вас есть решение.
  6. для ячейки вверху списка: выбрать случайное число из возможных значений ячейки. Удалите это значение во всех возможных значениях его соседей. Перейти к 5.
  7. возврат (т. е. ошибка в Прологе)

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

person m09    schedule 13.04.2012

arrow_upward
1
arrow_downward

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

Вот реализация эвристики наиболее ограниченной переменной в C#: Упражнение №2: Решение судоку

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

person Zoran Horvat    schedule 17.07.2013