En la seguidilla de las ideas que estoy dando a conocer, esta es otra de ellas. En los siguientes párrafos, les dejo a continuación la idea.
El objetivo de esta idea es conseguir un algoritmo que dado un conjunto de bytes de entrada, genere otro flujo de salida con ciertas propiedades que explico a continuación.
El algoritmo, en una primera versión, internamente va tomando subconjuntos de 81 bytes, conformando matrices de 9x9 que llamaremos matriz T (el tamaño del tablero de Sudoku tradicional; otra versión podría extenderse a otros tamaños). Posteriormente, a partir de T se busca un conjunto de matrices Sudoku S tal que aplicada alguna función, como sumas y multiplicaciones (u otro operador), se pueda reconstruir T.
Dada la naturaleza del Sudoku, es posible dejar sólo algunos datos en las matrices s en S. De esta forma, la representación binaria de s pudiera reducirse considerablemente, y no tan sólo porque, eventualmente, serían menos números, sino porque los números van de 1 a 9, representables con 4 bits.
Algunos pequeños gigantes problemas son los siguientes:
- La búsqueda del conjunto S óptimo es un problema de combinación, resultando en un algoritmo exponencial. Se podría tratar con metaheurísticas, pero no garantizaría completitud.
- Suponiendo que se ha encontrado un S óptimo, al momento de descomprimir, cada s debe ser reconstruido. Los mejores algoritmos para resolver Sudokus aún son exponenciales.
¿Alguna idea?
1 comentario:
Amigo,
No soy experto en Sudoku, pero programé en Excel un método matricial, etc que resuelve la mayoría de los casos a excepción de aquellos que requieren backtracking.
Sin duda que la matris Sudoku se puede llevar a stream de datos, bla, bla.
Pero no veo la real ventaja de este método frente a los otros, tienes un ejemplo?
Publicar un comentario