Алгоритм блока судоку в прологе?

как получить все элементы блоков в прологе? размер может меняться динамически в моем коде, поэтому размер блока отличается, 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] ],

Итак, список со списками строк в судоку. проверка строк и столбцов не проблема, -> проверка всех_различных строк, транспонирование всего списка, проверка всех_различных с транспонированным списком.

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

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


list algorithm sudoku prolog
person viktor    schedule 04.06.2011    source источник
comment
Под блоком вы подразумеваете один из девяти сегментов 3x3, на которые делится вся обычная судоку 9x9?   -  person Anko    schedule 04.06.2011

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

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]]
person Howard    schedule 04.06.2011

arrow_upward
1
arrow_downward

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

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 к каждому из них даст требуемый список «коробок». списки.

person hardmath    schedule 04.06.2011