Day 4 : N Queen with Max Score

hardBacktracking

You have been given an 8X8 chessboard with each square having a score attached to it. You need to place 8 queens on the board such that none of the queen is attacked by the other and the sum of scores of squares occupied by the queens is maximum. You need to only give the max sum of scores.

Input Format:

The first line of input contains $t$ the number of testcases. The Input of each of the following $t$ testcases contains 8 lines each having 8 integers denoting the scores of each square of the chessboard. Each integer will lie between 1 and $10^5$.

Output Format:

Give $t$ integers denoting the answer to each of the testcases

Constraints:

($1 \le t \le 10$)
($1 \le score \le 10^5$).

Examples:

Example 1:

Input:

1
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

Output:

Code

Loading Editor...