Placing the knights
Statement
K knights are placed on an N×N board, and you want to rearrange their positions to score as high as possible. Each knight can stay where it is or move to one of 8 positions relative to its current position. Every knight may move at most once, and no knight may leave the board. Also, after the rearrangement no single position (cell) on the board may hold two or more knights.
On the starting board, every position holding a knight is marked 0. Every place without a knight is marked with a number greater than 0, which stands for a score. A score is always a natural number from 1 to 100. When a knight moves onto a cell that holds a score (a cell with a number greater than 0), it gains that value as score. As noted above, each knight may move from its starting position to one of 8 positions if it wants to, and it moves the same way a knight moves in chess or in janggi (Korean chess).
Write the position of each cell on the board as (row, column), and assume indices start from 0. When one knight is at position (3, 3), the positions it can move to are drawn below. Specifically, it can move to (1, 2), (1, 4), (2, 1), (2, 5), (4, 1), (4, 5), (5, 2) and (5, 4). In the figure below, the 8 shaded positions are the ones it can move to.
| ● | ● | |||||
| ● | ● | |||||
| 0 | ||||||
| ● | ● | |||||
| ● | ● |
The table above is a grid of 7 rows and 7 columns with the knight (0) at (3, 3). In the original, the 8 reachable positions were marked only by shading, so no cell values survived the text extraction. The list of positions written in the body has been copied over unchanged and marked with ●.
Next, assume a situation with N=7 and K=3. In the grid below, the positions holding knights are shaded.
| 2 | 0 | 6 | 5 | 7 | 8 | 4 |
|---|---|---|---|---|---|---|
| 5 | 7 | 7 | 8 | 7 | 4 | 5 |
| 8 | 5 | 9 | 6 | 5 | 9 | 6 |
| 7 | 9 | 4 | 5 | 0 | 8 | 7 |
| 9 | 8 | 5 | 9 | 7 | 8 | 8 |
| 7 | 0 | 7 | 4 | 3 | 7 | 4 |
| 7 | 9 | 9 | 5 | 8 | 4 | 3 |
As noted above, when a knight moves it gains score equal to the number written on the position it moved to. Our goal is to place the knights well and make the sum of the scores as large as possible. In this example, if the knight at (0, 1) moves to position (1, 3), the knight at (3, 4) moves to position (2, 2) and the knight at (5, 1) moves to position (4, 3), the total comes to 8 + 9 + 9 = 26. Taking every possible case into account, this is the maximum score that can be obtained.
The figure below shades in red the positions the knights reach to get that maximum possible score.
| 2 | 0 | 6 | 5 | 7 | 8 | 4 |
|---|---|---|---|---|---|---|
| 5 | 7 | 7 | 8 | 7 | 4 | 5 |
| 8 | 5 | 9 | 6 | 5 | 9 | 6 |
| 7 | 9 | 4 | 5 | 0 | 8 | 7 |
| 9 | 8 | 5 | 9 | 7 | 8 | 8 |
| 7 | 0 | 7 | 4 | 3 | 7 | 4 |
| 7 | 9 | 9 | 5 | 8 | 4 | 3 |
Again, with 3 knights at positions (0, 1), (3, 4) and (5, 1), suppose this time they move to positions (0, 1), (1, 5) and (6, 3). The knight at position (0, 1) did not move and chose to stay where it was. In this case the total score is 0 + 4 + 5 = 9, so only 9 points can be obtained. As this shows, the score you can obtain changes greatly depending on how each knight's position is chosen.
| 2 | 0 | 6 | 5 | 7 | 8 | 4 |
|---|---|---|---|---|---|---|
| 5 | 7 | 7 | 8 | 7 | 4 | 5 |
| 8 | 5 | 9 | 6 | 5 | 9 | 6 |
| 7 | 9 | 4 | 5 | 0 | 8 | 7 |
| 9 | 8 | 5 | 9 | 7 | 8 | 8 |
| 7 | 0 | 7 | 4 | 3 | 7 | 4 |
| 7 | 9 | 9 | 5 | 8 | 4 | 3 |
So, given the board, write a program that returns the maximum sum of scores that can be obtained by placing the knights well.
Input and Output Examples
Example 1
Input
7, 3, [[2, 0, 6, 5, 7, 8, 4], [5, 7, 7, 8, 7, 4, 5], [8, 5, 9, 6, 5, 9, 6], [7, 9, 4, 5, 0, 8, 7], [9, 8, 5, 9, 7, 8, 8], [7, 0, 7, 4, 3, 7, 4], [7, 9, 9, 5, 8, 4, 3]]
Output
26
Input
First the board size N is given as a natural number. N is a natural number from 5 to 30.
Next, the number of knights K is given as a natural number. K is a natural number from 3 to 7.
After that, an array board holding the N×N board information is given. On the starting board every position holding a knight is marked 0, and a score is always a natural number from 1 to 100.
Output
Place the K knights well and return the maximum sum of scores that can be obtained, as a natural number.
Requirements
- You must write a solution(N, K, board) function and return the answer
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
- There are 14 cases, and 4 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 14 cases to solve this.
Examples
4 public cases. Judging also uses hidden cases. You have to pass all 14 cases to solve this.
7, 3, [[2, 0, 6, 5, 7, 8, 4], [5, 7, 7, 8, 7, 4, 5], [8, 5, 9, 6, 5, 9, 6], [7, 9, 4, 5, 0, 8, 7], [9, 8, 5, 9, 7, 8, 8], [7, 0, 7, 4, 3, 7, 4], [7, 9, 9, 5, 8, 4, 3]]
26
18, 3, [[35, 39, 93, 56, 5, 42, 68, 55, 56, 6, 73, 4, 71, 2, 51, 21, 37, 86], [40, 58, 20, 16, 52, 62, 0, 86, 23, 80, 5, 93, 70, 68, 12, 65, 95, 87], [38, 77, 11, 56, 5, 11, 85, 18, 78, 86, 2, 47, 95, 93, 77, 56, 83, 88], [11, 64, 88, 71, 93, 64, 50, 25, 9, 46, 61, 50, 10, 89, 38, 8, 79, 58], [94, 2, 6, 18, 40, 60, 13, 82, 3, 37, 88, 15, 79, 92, 22, 30, 45, 58], [10, 75, 59, 41, 36, 92, 56, 77, 12, 91, 69, 5, 38, 11, 58, 95, 0, 43], [76, 20, 27, 3, 59, 24, 76, 18, 30, 17, 53, 95, 96, 12, 26, 88, 15, 21], [39, 84, 12, 65, 27, 61, 83, 8, 75, 64, 83, 80, 23, 31, 60, 21, 45, 93], [60, 10, 29, 32, 68, 99, 1, 100, 1, 14, 85, 45, 98, 48, 43, 92, 81, 51], [20, 89, 90, 47, 42, 0, 37, 5, 11, 54, 40, 4, 12, 69, 96, 77, 49, 14], [54, 85, 39, 43, 38, 26, 7, 86, 57, 33, 4, 50, 2, 46, 11, 79, 22, 76], [50, 33, 58, 41, 19, 23, 52, 45, 22, 37, 70, 93, 84, 97, 74, 86, 99, 24], [44, 83, 76, 33, 29, 35, 84, 98, 96, 70, 31, 40, 60, 3, 59, 100, 85, 74], [29, 26, 81, 69, 15, 34, 40, 7, 51, 50, 80, 13, 4, 69, 18, 64, 99, 97], [39, 100, 2, 19, 72, 4, 8, 11, 70, 29, 33, 91, 36, 89, 88, 23, 94, 30], [37, 16, 73, 9, 72, 43, 74, 21, 59, 60, 2, 72, 99, 96, 47, 2, 91, 68], [9, 35, 82, 26, 41, 56, 74, 94, 65, 73, ... cut off here (1,305 chars in total)
271
25, 7, [[52, 57, 36, 63, 3, 34, 44, 62, 2, 22, 50, 51, 13, 53, 93, 90, 22, 36, 33, 68, 40, 97, 72, 36, 28], [44, 13, 26, 79, 13, 34, 25, 6, 64, 65, 10, 56, 41, 87, 65, 95, 64, 70, 58, 83, 22, 67, 68, 88, 64], [74, 23, 29, 12, 47, 16, 47, 43, 91, 53, 20, 7, 15, 82, 58, 40, 35, 19, 90, 75, 42, 47, 39, 22, 19], [26, 18, 67, 64, 96, 15, 93, 38, 70, 5, 68, 74, 81, 92, 97, 27, 46, 31, 1, 86, 7, 0, 56, 44, 54], [66, 50, 8, 78, 61, 31, 50, 21, 27, 46, 89, 13, 20, 75, 65, 13, 76, 39, 60, 26, 90, 35, 73, 93, 16], [35, 66, 50, 58, 32, 96, 41, 81, 88, 100, 15, 2, 71, 23, 72, 1, 98, 92, 72, 45, 27, 82, 27, 63, 19], [17, 10, 61, 38, 34, 13, 82, 33, 62, 36, 57, 96, 21, 87, 51, 73, 37, 65, 58, 99, 51, 39, 87, 91, 51], [41, 23, 63, 81, 4, 78, 1, 74, 69, 89, 90, 82, 72, 97, 91, 6, 41, 8, 88, 11, 0, 38, 85, 97, 0], [99, 56, 15, 60, 35, 91, 89, 3, 56, 78, 85, 67, 20, 52, 7, 61, 42, 63, 74, 60, 82, 11, 80, 31, 21], [80, 87, 65, 16, 98, 84, 32, 32, 19, 45, 35, 4, 64, 26, 67, 71, 30, 3, 55, 81, 53, 97, 62, 78, 42], [59, 48, 86, 44, 84, 26, 6, 10, 62, 24, 84, 46, 80, 9, 11, 78, 65, 83, 58, 52, 30, 60, 68, 73, 36], [6, 71, 25, 52, 37, 40, 95, 24, 7, 79, 96, 93, 16, 13, 39, 92, 58, 98, 79, 17, 82, 84, 84, 6 ... cut off here (2,511 chars in total)
613
26, 4, [[75, 87, 64, 64, 75, 64, 96, 17, 11, 27, 38, 19, 46, 88, 64, 72, 11, 66, 93, 89, 52, 60, 18, 98, 6, 31], [47, 17, 4, 39, 21, 72, 88, 79, 53, 20, 36, 30, 88, 46, 64, 98, 27, 53, 39, 31, 36, 84, 70, 50, 56, 96], [15, 27, 14, 81, 19, 66, 63, 70, 78, 80, 92, 61, 36, 82, 97, 83, 50, 38, 94, 64, 89, 78, 72, 79, 61, 65], [79, 95, 59, 52, 97, 7, 64, 26, 28, 21, 48, 76, 36, 48, 89, 48, 86, 86, 69, 55, 29, 4, 100, 31, 66, 22], [42, 67, 23, 80, 56, 90, 54, 76, 64, 3, 44, 61, 16, 82, 88, 84, 81, 20, 49, 32, 20, 44, 83, 40, 48, 33], [79, 93, 1, 12, 52, 50, 9, 25, 78, 69, 40, 16, 79, 15, 96, 11, 58, 90, 99, 81, 2, 22, 16, 65, 8, 80], [0, 32, 51, 9, 81, 2, 18, 37, 31, 75, 68, 94, 68, 63, 68, 48, 99, 28, 94, 52, 85, 41, 67, 33, 5, 6], [24, 35, 79, 36, 53, 83, 99, 59, 95, 77, 63, 31, 23, 82, 53, 65, 51, 79, 89, 21, 50, 44, 49, 97, 25, 78], [87, 3, 66, 57, 96, 3, 71, 9, 85, 96, 34, 43, 47, 80, 7, 31, 58, 13, 21, 76, 40, 34, 6, 47, 69, 20], [56, 26, 55, 46, 19, 27, 70, 47, 80, 85, 66, 97, 42, 62, 84, 73, 13, 76, 50, 76, 72, 15, 56, 12, 32, 59], [37, 32, 21, 72, 100, 92, 92, 9, 51, 83, 83, 22, 33, 23, 58, 0, 64, 30, 89, 94, 47, 33, 87, 97, 91, 68], [49, 85, 39, 25, 79, 41, 12, 43, 31, 78, 62, ... cut off here (2,708 chars in total)
340
Notes
Background that helps with solving. The rules you have to follow are in the input and output specs and the requirements above.
This is problem 3 of practice test 7 in the original.
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 4 public cases. Submitting runs the hidden cases too.
People who solved this problem
The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.
Input read time 7ms (excluded from the ranking)
Log in and you can see the code once you solve this problem.