Problem 167 -- The Sultan's Successors

read problem

Tips

An n-Queen problem.

My solution is to find out all possible solutions first (less than 100). Store the solutions in the program. Calculate the sums and store them in an array. Find out the largest value in the array and output it.

Efficiency is guaranteed.

Be careful in parsing the input file. They do not mention whether any spaces or blank lines are allowed. Get prepared to handle them.

Test Cases

Input

6
     1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
  17 18 19 20 21 22 23 24
   25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
   48 50 51 52 53 54 55 56
 57 58 59 60 61 62 63 64
33 34 35 36 37 38 39 40
 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
6 8 50 51 99 53 54 55 56
17 18 19 20 21 98 23 24
41 42 43 44 45 46 47 48
25 80 27 28 29 30 31 32
57 58 59 60 61 62 63 64
99 99 99 99 99 99 99 00 
99 99 99 99 99 99 99 99 
99 99 00 99 99 99 99 99 
99 99 99 99 99 99 99 99 
99 99 99 99 00 99 99 99 
00 99 99 99 99 99 99 99 
99 99 99 99 99 99 99 99 
99 99 99 99 99 99 99 99 
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
00000 0000 0000 0000 0000      0000      000   0000 
00000 0000 0000 0000 0000      0000      000   0000 
00000 0000 0000 0000 0000      0000      000   0000 
00000 0000 0000 0000 0000      0000      000   0000 
00000 0000 0000 0000 0000      0000      000   0000 
00000 0000 0000 0000 0000      0000      000   0000 
00000 0000 0000 0000 0000      0000      000   0000 
00000 0000 0000 0000 0000      0000      000   0000 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
00000 0000 0000 0000 0000      0000      000   0000 

Output

  260
  389
  792
    8
    0
    0