algorithm - solucionador - sudoku resuelto de 3x3

Cómo generar tableros Sudoku con soluciones únicas

Question

¿Cómo se genera una placa Sudoku con una solución única? Lo que pensé fue inicializar un tablero aleatorio y luego eliminar algunos números. Pero mi pregunta es ¿cómo puedo mantener la singularidad de una solución?

Answer 1

A menos que P = NP, no existe un algoritmo de tiempo polinomial para generar problemas generales de Sudoku con exactamente una solución.

En su tesis de maestría, Takayuki Yato definió El otro problema de solución (ASP), donde el objetivo es, dado un problema y una solución, encontrar una solución diferente a ese problema o demostrar que no existe ninguno. Yato definió la integridad de ASP, problemas para los cuales es difícil encontrar otra solución, y demostró que Sudoku es ASP completo. Como también demuestra que la integridad de ASP implica dureza NP, esto significa que si permite tablas Sudoku de tamaño arbitrario, no hay un algoritmo de tiempo polinomial para comprobar si el rompecabezas que ha generado tiene una solución única (a menos que P = NOTARIO PÚBLICO).

Perdón por arruinar tus esperanzas de un algoritmo rápido.

Answer 2

Aquí hay una manera de hacer un sudoku clásico (sudoku puzzle con una única solución, los cuadrados precargados son simétricos alrededor del cuadrado central R5C5).

1) comience con una grilla completa (usando relleno de grupo más desplazamiento circular para obtenerlo fácilmente)

2) eliminar número (s) de dos cuadrados simétricos si los cuadrados borrados se pueden inferir utilizando las pistas restantes.

3) repita (2) hasta que todos los números estén marcados.

Usando este método puedes crear un sudoku muy fácil con o sin programación. También puedes utilizar este método para crear rompecabezas Sudoku más difíciles. Es posible que desee buscar "crear sudoku clásico" en YouTube para tener un ejemplo paso a paso.

Answer 3

Así es como lo hace mi propio programa SuDoKu:

1. Comience con un tablero completo y válido (lleno con 81 números).

2. Haz una lista de las 81 posiciones de celda y baraja aleatoriamente.

3. Siempre que la lista no esté vacía, tome la siguiente posición de la lista y elimine el número de la celda relacionada.

4. Prueba la singularidad usando un solucionador de retroceso rápido. Mi solucionador es, en teoría, capaz de contar todas las soluciones, pero para probar la singularidad, se detendrá inmediatamente cuando encuentre más de una solución.

5. Si la placa actual todavía tiene una solución, vaya al paso 3) y repita.

6. Si la placa actual tiene más de una solución, deshaga la última eliminación (paso 3) y continúe con la posición siguiente de la lista.

7. Deténgase cuando haya probado las 81 posiciones.

Esto le brinda no solo tableros únicos, sino tableros donde no puede eliminar más números sin destruir la singularidad de la solución.

Por supuesto, esta es solo la segunda mitad del algoritmo. La primera mitad es encontrar una tabla válida completa primero (¡rellena aleatoriamente!) Funciona muy similar, pero "en la otra dirección":

1. Comience con un tablero vacío.

2. Agregue un número aleatorio en una de las celdas libres (la celda se elige al azar, y el número se elige aleatoriamente de la lista de números válidos para esta celda según las reglas de SuDoKu).

3. Use el solucionador de retroceso para verificar si la placa actual tiene al menos una solución válida. Si no, deshaga el paso 2 y repita con otro número y celda. Tenga en cuenta que este paso puede producir tableros completos válidos por sí solos, pero que de ninguna manera son aleatorios.

4. Repita hasta que el tablero esté completamente lleno de números.

Answer 4

Esta lógica le dará un sudoku 9 * 9 único cada vez que lo ejecute. Puede tomar de 15 minutos a 20 minutos generar un sudoku único.

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.Random;
//random numbers with incremental locations
//final solution for creating random sudoku
public class Sudoku {

    public static void main(String[] args) 
    {
        int b = 0;
        int Low = 1;
        int High = 10;
        boolean y=false;
        int[][] a= new int[9][9];
        Random r = new Random();
        int count1=0;
        int count2=0;
        int count3=0;
        long startTime = System.currentTimeMillis();
        long endTime;
        long totalTime; 
        int tc=0;

        //created 9*9 unique array 
        for(int i=0;i<9;i++) 
        {
            for(int j=0;j<9;j++) 
            {
                while(y==false)
                {
                b=(r.nextInt(High-Low) + Low);

                //check for duplicates horizontally 
                for(int x=0;x<9;x++)
                {
                        if(a[i][x]!=b)
                        {
                            ++count1;
                        }
                }

                //check vertically
                for(int d=0;d<9;d++)
                {
                        if(a[d][j]!=b)
                        {
                            ++count2;
                        }
                }

                //check for duplicates with in a 3*3 block
                int d=0;
                int e=0;

                for(int x1=0;x1<3;x1++) 
                {
                  for(int y1=0;y1<3;y1++) 
                  {

                    for(int i1=d;i1<d+3;i1++) 
                     {
                        for(int j1=e;j1<e+3;j1++) 
                        {
                            //System.out.print(a[i][j]+" ");

                            if(i==i1 && j==j1) 
                            {
                                for(int k=d;k<d+3;k++) 
                                 {
                                    for(int l=e;l<e+3;l++) 
                                    {
                                        if(b!=a[k][l]) {

                                            ++count3;
                                        }

                                    }
                                 }
                            }

                        }
                        //System.out.println();
                     }
                    e=e+3;
                    //System.out.println();
                  }
                  e=0;
                  d=d+3;
                  //System.out.println();
                }




                if(count1==9 && count2==9 && count3==9) 
                {
                    System.out.print(b+" ");
                    a[i][j]=b;
                    tc++;
                    y=true;
                    break;

                }
                else 
                {
                    y=false;
                }
                count1=0;
                count2=0;
                count3=0;
                endTime=System.currentTimeMillis();
                totalTime=endTime-startTime;


                if(totalTime>2000)
                {
                    System.out.println();
                    System.out.println("reset "+tc);
                    //System.out.println();
                    startTime=System.currentTimeMillis();
                    a=new int[9][9];
                    count1=0;
                    count2=0;
                    count3=0;
                    y=true;
                    b=0;
                    tc=0;
                    main(null);
                    break;
                }

                }
                y=false;
                if (i==8 && j==8)
                {
                    break;
                }
            }

            System.out.println();

        }

        //print the sudoku
        /*for(int m=0;m<9;m++)
        {
            for(int n=0;n<9;n++) 
            {
                System.out.print(a[m][n]+" ");
            }
            System.out.println();
        }*/
        for(int i=1;i<=9;i++) 
        {
            int t=i-1;
            for (int j=1;j<=9;j++)
            {
                if(j==1) {
                System.out.print("|");}
                int s=j-1;
                System.out.print(a[t][s]);

                if (j%3==0)
                System.out.print("|");
                else
                 System.out.print(",");

            }
            if(i%3==0 && i<9) {
                System.out.println();
                for (int j=1;j<=9;j++)
            {
                if(j==1) {
                System.out.print("|");}     
                if (j%3==0 &&j<9)
                System.out.print("-+");
                else if(j%3==0 && j==9)
                System.out.print("-|");
                else
                System.out.print("--");
            }
            }

            System.out.println();

        }
        DateFormat dateFormat = new SimpleDateFormat("yyyy/MM/dd HH:mm:ss");
        Date date = new Date();
        System.out.println(dateFormat.format(date)); //2016/11/16 12:08:43
        System.exit(0);

    }

}

Answer 5

Fácil:

1. Encuentre todas las soluciones con un algoritmo de retroceso eficiente.
2. Si solo hay una solución, ya terminaste. De lo contrario, si tiene más de una solución, encuentre una posición en la cual la mayoría de las soluciones difieren. Agrega el número en esta posición.
3. Ir a 1.

Dudo que puedas encontrar una solución que sea mucho más rápida que esto.

Answer 6

No es fácil dar una solución genérica. Necesita saber algunas cosas para generar un tipo específico de Sudoku ... por ejemplo, no puede construir un Sudoku con más de nueve grupos vacíos de nueve números (filas, bloques o columnas de 3x3). Se cree que un mínimo de números dados (es decir, "pistas") en una solución única Sudoku es 17, pero las posiciones numéricas para este Sudoku son muy específicas si no estoy equivocado. El número promedio de pistas para un Sudoku es de alrededor de 26, y no estoy seguro, pero si abandonas los números de una grilla completa hasta tener 26 y los dejas de forma simétrica, puedes tener un Sudoku válido. Por otro lado, puede salir aleatoriamente de las cuadrículas completas y probarlas con CHECKER u otras herramientas hasta que aparezca un mensaje OK.

Answer 7

Puedes hacer trampa. Comience con una tabla de Sudoku existente que se pueda resolver y luego toquetee con ella.

Puedes intercambiar cualquier fila de tres bloques de 3x3 con cualquier otra fila. Puedes intercambiar cualquier columna de tres bloques de 3x3 con otra columna. Dentro de cada fila de bloque o columna puede intercambiar filas individuales y columnas individuales. Finalmente puede permutar los números para que haya diferentes números en las posiciones llenas, siempre y cuando la permutación sea constante en todo el tablero.

Ninguno de estos cambios hará que una placa resoluble sea insoluble.

Answer 8

También creo que tendrá que verificar explícitamente la singularidad. Sin embargo, si tiene menos de 17 datos, es muy poco probable una solución única: todavía no se ha encontrado ninguno, aunque aún no está claro si podría existir).

Pero también puede usar un solucionador de SAT, en lugar de escribir un algoritmo de retroceso propio. De esta forma, usted puede, hasta cierto punto, regular cuán difícil será encontrar una solución: si restringe las reglas de inferencia que usa el solucionador SAT, puede verificar si puede resolver el rompecabezas fácilmente. Solo busca "sudoku resolviendo SAT".