All paths having equal scores ⇔ All values on each anti-diagonal (cells with the same \(i+j\)) are equal.

Proof

Necessity: Constant on each anti-diagonal

Consider an arbitrary \(2\times2\) subsquare \((i,j),(i,j+1),(i+1,j),(i+1,j+1)\).

For paths passing through this subsquare:

• Path going (right→down): \((i,j)\to(i,j+1)\to(i+1,j+1)\)
• Path going (down→right): \((i,j)\to(i+1,j)\to(i+1,j+1)\)

These two paths differ in the set of visited cells by only \((i,j+1)\) and \((i+1,j)\), so the numbers written at \((i,j+1)\) and \((i+1,j)\) must be equal.

In other words, \(A_{i,j+1}=A_{i+1,j}\) holds for all \(i,j\). From this, all numbers on cells on the same anti-diagonal must be equal.

Sufficiency: If constant on each anti-diagonal, then independent of path

Assume the value is constant for each anti-diagonal \(d=i+j\) (\(2\le d\le 2N\)).

Moving right or down increases \(i+j\) by \(1\), so any path passes through exactly one cell for each \(d\). Therefore, the path score equals the sum of the anti-diagonal values and is constant regardless of the path.

Algorithm

For each anti-diagonal \(k=i+j\), collect all characters other than ?.

• If there are two or more different digits on one anti-diagonal, it is impossible → -1
• Otherwise, determine the digit for that anti-diagonal: if already determined, use that digit; if all are ?, use 0 or something, and fill all ? on the same anti-diagonal with it.