Blocked N-Queens
(Main file name: bq) 
Adapted from the 2009 ASP competition.

The blocked N-queens problem is a variant of the N-queens problem. In the blocked N-queens problem we have an NxN board and N queens. Each square on the board can hold at most one queen. Some squares on the board are blocked and cannot hold any queen. A conflict arises when any two queens are assigned to the same row, column or diagonal. A solution is an assignment of the N queens to the non-blocked squares of the board in a conflict-free manner. 

The input of the blocked N-queens problem specifies the blocked squares on the board, and the number N of queens.

Input formats

An input file for LP systems specifies two predicates: board/1 and block/2. The board/1 is defined by one fact, board(N), which gives the board size. The predicate block/2 is defined by one or more facts of the form block(R,C), which means that the position at row R and column C is blocked.

An input file for Minizinc specifies the size of the board n, the number of blocked positions m, and two arrays, named row and col, respectively, that give the blocked positions.

Output format

The output consists of N facts of the form queen(R,C), which means that there is a queen at square (R,C)'.

Samples


LP InputMinizinc InputOutput
board(4).
block(1,1).
block(2,2).
block(4,3).		n = 4;
m = 3;
row = [1,2,4];
col = [1,2,3];		queen(1,3).
queen(2,1).
queen(3,4).
queen(4,2).
board(4).
block(2,1).
block(2,2).
block(4,2).		n = 4;
m = 3;
row = [2,2,4];
col = [1,2,2];		queen(1,2).
queen(2,4).
queen(3,1).
queen(4,3).
board(5).
block(1,1).
block(2,2).
block(3,3).
block(4,5).
block(5,5).		n = 5;
m = 5;
row = [1,2,3,4,5];
col = [1,2,3,5,5];		queen(1,5).
queen(2,3).
queen(3,1).
queen(4,4).
queen(5,2).