Los cuadrados latinos son una aplicación matemática, utilizando combinatoria, para generar cuadrados con ciertos datos en cada casilla cumpliendo unas restricciones. Podemos encontrar cuadrados latinos por ejemplo en los famosos sudokus. También se puede aplicar a la forma de distribuir cultivos o fertilizantes en cuadrados de terrenos. También se pueden usar para generar puzzles, rompecabezas, o simplemente para practicar algorimos de programación..
Traigo entonces a modo de code-kata otro algoritmo, para resolver cuadrados latinos de tamaño NxN. Estos cuadrados latinos tienen la peculiaridad de que: en cada fila no se puede repetir el mismo dato, y en cada columna tampoco se puede repetir el mismo dato.
En este caso, he usado números para llenar de datos el cuadrado, y estos números del 1 a N significan un color. Un cero significa que está sin llenar, y los números entonces que llenamos van desde 1 hasta N, siendo N el ancho y alto del cuadrado.
La mejor estrategia para este algoritmo es la de vuelta atrás, ya que tenemos que encontrar todas las soluciones posibles de la forma más eficiente posible.
Al grano, generando los datos de inicio
<?php
define('N', 9);
define('WAIT_TIME', 3);
define('TRACE', true);
$GLOBALS['TOTAL_SOLUTIONS'] = 0;
$GLOBALS['SOLUTIONS'] = array();
$square = array();
for ($i = 0; $i < N; ++$i) {
for ($j = 0; $j < N; ++$j) {
$square[$i][$j] = 0;
}
}
echo 'NxN latin square with N='.N.'. Let\'s start filling with colors..'.PHP_EOL;
latinSquare($square, 1);
echo 'Total solutions found: '.$GLOBALS['TOTAL_SOLUTIONS'].PHP_EOL;
Aquí simplemente tenemos la inicialización de variables, y el cuadrado de partida lleno de ceros. De aquí llamamos a la función latinSquare y comenzamos el juego..
La función principal
Aquí ya vemos que tenemos una función recursiva. La estrategia consiste en ir llenando, color a color, el cuadrado, recorriendo todas las posibles combinaciones.
function latinSquare($square, $color)
{
if (TRACE) {
echo '---> latingSquare! Filling square with $color='.$color.PHP_EOL;
}
foreach (completions($square, $color) as $possibleSolution) {
if (possible($possibleSolution)) {
if (isSolution($possibleSolution)) { // Procces solution..
if (TRACE) {
echo '=====>> SOLUTION FOUND!'.PHP_EOL;
writeToScreen($possibleSolution);
sleep(WAIT_TIME);
}
++$GLOBALS['TOTAL_SOLUTIONS'];
$GLOBALS['SOLUTIONS'][] = $possibleSolution;
} else {
if (completable($possibleSolution)) {
if ($color + 1 <= N) {
latinSquare($possibleSolution, $color + 1);
}
}
}
}
}
}
Es decir, se va a ir construyendo un árbol de posibilidades. En el nodo inicial, nivel 0, tenemos el cuadrado vacío, justo antes de hacer la primera llamada a latinSquare(). En el nivel 1 tendremos todos los hijos posibles de llenar el nodo inicial vacio con el color 1. Es decir, en el nivel 1, llamando a la función completions() obtenemos todas las posibles combinaciones para poner el color=1. Así entramos con cada uno de estos hijos de nivel 1 y seguimos completando el árbol en el nivel 2.
Entonces, con cada hijo de nivel 1 se llama a sí mismo para llenar entonces ese hijo de todas las posibles formas con el color 2. Vamos entonces ramificando cada posible combinación de nivel 1 anterior, llenando ahora de todas las formas posibles con el color 2. Así sucesivamente vamos descendiendo de nivel hasta llegar a N. Hasta haber llenado con todos los colores el cuadrado.
Por ejemplo
NxN latin square with N=3. Let's start filling with colors.. ---> latingSquare! Filling square with $color=1 ---> latingSquare! Filling square with $color=2 ---> latingSquare! Filling square with $color=3 =====>> SOLUTION FOUND! 1 2 3 3 1 2 2 3 1 ---> latingSquare! Filling square with $color=3 =====>> SOLUTION FOUND! 1 3 2 2 1 3 3 2 1 ---> latingSquare! Filling square with $color=2 ---> latingSquare! Filling square with $color=3 =====>> SOLUTION FOUND! 1 2 3 2 3 1 3 1 2 ---> latingSquare! Filling square with $color=3 =====>> SOLUTION FOUND! 1 3 2 3 2 1 2 1 3 ---> latingSquare! Filling square with $color=2 ---> latingSquare! Filling square with $color=3 =====>> SOLUTION FOUND! 2 1 3 1 3 2 3 2 1 ---> latingSquare! Filling square with $color=3 =====>> SOLUTION FOUND! 3 1 2 1 2 3 2 3 1
Este es el primer recorrido en profundidad hasta llegar al nivel 3. En llegar aquí hace vuelta atrás, volviendo al nivel 2 para seguir el siguiente recorrido. Es curioso que veas cómo al llenar con el color 3 simplemente encuentra la solución, porque sólo llena con el color 3 las casillas vacias que puede llenar hasta llegar a una solución.
Resto de funciones auxiliares
function writeToScreen($square)
{
for ($i = 0; $i < N; ++$i) {
for ($j = 0; $j < N; ++$j) {
echo str_pad($square[$i][$j], 3, ' ', STR_PAD_BOTH);
}
echo PHP_EOL;
}
}
// Only check if it doesn't have any 0s.
function isSolution($square)
{
return !completable($square);
}
// Check if it has any 0s.
function completable($square)
{
for ($i = 0; $i < N; ++$i) {
for ($j = 0; $j < N; ++$j) {
if ($square[$i][$j] == 0) {
return true;
}
}
}
return false;
}
// Check if it has the same color in any row or col.
function possible($square)
{
for ($i = 0; $i < N; ++$i) {
// cols
$cont = array_fill(1, N, 0);
for ($j = 0; $j < N; ++$j) {
if ($square[$j][$i] != 0) {
++$cont[$square[$j][$i]];
}
}
foreach ($cont as $value) {
if ($value > 1) {
return false;
}
}
// rows
$cont = array_fill(1, N, 0);
for ($j = 0; $j < N; ++$j) {
if ($square[$i][$j] != 0) {
++$cont[$square[$i][$j]];
}
}
foreach ($cont as $value) {
if ($value > 1) {
return false;
}
}
}
return true;
}
// Fill squares with colors and return array with all possible fillings.
function completions($square, $color)
{
$completions = array();
for ($j = 0; $j < N; ++$j) {
if ($square[0][$j] == 0) {
$square[0][$j] = $color;
completionsRecursive($completions, $square, $color, 1);
$square[0][$j] = 0;
}
}
return $completions;
}
function completionsRecursive(&$completions, $square, $color, $row)
{
for ($j = 0; $j < N; ++$j) {
if ($square[$row][$j] == 0) {
$square[$row][$j] = $color;
if (possible($square)) {
if ($row + 1 < N) {
completionsRecursive($completions, $square, $color, $row + 1);
} else {
$completions[] = $square;
}
}
$square[$row][$j] = 0;
}
}
}
Se podría decir que también se aplica la técnica de divide y vencerás. Porque el algoritmo principal, de vuelta atrás, se ha dividido en varios subproblemas más sencillos, que son estas funciones auxiliares.
Terminando
Queda una posible mejora, ya que solution() y completable() se complementan, no hace falta llamar dos veces a estas dos funciones con cada iteración..
De nuevo me remito a la Wikipedia, donde hay más detalles sobre los cuadrados latinos:
https://es.wikipedia.org/wiki/Cuadrado_latino
