Solution

Answer: 13938

This is a classic assignment problem:

We must choose exactly one number from each row.
No two chosen numbers may come from the same column.
We want the maximum possible sum.

Mathematically, if the matrix is $A=(a_{ij})$, we seek

$$\max_{\sigma \in S_n} \sum_{i=1}^{n} a_{i,\sigma(i)}$$

where $S_n$ is the set of permutations of ${0,1,\dots,n-1}$.

For a $15\times 15$ matrix, brute force over all $15!$ permutations is impossible:

$$15! \approx 1.3\times 10^{12}$$

So we need dynamic programming.

Mathematical Analysis

Let:

$n = 15$
$dp(mask)$ = maximum sum achievable after assigning some rows to the set of columns represented by mask.

A bitmask of length 15 represents which columns are already used.

If mask has $k$ bits set, then we have already assigned rows $0,1,\dots,k-1$.

Transition:

For every unused column $j$,

$$dp(mask \cup {j}) = \max\left( dp(mask \cup {j}), ; dp(mask)+a_{k,j} \right)$$

where

$$k = \text{number of set bits in } mask$$

The total number of states is:

$$2^{15} = 32768$$

and each state tries at most 15 transitions, so complexity is roughly

$$15 \cdot 2^{15} \approx 5\times 10^5$$

which is tiny.

Python Implementation

# Project Euler 345
# Maximum matrix sum with no shared row/column

matrix = [
    [7,53,183,439,863,497,383,563,79,973,287,63,343,169,583],
    [627,343,773,959,943,767,473,103,699,303,957,703,583,639,913],
    [447,283,463,29,23,487,463,993,119,883,327,493,423,159,743],
    [217,623,3,399,853,407,103,983,89,463,290,516,212,462,350],
    [960,376,682,962,300,780,486,502,912,800,250,346,172,812,350],
    [870,456,192,162,593,473,915,45,989,873,823,965,425,329,803],
    [973,965,905,919,133,673,665,235,509,613,673,815,165,992,326],
    [322,148,972,962,286,255,941,541,265,323,925,281,601,95,973],
    [445,721,11,525,473,65,511,164,138,672,18,428,154,448,848],
    [414,456,310,312,798,104,566,520,302,248,694,976,430,392,198],
    [184,829,373,181,631,101,969,613,840,740,778,458,284,760,390],
    [821,461,843,513,17,901,711,993,293,157,274,94,192,156,574],
    [34,124,4,878,450,476,712,914,838,669,875,299,823,329,699],
    [815,559,813,459,522,788,168,586,966,232,308,833,251,631,107],
    [813,883,451,509,615,77,281,613,459,205,380,274,302,35,805]
]

n = len(matrix)

# dp[mask] = best sum achievable using columns in mask
dp = [-1] * (1 << n)
dp[0] = 0

for mask in range(1 << n):

    # Number of rows already assigned
    row = bin(mask).count("1")

    # If all rows assigned, skip transitions
    if row == n:
        continue

    # Try assigning current row to any unused column
    for col in range(n):

        # If column not used yet
        if not (mask & (1 << col)):

            new_mask = mask | (1 << col)

            dp[new_mask] = max(
                dp[new_mask],
                dp[mask] + matrix[row][col]
            )

answer = dp[(1 << n) - 1]

print(answer)

Code Walkthrough

1. Store the matrix

matrix = [...]

This is the given $15\times15$ matrix.

2. Create the DP table

dp = [-1] * (1 << n)
dp[0] = 0

There are $2^{15}$ masks.

dp[mask] stores the best achievable sum.
mask = 0 means no columns used yet, so value is 0.

3. Iterate over all masks

for mask in range(1 << n):

We process every subset of columns.

4. Determine which row we are assigning

row = bin(mask).count("1")

If 5 columns are already used, then we must now assign row 5.

5. Try every unused column

if not (mask & (1 << col)):

This checks whether column col is free.

6. Transition

dp[new_mask] = max(
    dp[new_mask],
    dp[mask] + matrix[row][col]
)

We update the best possible sum after assigning the current row to that column.

7. Final answer

answer = dp[(1 << n) - 1]

The mask with all 15 bits set means every column has been used exactly once.

Verification on the Small Example

For the $5\times5$ matrix in the statement, the algorithm finds:

$$863 + 383 + 343 + 959 + 767 = 3315$$

which matches the problem statement exactly.

Final Verification

The result should:

be larger than $15 \times 900 \approx 13500$, since many entries are near 1000,
but less than $15 \times 1000 = 15000$.

The computed value:

$$13938$$

fits perfectly in this range and is the known optimal assignment value.

Answer: 13938

Project Euler Problem 345