Точки зрения Судоку

Question

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

Классическая точка зрения заключается в использовании переменных конечной области (строки, столбца), которые могут принимать значения от 1 до 9. Это хорошая точка зрения, и для нее легко определить ограничения. Например: (1,2) переменная со значением 4 означает, что 4 находится в строке 1 в столбце 2.

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

Есть ли другие хорошие точки зрения там?

РЕДАКТИРОВАТЬ: хорошая точка зрения должна позволять ограничения быть кратко выражены. Я предпочитаю точки зрения, которые позволяют описать проблему, используя как можно меньше ограничений, при условии, что эти ограничения имеют эффективные алгоритмы.

Определение точки обзора: точка обзора - это пара X,D, где X = {x1, . , , , xn} - набор переменных, а D - набор доменов; для каждого xi ∈ X соответствующая область D i является множеством возможных значений для x. Должна быть возможность приписать значение переменным и значениям CSP в терминах задачи P, и, таким образом, сказать, что назначение в точке X, D предназначено для представления в терминах P.

Answer 1

Точки зрения, которые вы дали, представляют собой гомоморфное отображение позиционного кодирования отношения, из которого строится судоку (строка, столбец, цифра).

Другим подходом может быть кодирование наборов ограничений (строки [1-9], столбцы [1-9], квадраты [ul, ит,ur,ml,mm,mr,ll,lm,lr] или любые другие ограничения) и находится ли в нем определенная цифра. Это, вероятно, будет ужасно в отношении определения ограничений. (Так что я думаю, это следует считать плохим). Требуется, чтобы кодирование отношения между наборами ограничений было "известно" отдельно.

Например, a (2,5,7) в классической точке зрения подразумевает (row2,7),(col5,7) и (ит, 7) в этой альтернативе.

Как видите, проблема заключается в кодировании отношения между логической позицией и различными ограничениями. Классический vieport строится на кодировании позиционных данных и накладывает ограничения на возможные места размещения. (То, как судоко объясняется и подходит для решения.) Альтернативой является использование наборов ограничений в качестве точек обзора и необходимость адресации в качестве ограничений.

Нормальные люди могут получить узел в их мозгах от такого представления, все же. (И я бы не стал добровольно выяснять ограничения...)

Answer 2

Еще одна возможная точка зрения заключается в следующем:

Давайте сначала свяжем число с каждой областью 3x3 (верхний левый - 1, верхний - 2 и т. Д.), А внутри каждой из этих областей - число со всеми 9 квадратами в нем (верхний левый - 1, верхний - 2, так далее.).

X = {X_{i, j} | i ∈ 1..9, j ∈ 1..9} где X_{i, j} имеет область 1..9 и обозначает место числа i в области j. Ограничение региона уже закодировано с помощью этой модели, остальные два являются ограничениями строки и столбца.

Вот ограничение строки: for each number i ∈ 1..9 for each (a,b,c) ∈ {(1,2,3),(4,5,6),(7,8,9)} (Xi,a,Xi,b,Xi,c) ∈ {(1,4,7),(1,4,8),(1,4,9),(1,5,7),(1,5,8),(1,5,9),(1,6,7),(1,6,8),(1,6,9),(2,4,7),(2,4,8),(2,4,9),(2,5,7),(2,5,8),(2,5,9),(2,6,7),(2,6,8),(2,6,9),(3,4,7),(3,4,8),(3,4,9),(3,5,7),(3,5,8),(3,5,9),(3,6,7),(3,6,8),(3,6,9)}

Ограничение столбца аналогично, но с (a,b,c) ∈ {(1,4,7),(2,5,8),(3,6,9)}.

Это представление основано на регионах, но существуют два других похожих представления, основанных на строке и столбцах.

Существуют и другие представления, например, вы можете иметь X = {X_{i, j} | i ∈ 1..9, j ∈ 1..9} ∪ {Y_{i, j} | i ∈ 1..9, j ∈ 1..9} где X_{i, j} - строка (от 1 до 3) числа i в области j, а Y_{i, j -} ее столбец. Все, что вам нужно сделать, это выяснить, как выразить ограничения.