Cyclic n×n Latin squares representing solutions of (n, c)-coins problems for 0 ≤ c ≤ n

Abstract

The (n,c)-coins problem on an nxn square, for c <= n, generalizes the n-queens problem by allowing, on any row, column, sum-diagonal or difference-diagonal, no more than c coins (for the n-queens problem c = 1). We proved the following results. 1. For every natural number n with n >= 4, an incremental nxn Latin square represents n + 1 solutions of (n,c)-coins problems for all c with 0 <= c <= n. 2. For every natural number n with n >= 4, not in {4, 6}, there exists an incremental cyclic nxn Latin square. The proofs introduce the injective-majorization principle, avoiding intensive cardinality counting on each diagonal, which would computationally explode for large n.

Keywords