  Let $H$ be a $k$-graph on $n$ vertices, with minimum codegree at least $n/k +
cn$ for some fixed $c > 0$. In this paper we construct a polynomial-time
algorithm which finds either a perfect matching in $H$ or a certificate that
none exists. This essentially solves a problem of Karpi\'nski, Ruci\'nski and
Szyma\'nska; Szyma\'nska previously showed that this problem is NP-hard for a
minimum codegree of $n/k - cn$. Our algorithm relies on a theoretical result of
independent interest, in which we characterise any such hypergraph with no
perfect matching using a family of lattice-based constructions.
