#!/usr/bin/python
# file: queens.py
# created: 20 Feb 2015, last revision: 20 Feb 2015.
# author: Romeo Rizzi
# content: this example will ask to give a board size and then you are given the opportunity to place some queens on the board. The rest of the queens are then placed by the program to maximize the total number of queens that can be placed without attaching each other.
# main procedures taken from: http://pymprog.sourceforge.net/tutorial.html

from sys import argv, exit, stderr
import os
import pymprog 

def usage():
    print >> stderr, "\nUsage: %s <board_dimension>\nExample: %s 8" % \
        os.path.basename(argv[0])
    exit(1)


# The Queens Problem is to place as many queens as possible on the 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.

def queens(n): # n: size of the chess board
   p = pymprog.model('queens')
   iboard = pymprog.iprod(range(n), range(n)) #create indices
   x = p.var(iboard, 'X', bool) #create variables
   #row wise:
   p.st([sum(x[i,j] for j in range(n)) <= 1 for i in range(n)])
   #column wise:
   p.st([sum(x[i,j] for i in range(n)) <= 1 for j in range(n)])
   #diagion '\' wise
   p.st([sum(x[i,j] for i,j in iboard if i-j == k) <= 1 
                    for k in range(2-n, n-1)])
   #diagion '/' wise
   p.st([sum(x[i,j] for i,j in iboard if i+j == k) <= 1 
                    for k in range(1, n+n-2)])
   p.max(sum(x[t] for t in iboard), 'queens')
   return p,x

n = raw_input("board size = ")
n = int(n)
p,x = queens(n)
ys = raw_input("Would you like to place a queen? [y]/n")
while ys!='n':
   r = raw_input("row [0, %i): "%n)
   c = raw_input("col [0, %i): "%n)
   p.st(x[int(r), int(c)] == 1)
   ys = raw_input("Would you like to place another queen? [y]/n")
 
p.solve(int)
#print "solver status: ", p.p.status
for i in range(n):
   for j in range(n):
       if x[i,j].primal > 0.5: print 'Q',
       else: print '.',
   print

# Loading the instance file
if len(argv) < 2:
    usage()
queens(int(argv[1]))
exit(0)