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

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

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

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

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

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

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


constraint-programming sudoku prolog
person Stanko    schedule 14.03.2016    source источник
comment
Отсутствующий аспект в вашем вопросе - это определение добра.   -  person rpy    schedule 14.03.2016
comment
@rpy Точка зрения должна позволять кратко выражать ограничения. Я предпочитаю точки зрения, которые позволяют описать проблему с использованием как можно меньшего количества ограничений, если эти ограничения имеют эффективные алгоритмы.   -  person Stanko    schedule 14.03.2016

Ответы (2)


arrow_upward
1
arrow_downward

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

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

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

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

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

person rpy    schedule 14.03.2016
comment
Что касается определения добра, добавленного в то же время, я предполагаю, что не будет никаких других хороших точек зрения. Мое нестандартное представление определенно не позволит использовать (очевидно) эффективные алгоритмы. - person rpy; 14.03.2016

arrow_upward
0
arrow_downward

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

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

Х={Хi,j | i ∈ 1..9, j ∈ 1..9 }, где Xi,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={Xi,j | i ∈ 1..9, j ∈ 1..9 } ∪ {Yi,j | i ∈ 1..9, j ∈ 1..9 } где Xi,j — строка (от 1 до 3) числа i в области j, а Yi,j< /sub> свой столбец. Все, что вам нужно сделать, это выяснить, как выразить ограничения.

person Viperens    schedule 08.11.2016