RE: [math-fun] Latin square question
I'm afraid I may not have expressed myself clearly. What I meant was, suppose a matrix is partially filled. These entries will never change in this question. CONDITION (*): Suppose that any *individual* row that already contains at least one filled square satisfies the condition that its unfilled squares can be filled without repetition so that there is also no repetition in any column. *And* the same thing after switching the roles of rows & columns. This is clearly a prerequisite to extending the originally partially-filled matrix to a Latin square. Question: Is this sufficient to know the original partially-filled matrix can be extended to a Latin square? (Of course the 2x2 matrix given below fails to satisfy the condition (*).) (I very doubt the answer to my question is Yes, but it would require a trickier counterexample.) --Dan --------------------------------------------------------------------------------------------- Christian wrote: << I am afraid that the answer to your question will be difficult -or impossible- to get, excluding of course one value: e 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.)
I better understand your question. Here is a 4x4 counterexample: 1 3 ? ? ? ? ? 1 3 4 ? ? ? ? 2 3 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é : vendredi 9 juin 2006 08:36 À : math-fun Objet : RE: [math-fun] Latin square question I'm afraid I may not have expressed myself clearly. What I meant was, suppose a matrix is partially filled. These entries will never change in this question. CONDITION (*): Suppose that any *individual* row that already contains at least one filled square satisfies the condition that its unfilled squares can be filled without repetition so that there is also no repetition in any column. *And* the same thing after switching the roles of rows & columns. This is clearly a prerequisite to extending the originally partially-filled matrix to a Latin square. Question: Is this sufficient to know the original partially-filled matrix can be extended to a Latin square? (Of course the 2x2 matrix given below fails to satisfy the condition (*).) (I very doubt the answer to my question is Yes, but it would require a trickier counterexample.) --Dan ---------------------------------------------------------------------------- ----------------- Christian wrote: << I am afraid that the answer to your question will be difficult -or impossible- to get, excluding of course one value: e 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.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Christian Boyer -
dasimov＠earthlink.net