Пазл небоскреб с модулем ограничений в python - PullRequest
Новая
       75

Пазл небоскреб с модулем ограничений в python

0 голосов
/ 07 мая 2020

У меня есть задание, в котором я должен решить загадку с небоскребом, это конкретная c проблема. Это головоломка, сделанная в сетке 4x4, в которой каждое поле сетки имеет различное значение в строках и столбцах (как судоку). Значения внутри полей показывают нам высоту небоскреба, построенного на этом поле (1-4, 4 - самое высокое здание). Цифры за пределами сетки - это количество небоскребов, видимых с этого направления. (например, с этого направления вы можете видеть только один небоскреб, потому что самое высокое (4 здания) закрывает вид на другие -> 4312 <- с этого направления вы можете видеть три здания (покрыто только здание высотой 1)). Даны только числа снаружи, и вы должны заполнить сетку. Подробнее о правилах игры: <a href="http://www.brainbashers.com/skyscrapershelp.asp?fbclid=IwAR3loZmrSHbxknEL6MAkwFBchMZmpbl4uPPKT3QGgQIg-3OpjoQ54PkiulE" rel="nofollow noreferrer"> здесь

Это - начальное состояние и это - один из возможных выходов.

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

problem = Problem()

variables = range(16)
domains = range(1, 5)
problem.addVariables(variables, domains)

for row in range(4):
    problem.addConstraint(AllDifferentConstraint(), [row * 4 + i for i in range(4)])

for col in range(4):
    problem.addConstraint(AllDifferentConstraint(), [col + 4 * i for i in range(4)])


solution = problem.getSolution()
print(solution)

1 Ответ

1 голос
/ 08 мая 2020

Вот решение, использующее MiniZin c (извините за то, что не предоставил решение Python): 

include "globals.mzn";

int: N = 4;
set of int: POS = 1..N;
set of int: SEEN = 1..N;
set of int: HEIGHT = 1..N;

array[POS] of SEEN: top = [2, 1, 2, 2];
array[POS] of SEEN: bottom = [2, 4, 3, 1];
array[POS] of SEEN: left = [2, 3, 1, 2];
array[POS] of SEEN: right = [2, 2, 3, 1];    

array[POS, POS] of var HEIGHT: height;

constraint forall(p in POS)
    (all_different(row(height, p)) /\
     all_different(col(height, p)));

predicate sum_seen(array[POS] of var HEIGHT: values, int: seen) = 
    (sum(i in 2..N)(values[i] > max([values[j] | j in 1..i-1])) = seen - 1);

constraint forall(p in POS)
    (sum_seen(row(height, p), left[p]) /\
     sum_seen(reverse(row(height, p)), right[p]) /\
     sum_seen(col(height, p), top[p]) /\
     sum_seen(reverse(col(height, p)), bottom[p]));

solve satisfy;

output ["height = "] ++ [show2d(height)];

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

...