Sudoku kata

Introducción

Sudoku es un rompecabezas de números muy popular. 

El objetivo es rellenar una cuadrícula de 9 × 9 con números de modo que cada columna, cada fila y cada una de las nueve regiones de 3 × 3 que componen la cuadrícula contengan todos los dígitos del 1 al 9.

El punto de partida es una cuadrícula parcialmente completada:

La cuadrícula terminada se vería así:

Reglas

• Todos los números del rango deben estar presentes en todas las filas, columnas y regiones.
• Dentro de una fila, columna y región no puede haber ningún número repetido.

Los siguientes son ejemplos de infracciones:

Ninguna de esta opciones puede estar presente en una solución válida.

Instrucciones

Esta kata se divide en 4 niveles de dificultad creciente. Empieza por el primero y luego avanza al siguiente. 

Nivel 0 (Calentamiento)

Nota: Este nivel está pensado para que te familiarices con las reglas del juego. Si ya las conoces bien (por ejemplo, si practicas Sudoku en la vida real), puedes saltártelo y pasar directamente al Nivel 1.

Crear una aplicación capaz de determinar si una matriz es una solución potencial para un Sudoku.

El input es la ruta, un archivo CSV que contiene N filas y N números por fila, donde N es el cuadrado de un número entero mayor que 1:

Ejemplo:

1,2,3,4,

2,1,4,3,

3,4,1,2,

4,3,2,1,

N = 4

1,2,3,4,5,6,7,8,9

1,2,3,4,5,6,7,8,9

1,2,3,4,5,6,7,8,9

1,2,3,4,5,6,7,8,9

1,2,3,4,5,6,7,8,9

1,2,3,4,5,6,7,8,9

1,2,3,4,5,6,7,8,9

1,2,3,4,5,6,7,8,9

N = 9

El contenido del archivo forma una matriz que debes comprobar para detectar si hay infracciones de las normas.

Ejemplo:

Un archivo que contiene:

1,2,3,4,

2,1,4,3,

3,4,1,2,

4,3,2,1,

El output debería ser:

El input no cumple las reglas de Sudoku.

Un archivo que contiene

1,2,3,4,

3,4,1,2,

2,3,4,1,

4,1,2,3,

El output debería ser:

El input cumple con las reglas de Sudoku.

Sugerencias:

• Empieza a codificar asumiendo que el input es un cadena larga que contiene \n (Como si la lectura del archivo CSV ya hubiera sido abordada)
• Evita depender demasiado de los tipos primitivos,

Nivel 1

Crea una aplicación capaz de determinar si una solución planteada es válida para una determinada cuadrícula inicial.

El input es la ruta a dos archivos CSV que contienen N filas y N números por fila, donde N es el cuadrado de un número entero mayor que 3 (4, 9, 16, 25,...).

Ejemplo:

5,3, , ,7, , , , ,
6, , ,1,9,5, , , ,
 ,9,8, , , , ,6, ,
8, , , ,6, , , ,3,
4, , ,8,7,3, , ,1,
7, , , ,2, , , ,6,
 ,6, , , , ,2,8, ,
 , , ,4,1,9, , ,5,
 ,1, , ,8, , ,7,9, 

• El primer archivo define la cuadrícula inicial.
• El segundo archivo define la solución planteada.

A continuación se presentan algunos ejemplos de soluciones incorrectas (contenido del segundo archivo de entrada):

En cualquiera de estos casos el output debería ser:

La solución planteada es incorrecta.

Este es un ejemplo de una solución correcta:

5,3,4,6,7,8,9,1,2,
6,7,2,1,9,5,3,4,8,
1,9,8,3,4,2,5,6,7,
8,5,9,7,6,1,4,2,3,
4,2,6,8,5,3,7,9,1,
7,1,3,9,2,4,8,5,6,
9,6,1,5,3,7,2,8,4,
2,8,7,4,1,9,6,3,5,
3,4,5,2,8,6,1,7,9,

En este caso, el output debería ser:

La solución planteada es correcta

Sugerencias:

• Piensa en todas las razones por las que una solución podría ser errónea. Si ninguna de ellas es cierta para el caso concreto que estás comprobando, entonces hay que aceptarla.

Nivel 2

Crea una aplicación que proporcione una solución válida dada la cuadrícula inicial o un mensaje en caso de que el Sudoku no tenga solución.

El input es un fichero CSV con el mismo formato que en el primer nivel y el output es una cadena CSV que contiene la solución en caso de que exista.

Ejemplo: 

Para un input como el siguiente:

5,3, , ,7, , , , ,
6, , ,1,9,5, , , ,
 ,9,8, , , , ,6, ,
8, , , ,6, , , ,3,
4, , ,8, ,3, , ,1,
7, , , ,2, , , ,6,
 ,6, , , , ,2,8, ,
 , , ,4,1,9, , ,5,
 , , , ,8, , ,7,9,

El output debería ser:

5,3,4,6,7,8,9,1,2,
6,7,2,1,9,5,3,4,8,
1,9,8,3,4,2,5,6,7,
8,5,9,7,6,1,4,2,3,
4,2,6,8,5,3,7,9,1,
7,1,3,9,2,4,8,5,6,
9,6,1,5,3,7,2,8,4,
2,8,7,4,1,9,6,3,5,
3,4,5,2,8,6,1,7,9,

Para un input como el siguiente:

5,3, , ,7, , , , ,
6, , ,1,9,5, , , ,
 ,9,8, , , , ,6, ,
8, , , ,6, , , ,3,
4, , ,8, ,3, , ,1,
7, , , ,2, , , ,6,
6, , , , , ,2,8, ,
 , , ,4,1,9, , ,5,
 , , , ,8, , ,7,9,

El output debería ser:

El Sudoku no tiene solución

Sugerencias:

• Empieza suponiendo que la cuadrícula es 4x4 y luego generaliza la solución.
• No intentes dar con el algoritmo más eficiente al principio. Construye un conjunto de pruebas sólido y luego refactoriza el algoritmo.
• Utiliza la solución del nivel uno si te sirve de ayuda
• Puede haber situaciones en las que la insolubilidad del Sudoku no sea obvia a primera vista, por ejemplo:

1, ,3,4,
3,4,1,2,
 ,3,2,1,
4,1, ,3,

Nivel 3

Crea una aplicación que pueda producir una cuadrícula inicial NxN que se pueda resolver.

En este caso, el input es la dimensión de la cuadrícula y el número inicial de espacios en blanco.

El output es una cadena CSV con el formato comentado en los casos anteriores o un mensaje indicando que los requisitos no se pueden satisfacer.

Ejemplo:

Para un input como el siguiente:

3 51

El output debería ser algo similar a: 

5,3, , ,7, , , , ,
6, , ,1,9,5, , , ,
 ,9,8, , , , ,6, ,
8, , , ,6, , , ,3,
4, , ,8, ,3, , ,1,
7, , , ,2, , , ,6,
 ,6, , , , ,2,8, ,
 , , ,4,1,9, , ,5,
 , , , ,8, , ,7,9,

Sugerencias:

• Intenta reutilizar las soluciones de los niveles 1 y 2