Problem
You are given an n × n chessboard board where each cell contains a natural number. Write a function solution that returns the maximum sum of the numbers written in the cells where n rooks are placed on the board such that no two rooks can attack each other.
Background Information
- The N-Rook problem involves placing
nrooks on ann×nchessboard so that no two rooks can attack each other. - A rook can move any distance in the four directions: up, down, left, and right.
Constraints
nis a natural number between 2 and 10, inclusive.board[i][j]represents the number written in the cell at position (i+1, j+1) on the chessboard, and it is a natural number between 1 and 100, inclusive.
Test Case
| Test Case Number | board | return |
|---|---|---|
| 1 | [[4,4],[9,8]] |
13 |
| 2 | [[2,8,8],[7,9,3],[3,7,10]] |
25 |
| 3 | [[4,5,4,1],[2,1,10,6],[7,2,3,7],[9,2,6,3]] |
31 |
Explanation for Test Case 1
- When rooks are placed at positions (1,2) and (2,1) on the chessboard, the maximum sum is 13.
Explanation for Test Case 2
- When rooks are placed at positions (1,2), (2,1), and (3,3) on the chessboard, the maximum sum is 25.
Explanation for Test Case 3
- When rooks are placed at positions (1,2), (2,3), (3,4), and (4,1) on the chessboard, the maximum sum is 31.
