On completing latin squares Original Research Article

In 1984, Colbourn proved that completing a partially filled latin square is NP-complete. In this paper, we tighten the Colbourn result by showing that completing a partially filled square remains hard even if no more than three unfilled cells exist in any row or column of the square and where only three integers are available.