I am afraid that the answer to your question will be difficult -or impossible- to get, excluding of course one value: With N=1, the answer will be always "yes" ;-) With N=2, the answer can already be "no" even with your prerequisite, with such a matrix: 1 ? ? 2 With small N (say N < 8 or 9), we can have fast algorithms, because the Latin squares are not too numerous, but looks more difficult for bigger N. Christian. -----Message d'origine----- De : math-fun-bounces+cboyer=club-internet.fr@mailman.xmission.com [mailto:math-fun-bounces+cboyer=club-internet.fr@mailman.xmission.com] De la part de dasimov@earthlink.net Envoyé : mercredi 7 juin 2006 02:10 À : math-fun Objet : [math-fun] Latin square question Suppose an NxN matrix is partially filled with the numbers S_N = {1,2,...,N}. When can the blank squares be filled with elements of S_N so the result is a Latin square (each row and column contains each members of S_N) ??? An obvious prerequisite is that each nonempty row or column can *by itself* be filled with its missing numbers (even if there are none) in a way that leaves each number occurring at most once in any column or row, resp. Assuming this property, is there an algorithm to determine whether the original partial square can be completed to a Latin squre? (It's apparently a hard theorem just to prove that if the NxN matrix contains just N-1 entries so that no row or column has a repetition, then the fill can always be extended to a Latin square. So this question may be intractable.) --Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun