BABY - Baby

A baby tries to solve the well-known eight-queen puzzle: the problem of placing eight chess queens on an 8×8 chessboard so that no two queens share the same row, column, or diagonal. The baby understands the concept of row and column quite well but diagonal is not very clear to her. As a result she succeeds placing eight queens on the board so that no two queens share the same row or column but there remains the possibility that some queens share the same diagonal.

Given baby's queens (a solution by the baby) and a valid eight-queen solution, it is possible to move baby's queens to positions of queens in the valid solution. Assume that in a single move, a queen can be moved one unit row-wise or column-wise into an unoccupied position.

Write a program to find the minimum number of moves required to move baby's queens to positions of queens in the valid solution. The program should be usable for a more general n -queen puzzle where n queens are placed on an n×n chessboard, 4 ≤ n ≤ 16 . Assume that rows and columns of the chessboard are numbered 1, 2 ... n .


The input consists of multiple test cases.

Each case begins with a line containing the integer n .

Each of the next two lines contains a sequence of n integers. Integers in the first line represent column numbers of baby's queens appearing in rows 1, 2 ... n respectively. In the same way, the second line contains column numbers of queens in the given valid solution. A space separates two consecutive integers in the sequence.

A line containing a zero '0' as the first character follows the last case.


For each test case, print the minimum number of moves required.


Sample Input
1 2 3 4 
3 1 4 2 
3 2 4 1 
3 1 4 2 
5 3 1 4 2 
5 3 1 4 2 
1 5 2 4 3 
3 1 4 2 5 

Sample Output

hide comments
Rafail Loizou: 2020-11-12 13:39:43

Just do top-down if you just want to get the AC. Use memoization since you can have at most 2^16 states to deal with which is pretty small. So for each test case you don't have to do more than 2^16 recursive calls which will work and give you the AC. I would be interested to see in what other way it can be solved like flows and similar definitely gonna try this again.

Last edit: 2020-11-12 13:40:22
abhimanyu_1998: 2019-12-29 12:48:40


rks14: 2019-09-14 15:57:01

Are we assuming that we can move all the queens simultaneously?
Should be mentioned.

tarungupta: 2019-04-07 07:54:34

Since Time Limit is very less, don't take much additional space in dp matrix as initializing all with -1 can cost a TLE.
I used dp matrix of size [100000][20], this costed me a TLE, while changing size to [70000][17] got me AC.

learnerinblack: 2018-06-04 15:34:10

Hint :
Step1 : Make a matrix of nxn named dis where dis[i][j] = the distance between ith queen to the jth final position.
Step2 : Recurrence relation solve(mask) = minimum of( for all i st mask&(1<<i) == 0 solve(mask | (1<<i)) + dis[i][j])
Step3 : Submit the solution and get AC

enzymii: 2018-03-14 09:44:07

Got accepted with min-cost-max-flow rather than dp...

siddharth9820: 2016-12-26 21:26:26

Just do not use bottom-up as the time limit is low.

Furquan Uddin: 2016-09-14 08:28:23

Bottom up DP gave TLE while top down gave AC.

zoooma13: 2016-08-14 03:36:49

For people who want an image :
Hope this helps :)

Last edit: 2018-04-20 02:34:51
jajusantosh: 2016-06-17 07:54:14

will hungarian algorithm work?

Added by:Jimmy
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Kanpur 2007