Pregunta Multi-Sudoku AI enfoque


Estoy conceptualizando un solucionador para una variante de sudoku llamado multi-sudoku, donde varias tablas se superponen así:

image of a multi-sudoku

Si entiendo el juego correctamente, debe resolver cada cuadrícula de tal manera que la superposición entre dos o más cuadrículas sea parte de la solución para cada una.

No estoy seguro de cómo debería estar pensando en esto. ¿Alguien tiene pistas / pistas conceptuales? Además, si algún tema relacionado con la inteligencia artificial me viene a la mente, también me gustaría escucharlo.


5
2017-12-13 01:19


origen


Respuestas:


Programación de restricciones (CP)

El sudoku es un típico programación de restricciones problema. Tienes un conjunto de variables (los campos en la cuadrícula) cada uno con una dominio (aquí los dígitos 0 a 9) y un conjunto de restricciones sobre estas variables (el hecho de que un número ocurre solo una vez en una fila, columna, bloque, ...).

Una forma genérica de resolver problemas de programación de restricciones es consistencia del arco (CA): te propagas restricciones. Por variables que están (parcialmente) completadas, puede reducir el dominio de las variables restantes, etc. Finalmente, si la propagación ya no puede hacer que los dominios sean más pequeños, debe hacer una elección.

Con una opción, selecciona un valor para un determinado variable. Una buena estrategia es seleccionar una variable con una pequeña cantidad de valores posibles. A continuación, se propaga nuevamente y posiblemente haga otra elección, y así sucesivamente.

Es posible que su programa descubra que una elección fue incorrecta: hace que el dominio de una o más variables esté vacío. En ese caso, tú volver hacia atrás: deshace una elección que hizo anteriormente (así como la propagación que se hizo después de esa elección) y elige otro valor.

Evidentemente, esta respuesta no apunta a proporcionar una visión general en profundidad del tema, pero Página de Wikipedia Puede dar una mejor visión general y punteros a más información.

Existen programación de restricciones solucionadores como Eclipse (no el IDE), MiniZinc, etc. donde uno simplemente puede definir las variables, dominios y restricciones.

Resolviendo el problema con ECLiPSe

En el sitio web de ECLiPSe, puede encontrar un modelo para sudoku. Dado que leyó algo de documentación sobre ECLiPSe, puede convertir este archivo en un modelo para multi-sudoku. He hecho algunas pequeñas modificaciones resultando en lo siguiente rápido y sucio solución:

% credits to Joachim Schimpf for his model of sudoku
% http://eclipseclp.org/examples/sudoku.ecl.txt
:- lib(ic).
:- import alldifferent/1 from ic_global.

solve(ProblemName) :-
    problem(ProblemName,BA,BB),
    multi_sudoku(3,BA,BB),
    print_board(BA),
    print_board(BB).

multi_sudoku(N,BA,BB) :-
    sudoku(N,BA,VA),
    sudoku(N,BB,VB),
    N2 is N*N,
    Inc is N2-N,
    (multifor([I,J],1,N,1),param(BA,BB,Inc) do
        BA[I+Inc,J+Inc] #= BB[I,J]
    ),
    append(VA,VB,Vars),
    labeling(Vars).

sudoku(N,Board,Vars) :-
    N2 is N*N,
    dim(Board,[N2,N2]),
    Board[1..N2,1..N2] :: 1..N2,
    ( for(I,1,N2), param(Board,N2) do
        Row is Board[I,1..N2],
        alldifferent(Row),
        Col is Board[1..N2,I],
        alldifferent(Col)
    ),
    ( multifor([I,J],1,N2,N), param(Board,N) do
        ( multifor([K,L],0,N-1), param(Board,I,J), foreach(X,SubSquare) do
        X is Board[I+K,J+L]
        ),
        alldifferent(SubSquare)
    ),
    term_variables(Board, Vars).


print_board(Board) :-
    dim(Board, [N,N]),
    ( for(I,1,N), param(Board,N) do
        ( for(J,1,N), param(Board,I) do
            X is Board[I,J],
        ( var(X) -> write("  _") ; printf(" %2d", [X]) )
        ), nl
    ), nl.


%----------------------------------------------------------------------
% Sample data
%----------------------------------------------------------------------

problem(1, [](
    [](_, _, _, _, 6, _, _, _, _),
    [](_, _, _, 4, _, 9, _, _, _),
    [](_, _, 9, 7, _, 5, 1, _, _),
    [](_, 5, 2, _, 7, _, 8, 9, _),
    [](9, _, _, 5, _, 2, _, _, 4),
    [](_, 8, 3, _, 4, _, 7, 2, _),
    [](_, _, _, 2, _, 8, _, _, _),
    [](_, _, _, 6, _, 4, _, _, _),
    [](_, _, _, _, 5, _, _, _, _)
           ),
           [](
    [](_, _, _, _, 3, _, _, _, _),
    [](_, _, _, 8, _, 7, _, _, _),
    [](_, _, _, 1, _, 6, 3, _, _),
    [](_, 9, 8, _, _, _, 1, 2, _),
    [](2, _, _, _, _, _, _, _, 3),
    [](_, 4, 3, _, _, _, 6, 5, _),
    [](_, _, 7, 3, _, 5, 9, _, _),
    [](_, _, _, 4, _, 2, _, _, _),
    [](_, _, _, _, 6, _, _, _, _)
           )
    ).

"Tomé prestado" el modelo del sudoku de Joachim Schimpf, por lo que le doy crédito. Además tenga en cuenta que esta respuesta no aconseja utilizar. Eclipse sobre otra herramienta. Simplemente estoy más familiarizado con la cadena de herramientas Prolog cuando se trata de restringir la programación. Pero si estás más en C ++, Gecode hará el truco con aproximadamente el mismo (o incluso mejor) rendimiento.

que genera la salida:

ECLiPSe Constraint Logic Programming System [kernel]
Kernel and basic libraries copyright Cisco Systems, Inc.
and subject to the Cisco-style Mozilla Public Licence 1.1
(see legal/cmpl.txt or http://eclipseclp.org/licence)
Source available at www.sourceforge.org/projects/eclipse-clp
GMP library copyright Free Software Foundation, see legal/lgpl.txt
For other libraries see their individual copyright notices
Version 6.1 #199 (x86_64_linux), Sun Mar 22 09:34 2015
[eclipse 1]: solve(1).
lists.eco  loaded in 0.00 seconds
WARNING: module 'ic_global' does not exist, loading library...
queues.eco loaded in 0.00 seconds
ordset.eco loaded in 0.01 seconds
heap_array.eco loaded in 0.00 seconds
graph_algorithms.eco loaded in 0.03 seconds
max_flow.eco loaded in 0.00 seconds
flow_constraints_support.eco loaded in 0.00 seconds
ic_sequence.eco loaded in 0.01 seconds
ic_global.eco loaded in 0.07 seconds
  2  1  4  8  6  3  9  5  7
  8  7  5  4  1  9  2  6  3
  6  3  9  7  2  5  1  4  8
  4  5  2  3  7  1  8  9  6
  9  6  7  5  8  2  3  1  4
  1  8  3  9  4  6  7  2  5
  5  4  1  2  3  8  6  7  9
  7  2  8  6  9  4  5  3  1
  3  9  6  1  5  7  4  8  2

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

Tomó mi máquina aproximadamente 0.11 segundos. Además hay 60 soluciones válidas en total.

Las dos últimas "matrices" muestran la solución para los dos Sudoku. Como puede ver (no lo he comprobado completamente), comparten un bloque (el mismo resultado) y todas las restricciones de sudoku son válidas. Una representación más conveniente de la solución se muestra a continuación:

+-----+-----+-----+
|2 1 4|8 6 3|9 5 7|
|8 7 5|4 1 9|2 6 3|
|6 3 9|7 2 5|1 4 8|
+-----+-----+-----+
|4 5 2|3 7 1|8 9 6|
|9 6 7|5 8 2|3 1 4|
|1 8 3|9 4 6|7 2 5|
+-----+-----+-----+-----+-----+
|5 4 1|2 3 8|6 7 9|5 3 4|2 8 1|
|7 2 8|6 9 4|5 3 1|8 2 7|4 6 9|
|3 9 6|1 5 7|4 8 2|1 9 6|3 7 5|
+-----+-----+-----+-----+-----+
            |7 9 8|6 5 3|1 2 4|
            |2 6 5|7 4 1|8 9 3|
            |1 4 3|2 8 9|6 5 7|
            +-----+-----+-----+
            |8 2 7|3 1 5|9 4 6|
            |9 1 6|4 7 2|5 3 8|
            |3 5 4|9 6 8|7 1 2|
            +-----+-----+-----+

No conozco una biblioteca de programación restringida en Python, ni conozco un puerto de Eclipse a Python. Pero mi experiencia es que todos los lenguajes de programación modernos tienen esa herramienta.

los ventaja de usar una herramienta de programación de restricciones como Eclipse, Gecode, ... es ante todo que solo tienes que especificar su problema, cómo se resuelve es algo de lo que no tiene que preocuparse. Además, estas bibliotecas implementan 30 años de investigación sobre programación de restricciones: están extremadamente optimizadas, explotan restricciones y estructuras de una manera que la mayoría de la gente no puede imaginar y es menos probable que contenga errores (que un algoritmo hecho a medida). Además, si se encuentran nuevas estrategias, algoritmos, ... una actualización de Eclipse resultará en un procesamiento más rápido del modelo.

UN desventaja es que algunos problemas difíciles aún no se pueden resolver usando la programación de restricciones: el espacio de búsqueda es simplemente demasiado grande, las restricciones son tan complejas que los dominios no se reducen a conjuntos pequeños, y no hay suficiente poder de procesamiento para hacer suficiente elecciones para encontrar una solución válida Otra desventaja es que no siempre es fácil especificar un problema: aunque los programadores intentan diseñar buenas restricciones, siempre hay problemas complejos en los que no se definen restricciones fáciles de usar.

Otras tecnicas

Evidentemente, hay otras técnicas de IA para resolver problemas. Una técnica que se usa comúnmente para abordar problemas de búsqueda y optimización difíciles es computación evolutiva: uno comienza rellenando el sudoku permitiendo que algunos valores sean incorrectos, luego en cada paso de tiempo apuntan a corregir uno o más campos. A veces introducen nuevos errores para encontrar finalmente una solución válida.


15
2017-12-13 01:40



Un enfoque diferente sería usar un algoritmo genético. Que se basa en la evolución biológica. Los algoritmos genéticos son parte de los algoritmos evolutivos y, por lo tanto, comparten la analogía "función física". Una solución válida se encuentra mediante recombinación, selección y mutación.

El concepto básico es inicializar una serie de soluciones "individuos" que consisten en "cromosomas" por azar (las soluciones pueden estar equivocadas, por supuesto). Defina una "función de aptitud" que evalúa la calidad de cada individuo dentro de la "generación" actual. Tome con mayor probabilidad a las personas con mejor aptitud para recombinarlas en una solución "infantil" y mute, con una baja probabilidad, algunas personas dentro de la nueva generación. Repita hasta que algunos criterios (max_iteration_count, valid_solution_found) sean verdaderos.

Para ajustar un algoritmo genético a su problema. Podrías hacer algo como lo siguiente. Cree para cada sudoku 3x3 o 9x9 una solución local correcta. Estos son los cromosomas. Póngalos en una estructura de datos. Eso es un individuo. Crea muchos de ellos para formar una generación. Evaluar a cada individuo por las restricciones que viola. Calcular la probabilidad correspondiente. Recombine los individuos, mute algunos cromosomas, repita.

Podrías verlo como una combinación de optimización local y global. Ya que necesitaría algún tipo de algoritmo codicioso (o lo que quiera usar para resolver el sudoku local) para encontrar un local, y el GA para encontrar los óptimos globales globales. Creo que no tendría sentido usar solo el GA y tratar de resolver este problema. Implementé una AG en un problema combinatorio recientemente y, sin optimización local, los resultados fueron, en la mayoría de los casos, bastante terribles.

Sin embargo, lo bueno de GA es que hacen grandes pasos al principio de la búsqueda que convergen hacia un óptimo, pero aún cubren grandes partes del espacio de búsqueda. Pero como siempre con EA, ajustar los parámetros puede ser bastante delicado.


1
2017-12-13 07:18