Hall's Condition for Partial Latin Squares
  Hall's Condition is a necessary condition for a partial latin square to be completable. Hilton and Johnson showed that for a partial latin square whose filled cells form a rectangle, Hall's Condition is equivalent to Ryser's Condition, which is a necessary and sufficient condition for completability.   We give what could be regarded as an extension of Ryser's Theorem, by showing that for a partial latin square whose filled cells form a rectangle, where there is at most one empty cell in each column of the rectangle, Hall's Condition is a necessary and sufficient condition for completability.   It is well-known that the problem of deciding whether a partial latin square is completable is NP-complete. We show that the problem of deciding whether a partial latin square that is promised to satisfy Hall's Condition is completable is NP-hard. 
A. J. W. Hilton and E. R. Vaughan
math.CO