/* 

  Queens problem, integer programming in Picat.

  From GLPK:s example queens.mod
  """
  QUEENS, a classic combinatorial optimization problem

  Written in GNU MathProg by Andrew Makhorin <mao@mai2.rcnet.ru>

  The Queens Problem is to place as many queens as possible on the 8x8
  (or more generally, nxn) chess board in a way that they do not fight
  each other. This problem is probably as old as the chess game itself,
  and thus its origin is not known, but it is known that Gauss studied
  this problem.
  """

  Note: I skip the optimization problem and use a sat problem, i.e.
        that Obj == N.


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import mip.


main => go.

go ?=>
  % size of the chess board 
  N = 100,

  % x[i,j] = 1 means that a queen is placed in square [i,j] 
  X = new_array(N,N),
  X :: 0..1,

  % at most one queen can be placed in each row 
  foreach(I in 1..N)
    sum([X[I,J] : J in 1..N]) #<= 1
  end,

  % at most one queen can be placed in each column 
  foreach(J in 1..N)
    sum([X[I,J] : I in 1..N]) #<= 1
  end,

  % at most one queen can be placed in each "\"-diagonal 
  foreach(K in 2-N..N-2)
    sum([X[I,J] : I in 1..N, J in 1..N, I-J == K]) #<= 1
  end,

  % at most one queen can be placed in each "/"-diagonal 
  foreach(K in 3..N+N-1)
    sum([X[I,J] : I in 1..N, J in 1..N, I+J == K]) #<= 1
  end,

  % objective is to place as many queens as possible 
  Obj #= sum([X[I,J] : I in 1..N, J in 1..N]),
  Obj #= N,

  % solve($[max(Obj)],X.vars),
  solve($[degree,updown],X.vars),  

  println(obj=Obj),
  foreach(Row in X)
    println(Row)
  end,
  nl,
  % fail,

  nl.

go => true.