Latin négyzet felbontása alnégyzetekre

Abstract

Létezik-e latin négyzet a négyzeten, azaz létezik-e olyan latin négyzet, mely particionálható latin al-négyzetekre, melyek közül mindegyik különböző méretű? A problémát, mely a 22-edik British Combitnatorial Conference konferencián hangzott el, 22.4-es problémaként van feltüntetve: szerzője Graham Farr. A probléma leírása a nem összefüggő alnégyzetek koncepcióját használja, és nem tekintjük megoldásnak, ha az alnégyzetek metszik egymást. A dolgozat célja nem a kérdés közvetlen megválaszolása. A kitűzött cél az, hogy ezen dolgozat végén megállapítok egy méretet amelynél biztosan nincs kisebb, a leírt tulajdonságoknak megfelelő latin négyzet. A kérdés megválaszolásához, hogy létezik-e a leírt tulajdonságoknak megfelelő latin négyzet, azt a módszert választottam, hogy megpróbálok előállítani egyet. A problémát részproblémákra bontottam, ezekkel bizonyítom, hogy ilyen tulajdonságú adott méretű latin négyzet nem állítható elő. A részproblémák megoldására algoritmusokat fogalmaztam meg, és Java-ban implementáltam őket.