Пролог блока судоку? - PullRequest
Новая
       14

Пролог блока судоку?

3 голосов
/ 04 июня 2011

как получить все элементы блоков в прологе? размер может меняться динамически в моем коде, поэтому размер блоков различается, 4x4 = 4 элемента, 9x9 = 9 элементов и т. д. блоки делятся на квадраты, поэтому в 4x4 горизонтальная длина округлая (sqrt (4)) = 2 и вертикальная длина блока круглая (sqrt (4)) = 2. и 9x9 ... sqrt (9) .. таким образом, высота и ширина блоков равны 3. Мне нужен алгоритм, чтобы получить эффективные элементы.

мои судокулисты построены так:

L = [ [4,3,1,2], [2,1,4,3], [3,4,2,1], [1,2,3,4] ]

так список, со списками строк в судоку. проверка строк и столбцов не проблема, -> проверка all_different со строками, транспонирование всего списка, проверка all_different с транспонированным списком.

но из-за динамического размера судоку я не могу закодировать код исправления для блоков. так кто-нибудь есть идеи? я думал о сглаживании (L) и работе со смещениями, чтобы получить правильные блоки, но кажется, что это довольно сложно сделать таким образом?

пожалуйста, помогите мне!

Ответы [ 2 ]

2 голосов
/ 04 июня 2011

Возможное решение заключается в следующем (при условии, что у вас есть blocksize x blocksize блоков размером blocksize x blocksize - в стандартном судоку все числа равны, их можно настроить в соответствии с другими раскладками)

  1. Пусть a = [],...,[] будет списком blocksize сегментов.
  2. Разделите каждый ряд на blocksize части.
  3. Поместите первую часть в первое ведро, вторую во второе, и так далее.Если вы достигли последнего сегмента, снова начните с первого.
  4. Сгладьте a полностью
  5. Снова разбейте результат на blocksize x blocksize блоки

В вашем примере: 

L=[ [4,3,1,2], [2,1,4,3], [3,4,2,1], [1,2,3,4] ]
Partitions => [[4,3] [1,2] [2,1] [4,3] [3,4] [2,1] [1,2] [3,4]]
Bucketed => [[4,3] [2,1] [3,4] [1,2]] [[1,2] [4,3] [2,1] [3,4]]
Flattened => [4,3,2,1,3,4,1,2,1,2,4,3,2,1,3,4]
Partitioned => [4,3,2,1], [3,4,1,2], [1,2,4,3], [2,1,3,4]]
1 голос
/ 04 июня 2011

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

transpose([[ ]|_],[ ]) :- !.
transpose(A,[H|T]) :-
    decap_List(A,H,B),
    transpose(B,T).

decap_List([ ],[ ],[ ]).
decap_List([[H|T]|Rows],[H|Hs],[T|Ts]) :-
    decap_List(Rows,Hs,Ts).

Например: 

?- transpose([[1,2,3],[4,5,6],[7,8,9]],X).

X = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]

Заметьте, однако, что для обобщенной матрицы судоку размером K²xK² у вас также есть «все разные» записи в каждом «поле» размера KxK для разбиения матрицы.Используя тот же дизайн, что и раньше, вам также понадобится предикат для переупаковки матрицы судоку в список «коробочных» списков.

Для этого требуется только дополнительный предикат для «разбиения» матрицы на группы. K строк на штуку. 

part_K_rows([ ],_,[ ]) :- !.
part_K_rows(A,K,[H|T]) :-
    get_K_rows(A,K,H,B),
    part_K_rows(B,K,T).

get_K_rows(A,0,[ ],A) :- !.
get_K_rows([H|T],K,[H|Z],B),
    J is K-1,
    get_K_rows(T,J,Z,B).

Применение part_K_rows / 3 к исходной матрице судоку, затем транспонирование каждого из полученных разделов строки и применение part_K_rows /3 каждому из них выдаст необходимый список «коробочных» списков.

...