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.

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.

LP Input | Minizinc Input | Output |

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). |