Fixing N-Queens
(Main file name: fqueens)

The N-queens problem is probably one of the most famous problems in computer science. Given an NxN chess board and N queens, the goal of the N-queens problem is to place the N-queens on the squares of the board such that no two queens attack each other, meaning that no two queens are on the same row, the same column or the same diagonal.

You are given a configuration of N-queens on the board, which may not constitute a correct solution to the N-queens problem. Your goal is to transform the configuration into a correct solution by rearranging the queens in the  fewest valid moves. In chess, the queen can move horizontally, vertically, or diagonally, and no other piece can occur between the starting square and the ending square of the move.

Input Formats

An input file for LP systems contains a fact of the form board_size(N), which specifies the number of queens N (4 ≤ N ≤ 6), and N facts of the form pos(R,C), which indicates that there is a queen at row R and column C (1 ≤ R , C ≤ N).

An input file for Minizinc specifies the size of the board, board_size, and two arrays, named row and col, respectively, that give the initial positions of the queens.

Output format

The output should contain exactly one fact of the form moves(K), where K is the minimum number of moves needed to rearrange the queens in the input configuration to build a correct solution to the N-queens problem. For ASP systems, the output may consist of multiple answer sets, and only the final one is treated as a solution.

Samples


LP InputMinizinc InputOutput
board_size(4).
pos(1,2).
pos(2,4).
pos(3,1).
pos(4,3).		board_size = 4;
row = [1,2,3,4];
col = [2,4,1,3];
moves(0).
board_size(4).
pos(1,2).
pos(1,3).
pos(2,1).
pos(4,3).
board_size = 4;
row = [1,1,2,4];
col = [2,3,1,3];		moves(2).
board_size(5).
pos(1,1).
pos(2,5).
pos(3,3).
pos(5,2).
pos(5,5). 		board_size = 5;
row = [1,2,3,5,5];
col = [1,5,3,2,5];		moves(3).