Verificar si una matriz es Sudoku con un ciclo y con ninguno

Voy a compartir un pequeño divertimento de como verificar si una matriz de 9x9 cumple las condiciones para ser un Sudoku utilizando un ciclo [MATLAB] y ninguno [F#]. El objetivo no es reducir líneas de código sino hacer el código más declarativo (es decir que el código “hable por sí solo” o casi).

Las condiciones que debe cumplir una matriz son que en cada una de sus filas, columnas y celdas de orden 3 deben estar todos los números del 1 al 9, es decir no puede haber repeticiones en cada uno de los 27 conjuntos.

Para verificar estos conjuntos debe observarse que la suma de las potencias de 2 cuyos exponentes son sus elementos es igual 1022:

2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + 2^9 = 1022

O bien que dicha sumatoria dividida por 1022 es igual a 1

Por otra parte si agrupamos cada uno de los 27 conjuntos en tres grupos (filas, columnas, celdas) resulta que cada uno contiene 9 elementos. Esta enumeración nos lleva a utilizar un solo ciclo para analizar la terna de la fila, columna y celda n. Donde si aplicamos el criterio de verificación anterior como una función, a cada uno de los conjuntos de la terna su suma debe ser igual a 3:

C(Fila[n]) + C(Columna[n]) + C(Celda[n]) = 3 

Cualquier otro valor indicaría que el conjunto no tiene todos los números naturales menores que 10 y por tanto que la matriz no es un Sudoku.

Llevando lo anterior a código de MATLAB quedaría como sigue:

function R = IsSudoku(SU)
f = @(x) sum(sum(power(2,min(10,max(0,x))))) / 1022;
R = 1;
for n = 1:9
    r = sum([1 2 3 4 4 5 5 6 6 7 7 7 8 8 8 9 9 9] == n);
    c = sum([1 2 2 3 3 3 4 5 5 6 6 6 7 8 8 9 9 9] == n);
    if sum([f(SU(n,:)) f(SU(:,n)) f(SU(3*r-2:3*r,3*c-2:3*c))]) ~= 3
        R = 0; return;
    end
end

Lo más destacable es la obtención de cada uno de los conjuntos a partir de la sintaxis que soporta MATLAB para extraer submatrices, en especial la submatriz correspondiente a la celda. Una manera de sacar la formula puede verse en la siguiente imagen:

Nótese que aunque podria haberse creado una función con condicionales, al obtener los resultados mediante 3k-2 es más sencillo plantear una función en forma de vector que tome el indice de la celda y obtenga el k para calcular el valor deseado. 

Una implementación enteramente funcional (sin ciclos) con el lenguaje F# quedaría así:

let isSudoku (m : FMatrix) =
    requires (m.Dimension = (9,9)) "Not a Sudoku Matrix"
    let f (a : FMatrix) = (a.Items |> Seq.map (fun x -> Math.Pow(2.0,Math.Min(10,Math.Max(0,x)))) |> Seq.sum) / 1022.0
    let pos arr n = arr |> Array.filter ((=) n) |> Array.length
    let h n = 
        let r,c = pos [|1;2;3;4;4;5;5;6;6;7;7;7;8;8;8;9;9;9|] n, 
                  pos [|1;2;2;3;3;3;4;5;5;6;6;6;7;8;8;9;9;9|] n
        f(m.[n .. n, *]) + f(m.[*, n .. n]) + f(m.[3 * r - 2 .. 3 * r, 3 * c - 2 .. 3 * c])
    seq {1..9} |> Seq.map h |> Seq.forall ((=) 3.0)

La clase FMatrix se encuentra en un proyecto de CodePlex, dicha clase  implementa una convención de F# para permitir una sintaxis de extración de submatrices equivalente a la de  MATLAB. En esta versión para no utilizar ciclos se utiliza una secuencia (seq {1..9}) como secuencia de entrada, un mapping (Seq.map) para aplicar el criterio y el operador forall que consolida  la secuencia final en un valor booleano obtenido de comprobar que todos los elementos sean iguales a 3.

El performance de los dos códigos es bueno, en parte gracias a la instrucción: min(10,max(0,x)) que previene de evaluar una potencia de 2 costosa al tiempo que mantiene el resultado final. En el caso de MATLAB no estoy 100% seguro que no se utilicen otros ciclos en el proceso de hallar la submatriz, para el código en F# puede comprobarse que los iteradores involucrados (incluso los definidos en la biblioteca de F#) no utilizan variables de estado para soportar contadores.

Espero que les haya resultado interesante.

-hnh

__

Currently Reading: Frank Herbert – Children of Dune; Aldous Huxley – Brave New World.