/* Schuh's queen placement problem in Picat. From Martin Chlond Integer Programming Puzzles: http://www.chlond.demon.co.uk/puzzles/puzzles2.html, puzzle nr. 10. Description : Schuh's queen placement problem Source : Schuh, F., (1943), Wonderlijke Problemen; Leerzam Tijdverdrijf Door Puzzle en Speel, W.J. Thieme & Cie, Zutphen. """ Place eight queens on a chessboard in such a way that none of the queens is attacking another queen. (Schuh) """ This model was inspired by the XPress Mosel model created by Martin Chlond. http://www.chlond.demon.co.uk/puzzles/sol2s10.html This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ % import sat. % 6.1s import cp. % 0.008s % import mip. % 0.13s main => time2(go). go => Size = 8, % X[I,J] = 1 if square occupied, 0 otherwise X = new_array(Size,Size), X :: 0..1, % A[I,J] = 1 if square attacked, 0 otherwise A = new_array(Size,Size), A :: 0..1, NumQ #= sum([X[I,J] : I in 1..Size, J in 1..Size]), NumQ #=< Size, % a(i,j) = 1 if square (i,j) attacked foreach(I in 1..Size, J in 1..Size) sum([X[M,M-I+J] : M in 1..Size, M != I, M-I+J >= 1, M-I+J <= Size]) + sum([X[M,I+J-M] : M in 1..Size, M != I, I+J-M >= 1, I+J-M <= Size]) + sum([X[M,J] : M in 1..Size, M != I]) + sum([X[I,N] : N in 1..Size, N != J]) #=< 99*A[I,J], % each square either attacked or occupied A[I,J]+X[I,J] #= 1 end, solve($[ff,max(NumQ)], A ++ X), println(numQ=NumQ), println("X:"), print_mat(X), printf("Queens positions: %w\n", [[J : J in 1..Size, X[I,J] == 1] : I in 1..Size].flatten()), println("A:"), print_mat(A), nl. print_mat(X) => foreach(Row in X) println(Row.to_list()) end.