Репозиторий minizin c benchmarks содержит несколько примеров пентамино .
Вот данные для первого примера :
width = 5;
height = 4;
filled = 1;
ntiles = 5;
size = 864;
tiles = [|63,6,1,2,0,
|9,6,1,2,378,
|54,6,1,2,432,
|4,6,1,2,756,
|14,6,1,2,780,
|];
dfa = [7,5,5,5,5,3,0,2,2,2,2,2,7,5,5,5,5,3,19,4,4,4,4,3,30,4,4,4,4,3,0,10,10,10,10,10,46,8,8,8,8,0,0,12,12,12,12,13,0,15,15,15,15,14,0,16,16,16,16,16,0,18,18,18,18,17,0,20,20,20,20,20,0,21,21,21,21,21,0,22,22,22,22,22,0,23,23,23,23,23,0,28,28,28,28,0,47,22,22,22,22,22,47,23,23,23,23,23,46,11,11,11,11,24,0,26,26,26,26,26,0,25,25,25,25,25,0,27,27,27,27,25,0,29,29,29,29,26,0,31,31,31,31,31,32,0,0,0,0,0,33,0,0,0,0,0,34,0,0,0,0,0,35,0,0,0,0,0,36,0,0,0,0,0,46,9,9,9,9,6,47,16,16,16,16,16,0,35,35,35,35,0,60,35,35,35,35,0,0,37,37,37,37,39,0,39,39,39,39,39,60,37,37,37,37,39,0,40,40,40,40,40,0,41,41,41,41,41,0,42,42,42,42,42,0,43,43,43,43,43,0,45,45,45,45,45,0,47,47,47,47,47,60,47,47,47,47,47,48,0,0,0,0,0,49,44,44,44,44,0,53,38,38,38,38,38,60,0,0,0,0,0,0,50,50,50,50,50,0,51,51,51,51,0,0,52,52,52,52,52,0,54,54,54,54,54,0,55,55,55,55,55,0,56,56,56,56,56,0,57,57,57,57,57,0,60,60,60,60,0,0,58,58,58,58,58,0,59,59,59,59,59,61,55,55,55,55,0,62,0,0,0,0,0,63,0,0,0,0,0,0,62,62,62,62,0,0,63,63,63,63,0,0,2,2,2,2,2,3,4,3,3,3,3,2,0,2,2,2,2,3,4,3,3,3,3,5,9,5,5,5,5,6,0,6,6,6,6,7,0,7,7,7,7,8,0,8,8,8,8,0,9,0,0,0,0,2,0,2,2,2,2,4,4,14,4,4,5,2,2,0,2,2,2,3,3,10,3,3,5,3,3,12,3,3,5,4,4,14,4,4,5,8,8,0,8,8,0,9,9,0,9,9,13,11,11,0,11,11,11,11,11,22,11,11,11,7,7,15,7,7,11,13,13,0,13,13,13,6,6,15,6,6,0,0,0,22,0,0,0,6,6,25,6,6,0,17,17,29,17,17,16,19,19,0,19,19,19,20,20,0,20,20,20,21,21,0,21,21,21,22,22,0,22,22,0,23,23,0,23,23,24,24,24,0,24,24,24,26,26,0,26,26,0,26,26,27,26,26,0,0,0,27,0,0,0,18,18,29,18,18,0,0,0,30,0,0,0,28,28,0,28,28,0,30,30,0,30,30,0,32,32,0,32,32,32,33,33,0,33,33,33,34,34,0,34,34,0,35,35,0,35,35,35,36,36,0,36,36,36,0,0,37,0,0,0,31,31,40,31,31,0,0,0,45,0,0,0,39,39,0,39,39,39,41,41,0,41,41,41,42,42,0,42,42,42,43,43,0,43,43,0,44,44,0,44,44,44,45,45,0,45,45,0,38,38,46,38,38,0,0,0,50,0,0,0,0,0,51,0,0,0,47,47,0,47,47,47,49,49,0,49,49,49,51,51,0,51,51,0,48,48,52,48,48,0,0,0,53,0,0,0,0,0,54,0,0,0,53,53,0,53,53,0,54,54,0,54,54,0,2,2,0,2,2,2,3,3,3,4,3,3,2,2,2,0,2,2,3,3,3,4,3,3,2,2,2,0,2,2,3,3,3,3,8,3,2,2,2,2,0,2,3,3,3,3,8,3,5,5,5,5,0,5,6,6,6,6,0,6,7,7,7,7,0,7,0,0,0,0,9,0,4,4,4,4,13,4,10,10,10,10,0,10,11,11,11,11,0,11,12,12,12,12,0,12,13,13,13,13,0,13,0,0,0,0,14,0,2,2,2,2,0,2,]
Насколько я понимаю, цель состоит в том, чтобы заполнить доску 5 x 4 5 пентамино . Кажется, требуется некоторое перекрытие и / или исключение плиток, что необычно.
Вот решение minizin c :
include "globals.mzn";
int: Q = 1;
int: S = 2;
int: Fstart = 3;
int: Fend = 4;
int: Dstart = 5;
int: width;
int: height;
int: filled;
int: ntiles;
int: size;
array[1..ntiles,1..Dstart] of int: tiles;
array[1..size] of int: dfa;
array[1..width*height] of var filled..ntiles+1: board;
constraint forall (h in 1..height, w in 1..width-1) (
board[(h-1)*width+w] != ntiles+1);
constraint forall (h in 1..height) (
board[(h-1)*width+width] = ntiles+1);
constraint
forall (t in 1..ntiles)(
let {
int: q = tiles[t,Q],
int: s = tiles[t,S],
set of int: f = tiles[t,Fstart]..tiles[t,Fend],
array[1..q,1..s] of int: d =
array2d(1..q,1..s,
[ dfa[i] | i in tiles[t,Dstart]+1..tiles[t,Dstart]+q*s] )
}
in
regular(board,q,s,d,1,f)
);
solve :: int_search(board, input_order, indomain_min, complete) satisfy;
output [show(board)];
I ' Нам не удалось найти много документации по тестам minizin c. Они были частью задачи minizin c в течение нескольких лет, но не больше.
Глава 3 из Тезис Микаэля Лагерквиста , возможно, частично актуален. Он описывает размещение пентамино с использованием ограничения regular в наборе инструментов gecode . Раздел 3.2 иллюстрирует строковое представление для размещения пентамино L с использованием строки регулярного выражения из нулей и единиц: 1, где каждый квадрат доски перекрывает квадрат пентамиино L. Вращения частей обрабатываются в разделе 3.3 с использованием дизъюнкций регулярных выражений. В общем, есть 8 симметрий, которые следует учитывать для каждого пентамино (2 зеркалирования и 4 поворота).
Данные minizin c, приведенные выше, не используют дизъюнкции 8 двоичных строк для представления плиток пентамино, но minizin c код действительно использует ограничение regular.
Я понимаю, что gecode и minizin c работают по-разному, и в этом случае minizin c выбрал альтернативу сложным для чтения и записи дизъюнкциям регулярных выражений двоичных строк. Длинная строка из 864 чисел в переменной dfa, вероятно, является основной частью решения minizin c, которое мне не хватает. Остальное решение (удаление симметрии платы) я, вероятно, смогу понять после этого.
Я не понимаю, как заполнить доску 5 x 4 5 пентамино без наложений и / или исключений. Какова цель этого примера?
Как работает миниизин c плитка пентамино и dfa представление?
Как вращение пентамино и зеркальное отображение работают в этом миниизин c представлении ?
Вот единственное решение платы из приведенного выше кода:
[1, 1, 1, 2, 6, 3, 3, 1, 2, 6, 3, 5, 5, 5, 6, 3, 3, 3, 4, 6]
Вот решение, переформатированное в плату 5 x 4:
[1, 1, 1, 2, 6,
3, 3, 1, 2, 6,
3, 5, 5, 5, 6,
3, 3, 3, 4, 6]
Обратите внимание на 6с. Что они означают?
См. на этой веб-странице для получения полного набора плиток пентамино размером 50, 5 x 4 без наложений, исключений или отверстий.
Там альтернативные подходы для решения такого рода проблем с minizin c. Предикат geost - это одна из возможностей. Ни одна из этих альтернатив не имеет отношения к этому вопросу.
Альтернативные предложения или обсуждения программного обеспечения, помимо minizin c и gecode, снова не актуальны.