全ての経路のスコアが等しい ⇔ 各反対角線 (\(i+j\) が同じマス) の値が全て等しい、が成り立ちます。

証明

必要性：反対角線ごとに一定

任意の \(2\times2\) の部分正方形 \((i,j),(i,j+1),(i+1,j),(i+1,j+1)\) を考えます。

この部分を通る経路で、

• （右→下）で進む経路：\((i,j)\to(i,j+1)\to(i+1,j+1)\)
• （下→右）で進む経路：\((i,j)\to(i+1,j)\to(i+1,j+1)\)

の \(2\) つは、訪れるマスの集合の差が \((i,j+1)\) と \((i+1,j)\) だけであり、\((i,j+1)\) と \((i+1,j)\) に書かれた数が等しい必要があります。

つまり \(A_{i,j+1}=A_{i+1,j}\) が任意の \(i,j\) で成り立ちます。このことから、反対角線上のマスの数字は全て等しい必要があります。

十分性：反対角線ごとに一定なら経路によらない

反対角線 \(d=i+j\)（\(2\le d\le 2N\)）ごとに値が一定だとします。

右・下移動では \(i+j\) が \(1\) ずつ増えるため、任意の経路は各 \(d\) についてちょうど \(1\) マスずつ通ります。 よって経路のスコアは「各反対角線の値の総和」に等しく、経路によらず一定です。

アルゴリズム

反対角線 \(k=i+j\) ごとに、? 以外の文字を集めます。

• \(1\) つの反対角線に異なる数字が \(2\) 種類以上あれば不可能 → -1
• それ以外は、その反対角線の数字を、既に決まっているならその数字、全て ? なら 0 等として決め、同じ反対角線上の ? を全てそれで埋める