67_itmo


Группа К4132 СПбГУ ИТМО


Previous Entry Share Next Entry
Эвристический алгоритм решения судоку, основанный на байесовских оценках
matholimp wrote in 67_itmo
Классическое понятие вероятности основано на возможности повторять один и тот же эксперимент. Здесь нам потребуется иной подход: учёт имеющейся в наличии информации. Например, если в некоторой строке судоку остались две свободные клетки, то для каждой из двух неиспользованных цифр вероятность оказаться в той или иной клетке принимаем за 50%.
Ситуация становится чуть сложнее, когда нарушается симметрия. Например, если в некоторой строке судоку остались три свободные клетки, но какая-то из трёх неиспользованных цифр заведомо не может стоять в одной из этих клеток. Начните с этого упражнения и аналогичных ему, но с большим числом неиспользованных цифр и запретов.
Затем перейдите к основной задаче. С самого начала введите два параметра m и n для размеров прямоугольного блока. В "классическом" судоку m=n=3.
Для вероятности того, что в выбранной клетке стоит выбранная цифра рассмотренное выше упражнение позволяет получить три оценки: для строки, для столбца и для прямоугольного блока. Сначала зафиксируйте эти оценки для каждой клетки и каждой цифры. Если какая-то цифра уже стоит или обязательно должна стоять в этой клетке, то все три вероятности окажутся равными единице. А если какая-то цифра заведомо не может стоять там, то все три вероятности окажутся нулями. В остальных случаях эти оценки будут отличаться от 0 и 1, причём могут быть различными.
Назовём наименьшую из трёх оценок нижней вероятностью, наибольшую - верхней, а оставшуюся - промежуточной. Кроме того, введём ещё одну вероятность - экспертную. Например, на этом этапе решения её значение можно взять равным среднему арифметическому нижней, верхней и промежуточной вероятностей.
Следующий шаг алгоритма - попытка устранить конфликта баланса. Ясно, что "в норме" (в частности, когда задача будет решена) в каждой клетке сумма вероятностей для всех цифр должна быть равна 1. Кроме того, для каждой цифры сумма всех вероятностей по строке, по столбцу или по прямоугольному блоку должна быть равна 1. Но пока хотя бы одна из оценок будет отличаться от 0 и 1, в соответствующих клетке, строке, столбце или прямоугольном блоке сумма нужных вероятностей не будет равна 1. Чтобы восстановить баланс, нужно пропорционально изменить все вероятности клетки, строки, столбца или прямоугольного блока. При этом нужно следить, чтобы промежуточная вероятность была больше нижней и меньше верхней.
Здесь возникает множество вариантов, в зависимости от выбора последовательности вычислений, учёта конфликта между новыми и прежними значениями одних и тех же вероятностей и т.п. Я надеюсь, что из этого множества вариантов каждый студент выберет свой собственный путь, отличающийся от остальных.
В идеале Ваш алгоритм должен завершиться, когда значения всех вероятностей окажутся равными 0 и 1, причём все нижние вероятности будут равны соответствующим верхним. Чтобы избежать бесконечного числа итераций, возможно, Вам придётся применить операцию "принудительного" предельного перехода. Например, если какая-то из вероятностей превысила 90% и продолжает монотонно возрастать, то есть все основания заменить её единицей. Более рискованная замена: приравнять к 0 вероятность, которая стала меньше 1% и продолжает монотонно убывать.
Если же ситуация стабилизируется, но значения некоторых вероятностей далеки от 0 и 1, то это может означать, что исходная головоломка имела несколько решений. Попробуйте выйти из этой ситуации, резко изменив какую-то из таких вероятностей.

?

Log in