Book of programming problems

Complexity (1-100): 20

Each square of the chess board is marked with a natural number. Put eight rooks on the board so that they are not under attack and the sum of numbers of the occupying squares is minimal.

Self-test:

The chess-board (download: input.txt):
9 0 9 9 9 9 9 9
9 9 0 9 9 9 9 9
9 0 0 0 0 0 0 9
9 0 9 9 9 9 9 0
0 9 9 9 9 9 9 9
9 9 9 9 9 9 9 0
9 9 9 9 9 9 9 0
9 9 9 9 9 9 9 0

Optimal rooks placement:
Column 1 row 5
Column 2 row 1
Column 3 row 2
Column 4 row 3
Column 5 row 4
Column 6 row 6
Column 7 row 7
Column 8 row 8
The minimal sum is 27

From the problem definition it is clear that each column and row should have exactly one rook. The solultion therefor is a permitation of rows A=(a₁,a₂,...,a₈), where  1 ≤ a_i ≤ 8 is the index of a row for rook standing at column with index i. In the self-test, for example, the solution is described by the vector (5,1,2,3,4,6,7,8). Let m[i, j] be the number at the ith row and jth column of the chessboard. Then the solution cost is the sum m[a₁,1]+m[a₂,2]+...+m[a_k,k].

The simplest solution to the problem is using the backtracking algorithm. At each step we select a_k different from any of a₁ - a_k-1. We than check that the cost of this partial solution (a₁,..., a_k) does not exceed the cost of the best solution already found. If it does not, we select the (k+1)th component of the vector and so on until k reaches 8. If that happen, we check if we've found the best solution of those already encountered. See the algortithm.