Este no es un solucionador de Sudoku, ni un corrector de Sudoku.

Su desafío es escribir una función o script que, dado como entrada, el tamaño de "bloque" de un rompecabezas Sudoku 2D (que es 3 para el tablero clásico de 9x9 , 4 para un tablero de 16x16 , etc.) calculará una aproximación del número de acertijos distintos (soluciones) que existen para ese tamaño.

Por ejemplo, dada la entrada 3, su programa debería imprimir una aproximación, con la precisión deseada, del número 6,670,903,752,021,072,936,960, que es el número conocido de acertijos Sudoku 9x9 distintos , o 5,472,730,538 al tener en cuenta las diversas simetrías. Su solución debe indicar si las simetrías se cuentan o se ignoran.

La "precisión deseada" no se define: su programa puede ejecutarse durante un tiempo determinado y luego generar su resultado, o calcularlo hasta un número determinado de dígitos significativos, o incluso ejecutarse para siempre, imprimiendo mejores y mejores aproximaciones. El punto es que debería ser posible hacer que calcule el resultado con cualquier precisión requerida, en un tiempo finito. (Por lo tanto, "42" no es una respuesta aceptable). Restringir la precisión de su resultado a los flotadores de máquina disponibles es aceptable.

Sin acceso a recursos en línea, sin almacenar el código fuente en el nombre del archivo, etc.

PD: Sé que este es un problema difícil (NP completo si no me equivoco). Pero esta pregunta solo está pidiendo una solución estadística aproximada. Por ejemplo, puede probar configuraciones aleatorias que satisfagan una (o mejores dos) restricciones, calcule cuántas existen y luego verifique con qué frecuencia obtiene un rompecabezas que satisfaga las tres restricciones. Esto funcionará en un tiempo decente para tamaños pequeños (ciertamente para tamaño = 3 y posiblemente 4), pero el algoritmo debe ser lo suficientemente genérico como para funcionar para cualquier tamaño.

El mejor algoritmo gana.

PS2: Cambié de código de golf a código de desafío para reflejar mejor la dificultad del problema y alentar soluciones más inteligentes, sobre las tontas pero bien desarrolladas. Pero dado que aparentemente el "mejor algoritmo" no está claro, déjame intentar definirlo correctamente.

Dado el tiempo suficiente y sin tener en cuenta los factores constantes (incluida la CPU y la velocidad del intérprete), o de manera equivalente, teniendo en cuenta su comportamiento asintótico, ¿ qué solución convergería al resultado exacto más rápido?

C ++

Lo que presentaré aquí es un algoritmo, ilustrado con un ejemplo para un caso 3x3. Teóricamente podría extenderse al caso NxN, pero eso necesitaría una computadora mucho más poderosa y / o algunos ajustes ingeniosos. Mencionaré algunas mejoras a medida que avance.

Antes de continuar, observemos las simetrías de la cuadrícula de Sudoku, es decir , las transformaciones que conducen a otra cuadrícula de manera trivial. Para el tamaño de bloque 3, las simetrías son las siguientes:

Simetría horizontal

**The N=3 sudoku is said to consist of 3 "bands" of 3 "rows" each**
permute the three bands: 3! permutations = 6
permute the rows in each band: 3 bands, 3! permutations each =(3!)^3=216

Simetría vertical

**The N=3 sudoku is said to consist of 3 "stacks" of 3 "columns" each.**
the count is the same as for horizontal.

Tenga en cuenta que los reflejos horizontales y verticales de la cuadrícula se pueden lograr mediante una combinación de estos, por lo que no es necesario contarlos. Hay una simetría espacial más a considerar, que es la transposición, que es un factor de 2. Esto da la simetría espacial total de

2*(N!*(N!)^N)^2 = 2*(6*216)^2=3359232 spatial symmetries for the case N=3.

Luego hay otra simetría muy importante, llamada re-etiquetado.

Relabelling gives a further (N^2)!=9!=362880 symmetries for the case N=3. So the total 
number of symmetries is 362880*3359232=1218998108160.

No se puede encontrar el número total de soluciones simplemente multiplicando el número de soluciones únicas de simetría por este número, porque hay un número (menos del 1%) de soluciones automorfas. Eso significa que para estas soluciones especiales hay una operación de simetría que las asigna a sí mismas, o múltiples operaciones de simetría que las asignan a la misma otra solución.

Para estimar el número de soluciones, abordo el problema en 4 pasos:

1.Rellena una matriz r[362880][12]con todas las permutaciones posibles de los números del 0 al 8. (esto es programación y está en C, por lo que no vamos a usar del 1 al 9.) Si eres astuto, notarás que el segundo subíndice es 12 no 9. Esto se debe a que, al hacer esto, teniendo en cuenta que vamos a considerar que se trata de una "fila", también calculamos tres enteros más, r[9,10,11] == 1<<a | 1<<b | 1<<cdonde 9,10,11 se refieren a la primera, segunda y tercera pila. y a, b, c son los tres números presentes en cada pila para esa fila.

2. Llene una matriz bcon todas las soluciones posibles de una banda de 3 filas. Para mantener esto razonablemente pequeño, solo incluya aquellas soluciones donde la fila superior sea 012,345,678. Lo hago por fuerza bruta, generando todas las filas intermedias posibles y ANDing r[0][10,11,12]con r[i][10,11,12]. Cualquier valor positivo significa que hay dos números idénticos en el mismo cuadrado y la banda no es válida. Cuando hay una combinación válida para las dos primeras filas, busco en la tercera fila (inferior) con la misma técnica.

Dimensioné la matriz como b [2000000] [9] pero el programa solo encuentra soluciones 1306368. No sabía cuántos había, así que dejé la dimensión de la matriz así. En realidad, esta es solo la mitad de las soluciones posibles para una sola banda (verificada en wikipedia), porque solo escaneo la tercera fila desde el valor actual hacia iarriba. La mitad restante de las soluciones se puede encontrar trivialmente intercambiando la segunda y la tercera fila.

La forma en que la información se almacena en una matriz bes un poco confusa al principio. en lugar de usar cada número entero para almacenar los números 0..8encontrados en una posición dada, aquí cada número entero considera uno de los números 0..8e indica en qué columnas se puede encontrar. por b[x][7]==100100001lo tanto , indicaría que para la solución x el número 7 se encuentra en las columnas 0,5 y 8 (de derecha a izquierda). La razón de esta representación es que necesitamos generar el resto de las posibilidades para la banda volviendo a etiquetar, y esto la representación hace que sea conveniente hacer esto.

Los dos pasos anteriores comprenden la configuración y toman aproximadamente un minuto (posiblemente menos si eliminé la salida de datos innecesarios. Los dos pasos a continuación son la búsqueda real).

3 Busque al azar soluciones para las dos primeras bandas que no entren en conflicto (es decir, que no tengan el mismo número dos veces en una columna determinada. Escogemos una solución aleatoria para la banda 1, suponiendo siempre la permutación 0, y una solución aleatoria para la banda 2 con una permutación aleatoria. Un resultado normalmente se encuentra en menos de 9999 intentos (tasa de aciertos de la primera etapa en el rango de miles) y toma una fracción de segundo. Por permutación, quiero decir que para la segunda banda tomamos una solución de b [] [] donde la primera fila es siempre 012,345,678 y la vuelve a etiquetar para que sea posible cualquier secuencia de números en la primera fila.

4 Cuando se encuentra un hit en el paso 3, busque una solución para la tercera banda que no choque con las otras dos. No queremos hacer un solo intento, de lo contrario se desperdiciaría el tiempo de procesamiento para el paso 3. Por otro lado, no queremos poner una cantidad excesiva de esfuerzo en esto.

Solo por diversión, anoche lo hice de la manera más tonta posible, pero aún así fue interesante (porque no fue nada durante años, luego encontré un gran número de soluciones en ráfagas). Me llevó toda la noche obtener un punto de datos, incluso con el pequeño truco (!z)Hice un aborto para el último kbucle tan pronto como sabemos que esta no es una solución válida (lo que hace que se ejecute casi 9 veces más rápido). Encontró 1186585 soluciones para la cuadrícula completa después de buscar todas las 362880 reenvíos de todas las 1306368 soluciones canónicas para el último bloque, un total de 474054819840 posibilidades. Esa es una tasa de éxito de 1 en 400000 para la segunda etapa. Intentaré nuevamente pronto con una búsqueda aleatoria en lugar de un escaneo. Debería dar una respuesta razonable en solo unos pocos millones de intentos, lo que debería llevar solo unos segundos.

La respuesta general debe ser (362880 * (1306368 * 2)) ^ 3 * tasa de aciertos = 8.5E35 * tasa de aciertos. Al volver a calcular el número en la pregunta, espero una tasa de éxito de 1 / 1.2E14. Lo que tengo hasta ahora con mi único punto de datos es 1 / (400000 * 1000) que está fuera por un factor de aproximadamente un millón. Esto podría ser una anomalía de azar, un error en mi programa o un error en mis matemáticas. No sabré cuál es hasta que realice algunas pruebas más.

Dejaré esto aquí por esta noche. El texto es un poco descuidado, lo ordenaré pronto y espero agregar algunos resultados más, y tal vez algunas palabras sobre cómo hacerlo más rápido y cómo extender el concepto a N = 4. Sin embargo, no creo que vaya a hacer muchos más cambios en mi programa :-)

Ah .. el programa:

#include "stdafx.h"
#define _CRT_RAND_S
#include <algorithm>  
#include <time.h>

unsigned int n[] = { 0,1,2,3,4,5,6,7,8 }, r[362880][12], b[2000000][9],i,j,k,l,u,v,w,x,y,z;

int main () {

  //Run through all possible permutations of n[] and load them into r[][] 
  i=0;  
  do {
      r[i][9] = r[i][10] = r[i][11]=0;
      for (l = 0; l < 9; l++){
          r[i][l] = n[l];
          r[i][9 + l / 3] |= 1 << n[l];
      }
      if((i+1)%5040==0) printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
          ,r[i][0],r[i][1],r[i][2],r[i][3],r[i][4],r[i][5],r[i][6],r[i][7],r[i][8],r[i][9],r[i][10],r[i][11],r[i][9]+r[i][10]+r[i][11]);
      i++;
  } while ( std::next_permutation(n,n+9) );

  //Initialise b[][]
  for (l = 0; l<2000000; l++) for (k = 0; k<9; k++) b[l][k]=0;
  //fill b[][] with all solutions of the first band, where row0 ={0,1,2,3,4,5,6,7,8} and row1<row2 
  l=0;
  for (i = 0; i<362880; i++) 
  if (!(r[0][9] & r[i][9] | r[0][10] & r[i][10] | r[0][11] & r[i][11])){printf("%d %d \n",i,l);
     for (j=i; j<362880;j++) 
       if(!(r[0][9]&r[j][9] | r[0][10]&r[j][10] | r[0][11]&r[j][11] | r[j][9]&r[i][9] | r[j][10]&r[i][10] | r[j][11]&r[i][11] )){
           for (k = 0; k < 9; k++){
               b[l][r[0][k]]|=1<<k;
               b[l][r[i][k]]|=1<<k;
               b[l][r[j][k]]|=1<<k;
            } 
            l++;
       }
//        printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
//        ,r[i][0],r[i][1],r[i][2],r[i][3],r[i][4],r[i][5],r[i][6],r[i][7],r[i][8],r[i][9],r[i][10],r[i][11],r[i][9]+r[i][10]+r[i][11]);
//        printf("%d%d%d %d%d%d %d%d%d %o %o %o %o \n"
//        ,r[j][0],r[j][1],r[j][2],r[j][3],r[j][4],r[j][5],r[j][6],r[j][7],r[j][8],r[j][9],r[j][10],r[j][11],r[j][9]+r[j][10]+r[j][11]);
//        printf("%d %d %o %o %o %o %o %o %o %o %o \n",i,l,b[l][0],b[l][1],b[l][2],b[l][3],b[l][4],b[l][5],b[l][6],b[l][7],b[l][8]);
  }

  // find a random solution for the first 2 bands
  l=0;
  do{
      rand_s(&u); u /= INT_MIN / -653184; //1st band selection
      rand_s(&v); v /= INT_MIN / -181440; //2nd band permutation
      rand_s(&w); w /= INT_MIN / -653184; //2nd band selection
      z = 0;
      for (k = 0; k < 9; k++) z |= b[u][k] & b[w][r[v][k]];
      l++;
  } while (z);
  printf("finished random after %d tries \n",l);
  printf("found solution with top band %d permutation 0, and middle band %d permutation %d \n",u,w,v);
  getchar();

  // scan all possibilities for the last band
  l=0;
  for (i = 0; i < 362880; i++) for (j = 0; j < 1306368; j++){
              z=0;
              for(k=0;(k<9)&&(!z);k++) z|= b[u][k] & b[j][r[i][k]] | b[j][r[i][k]] & b[w][r[v][k]];
              if (!z){ l++; printf("solution %d : i= %d j=%d",l,i,j); }
  }
  printf("finished bottom band scan at %d millisec \n", clock()); getchar();
}