Polynomial-Time Solution of Unique Latin Square Completion via Prime Debt Graphs and Exhaustive Cascade

We prove that any N ×N Latin square completion in-stance with a unique solution (M =1) can be solved in O(N 11) timewithout backtracking. The proof combines three tools. House poly-nomials encode row and column constraints so that candidate setsat each cell are the common roots of two polynomials; a parallelprime encoding gives the same sets via divisibility. The surplus ofcandidates beyond the correct value creates alternating cycles ineach house’s bipartite matching graph—locally feasible reassign-ments. Under M =1, the Cavenagh–Wanless trade impossibilitytheorem prevents these local alternatives from forming a globalLatin trade. This tension is captured by the prime debt graph,a DAG that traces the displacement from any wrong candidateto a terminal house violation. A three-layer composed operator(house-consistency closure, rectangle enumeration, single-variableconditioning) detects every such violation, guaranteeing that eachapplication eliminates wrong candidates.