На этой странице представлены подробные исправленные упражнения задачи логическое программирование ограничениями, что является естественным сочетанием логического программирования и программирование ограничений.
Упражнение 1
Рассмотрим следующую головоломку:
Каждая область сетки должна быть заполнена числом от 0 до 9, чтобы
- числа в двух соседних регионах (по вертикали или по горизонтали) разные
- всякий раз, когда есть четыре области, которые встречаются в точке (обозначенной маленьким кружком), сумма их номеров равна 20.
Решите эту проблему с помощью логического программирования ограничений.
Решение
Назовем сверху слева направо (по строке) пустые квадраты по букве. Каждый домен имеет значение от 0 до 9. После этого два ограничения необходимо заполнить вручную.
Для каждого квадрата его счет должен отличаться от его соседей.
Для каждого круга сумма должна быть равна 20.
Таким образом, у нас есть следующее программирование логики ограничений:
L = [A,B,C,D,E,F,G,H,I,J,K,M],
Л::[0..9],
При #\= 7, При #\= 8, При #\= 6,
В #\= 8, В #\= 4,
С #\= 7, С #\= 6, С #\= 9,
Д 1ТР4Т\= 6, Д 1ТР4Т\= 8,
Е 1ТР4Т\= 6, Е 1ТР4Т\= 8, Е 1ТР4Т\= 4, Е 1ТР4Т\= 5,
F #\= 9, F #\= 6, F #\= G, F #\= Y,
G #\= 6, G #\= 5, G #\= K,
Н 1ТР4Т\= 5, Н 1ТР4Т\= 4, Н 1ТР4Т\= М,
I #\= 9, I #\= J, J #\= K,
К 1ТР4Т\= 5, К 1ТР4Т\= М,
7+6+A+C #= 20, A+6+8+D #= 20, 6+8+D+E #= 20, 4+8+B+E #= 20,
9+6+C+F #= 20, 5+6+E+G #= 20, 4+5+E+H #= 20,
9+F+I+J #= 20, F+G+J+K #= 20, 5+H+K+M #= 20,
маркировка(L).
Упражнение 2
Рассмотрим игру Боккусу. Цель игры состоит в том, чтобы отметить определенные квадраты заданной сетки черным цветом.
Каждое поле имеет два значения: значение A и значение B. Числа справа обозначают значения A полей в каждой соответствующей строке, а числа внизу обозначают значения B полей в каждом соответствующем столбец (Эти значения всегда варьируются от 1 до размера сетки, увеличиваясь на 1 слева направо или сверху вниз).
Значения слева указывают сумму значений B черных ящиков для каждой строки, а значения вверху указывают сумму значений A черных ящиков для каждого столбца. Пример сетки и ее решение приведены на рисунке. В решении этого примера у нас есть, например, 7 = 1 + 2 + 4 (ящики со значением B 1, 2 и 4 отмечены черным) и 6 = 2 + 4 (ящики со значениями A 2 и 4 отмечены).
Решите эту проблему с помощью логического программирования ограничений.
Решение
Давайте назовем каждый квадрат в сетке матричным способом. Для ограничений сумма бинарных переменных (белый=0 или черный=1), умноженная на коэффициенты слева или сверху, должна быть равна значению напротив.
Л = [Х11,Х12,Х13,Х14,
С21, С22, С23, С24,
С31, С32, С33, С34,
Х41,Х42,Х43,Х44],
fd_domain(L,0,1),
Х11 + 2*Х12 + 3*Х13 + 4*Х14 #= 3,
Х21 + 2*Х22 + 3*Х23 + 4*Х24 #= 7,
Х31 + 2*Х32 + 3*Х33 + 4*Х34 #= 1,
Х41 + 2*Х42 + 3*Х43 + 4*Х44 #= 2,
Х11 + 2*Х21 + 3*Х31 + 4*Х41 #= 5,
Х12 + 2*Х22 + 3*Х32 + 4*Х42 #= 6,
Х13 + 2*Х23 + 3*Х33 + 4*Х43 #= 1,
Х14 + 2*Х24 + 3*Х34 + 4*Х44 #= 2.
Упражнение 3
Рассмотрим задачу формирования расписания. Есть 7 классов и 4 слота. Слот может вместить максимум 2 урока. Существуют следующие ограничения:
– Курс 4 должен быть перед курсом 6.
– Курс 5 должен быть перед курсом 7.
– Курс 6 должен быть перед курсом 2.
– Курс 1 не может проходить параллельно с курсами 2, 3, 4 и 7.
– Курс 2 не может проходить параллельно с курсами 3 и 6.
– Курс 3 не может проходить параллельно с курсами 4, 5 и 6.
– Курс 4 не может проходить параллельно с курсами 5 и 6.
– Курс 5 не может быть параллелен курсу 7.
Решите эту проблему с помощью логического программирования ограничений.
Решение
Мы будем считать, что курсы являются доменами и могут принимать значения от 1 до 4, соответствующие нише, которая будет выбрана. Программирование логики ограничений выглядит следующим образом:
L = [С1,С2,С3,С4,С5,С6,С7],
fd_domain(L,1,4),
C4 #< C6, C5 #< C7, C6 #< C2,
C1 #\= C2, C1 #\= C3, C1 #\= C4, C1 #\= C7,
С2 1ТР4Т\= С3, С2 1ТР4Т\= С6,
C3 #\= C4, C3 #\= C5, C3 #\= C6,
С4 1ТР4Т\= С5, С4 1ТР4Т\= С6,
С5 1ТР4Т\= С7,
fd_cardinality(1,[C1#=1,C2#=1,C3#=1,C4#=1,C5#=1,C6#=1,C7#=1],2),
fd_cardinality(1,[C1#=2,C2#=2,C3#=2,C4#=2,C5#=2,C6#=2,C7#=2],2),
fd_cardinality(1,[C1#=3,C2#=3,C3#=3,C4#=3,C5#=3,C6#=3,C7#=3],2),
fd_cardinality(1,[C1#=4,C2#=4,C3#=4,C4#=4,C5#=4,C6#=4,C7#=4],2),
fd_labeling(L)
Упражнение 4
Inshi no heya — японская логическая игра. В нее играют на прямоугольной сетке ячеек, разделенных на прямоугольники. Одно измерение каждого прямоугольника равно 1, а другое измерение варьируется.
Каждый прямоугольник расположен горизонтально или вертикально и содержит число. Цель состоит в том, чтобы
заполните все ячейки числами от 1 до 9 так, чтобы:
– Если мы перемножим все цифры каждого прямоугольника, мы получим число, указанное в прямоугольнике
– Ни одно число не появляется в столбце более одного раза.
– Ни одно число не встречается в строке более одного раза.
Пример исходной сетки и решения приведены ниже:
Решите эту проблему с помощью логического программирования ограничений.
Решение
Каждый ящик матрицы рассматривается как домен, каждый ящик может принимать значение от 1 до 5. Ограничения просты, так как сумма ящиков определенного периметра должна быть равна заданному числу.
Л = [Х11,Х21,Х31,Х41,Х51,
С12, С22, С32, С42, С52,
С13, С23, С33, С43, С53,
С14, С24, С34, С44, С54,
С15,С25,С35,С45,С55],
fd_domain(L,1,9),
fd_all_differ([X11,X12,X13,X14,X15]),
fd_all_differ([X21,X22,X23,X24,X25]),
fd_all_differ([X31,X32,X33,X34,X35]),
fd_all_differ([X41,X42,X43,X44,X45]),
fd_all_differ([X51,X52,X53,X54,X55]),
fd_all_differ([X11,X21,X31,X41,X51]),
fd_all_differ([X12,X22,X32,X42,X52]),
fd_all_differ([X13,X23,X33,X43,X53]),
fd_all_differ([X14,X24,X34,X44,X54]),
fd_all_differ([X15,X25,X35,X45,X55]),
X11 #= 5, X31*X41 #= 2, X32*X42 #= 4, X33 #= 4,
X43*X53 #= 15, X34*X44 #= 15, X15*X25*X35*X45 #= 120,
X21*X22 #= 15, X51*X52 #= 12, X12*X13*X14 #= 8,
Х23*Х24 1ТР4Т= 2, Х54*Х55 1ТР4Т= 2,
fd_labeling(L)
Упражнение 5
Небоскребы строятся по сетке NxN. Каждый небоскреб имеет количество этажей, соответствующее его размеру (от 1 до N). В каждом столбце и каждой строке каждый размер появляется ровно один раз. Цифры по краям сетки показывают, сколько небоскребов можно увидеть, если смотреть с этой точки на соответствующую строку или столбец. Небоскреб виден, если все небоскребы перед ним меньше. Вот пример сетки и ее решения:
Например, во второй строке снизу, если смотреть слева, мы видим 2 небоскреба: один высотой 3, а другой высотой 4. Вот вторая задача сетки (5×5), которую нужно решить:
Решите эту проблему с помощью логического программирования ограничений.
Решение
Вы можете использовать предопределенный предикат fd_cardinality(+List, ?Count)
где List — это список ограничений, а Count — количество удовлетворенных ограничений List.
ограничение([A1,A2,A3,A4,A5],C):-
fd_cardinality([A5 #>A4 #/\A5 #>A3 #/\A5 #>A2 #/\A5 #>A1,
A4 #>A3 #/\A4 #>A2 #/\A4 #>A1,
A3 #> A2 #/\A3 #> A1, A2 #> A1],C).
небоскреб(L):-
L = [Строка1,Строка2,Строка3,Строка4,Строка5],
Строка1 = [X11,X12,X13,X14,X15],
Строка2 = [X21,X22,X23,X24,X25],
Строка3 = [X31,X32,X33,X34,X35],
Строка4 = [Х41,Х42,Х43,Х44,Х45],
Строка5 = [X51,X52,X53,X54,X55],
fd_domain(строка1,1,5),fd_domain(строка2,1,5),
fd_domain(строка3,1,5),fd_domain(строка4,1,5),
fd_domain(строка5,1,5),
fd_all_ Different (строка 1), fd_all_ Different (строка 2),
fd_all_ Different (Строка 3), fd_all_ Different (Строка 4),
fd_all_ Different (строка 5),
fd_all_differ([X11,X21,X31,X41,X51]),
fd_all_differ([X12,X22,X32,X42,X52]),
fd_all_differ([X13,X23,X33,X43,X53]),
fd_all_differ([X14,X24,X34,X44,X54]),
fd_all_differ([X15,X25,X35,X45,X55]),
% Первый небоскреб еще виден. Итак, вам нужно удалить 1
% за каждое количество видимых небоскребов.
ограничение (строка1,0), ограничение (строка2,3), ограничение (строка3,2),
ограничение (строка 4,1),
ограничение([X12,X22,X32,X42,X52],2),
ограничение([X13,X23,X33,X43,X53],2),
ограничение([X15,X14,X13,X12,X11],2),
ограничение([X25,X24,X23,X22,X21],1),
ограничение([X35,X34,X33,X32,X31],2),
ограничение([X55,X54,X53,X52,X51],0),
ограничение([X52,X42,X32,X22,X12],1),
ограничение([X53,X43,X33,X23,X13],1),
ограничение([X54,X44,X34,X24,X14],1),
ограничение([X55,X45,X35,X25,X15],0),
fd_labeling(Line1),fd_labeling(Line2),fd_labeling(Line3),
fd_labeling(строка4),fd_labeling(строка5).
RU 
FR 
EN 
ES