Ce n'est pas un solveur Sudoku, ni un vérificateur Sudoku.

Votre défi est d'écrire une fonction ou un script qui, étant donné en entrée la taille "bloc" d'un puzzle Sudoku 2D (qui est 3 pour la carte classique 9x9 , 4 pour une carte 16x16 , etc.) calculera une approximation du nombre de puzzles (solutions) distincts qui existent pour cette taille.

Par exemple, étant donné l'entrée 3, votre programme devrait imprimer une approximation, avec la précision souhaitée, du nombre 6,670,903,752,021,072,936,960 qui est le nombre connu de puzzles Sudoku 9x9 distincts , ou 5,472,730,538 en tenant compte des différentes symétries. Votre solution doit indiquer si les symétries sont comptées ou ignorées.

La «précision souhaitée» n'est pas définie: votre programme peut s'exécuter pendant un temps donné, puis produire son résultat, ou le calculer jusqu'à un nombre donné de chiffres significatifs, ou même s'exécuter indéfiniment, en imprimant de meilleures approximations. Le fait est qu'il devrait être possible de lui faire calculer le résultat avec toute précision requise, dans un temps fini. (Donc "42" n'est pas une réponse acceptable.) Restreindre la précision de votre résultat aux flotteurs disponibles de la machine est acceptable.

Pas d'accès aux ressources en ligne, pas de stockage du code source dans le nom de fichier, etc.

PS: Je sais que c'est un problème difficile (NP-complet si je ne me trompe pas.) Mais cette question ne demande qu'une solution statistique approximative. Par exemple, vous pouvez essayer des configurations aléatoires qui satisfont à une (ou mieux deux) contraintes, calculer le nombre de celles qui existent, puis vérifier la fréquence à laquelle vous obtenez un puzzle qui satisfait aux trois contraintes. Cela fonctionnera dans un temps décent pour les petites tailles (certainement pour la taille = 3 et peut-être 4) mais l'algorithme devrait être suffisamment générique pour fonctionner pour n'importe quelle taille.

Le meilleur algorithme gagne.

PS2: J'ai changé de code-golf en code-challenge pour mieux refléter la difficulté du problème et encourager des solutions plus intelligentes, plutôt que des solutions stupides mais bien golfées. Mais comme apparemment le "meilleur algorithme" n'est pas clair, permettez-moi d'essayer de le définir correctement.

Étant donné suffisamment de temps et sans tenir compte des facteurs constants (y compris le processeur et la vitesse des interprètes), ou de manière équivalente, compte tenu de leur comportement asymptotique, quelle solution convergerait vers le résultat exact le plus rapidement?

C ++

Ce que je vais présenter ici est un algorithme, illustré d'un exemple pour un cas 3x3. Il pourrait théoriquement être étendu au cas NxN, mais cela nécessiterait un ordinateur beaucoup plus puissant et / ou quelques ajustements ingénieux. Je mentionnerai quelques améliorations au fur et à mesure.

Avant d'aller plus loin, notons les symétries de la grille Sudoku, c'est-à-dire les transformations qui conduisent à une autre grille de manière triviale. Pour la taille de bloc 3, les symétries sont les suivantes:

Symétrie horizontale

**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

Symétrie verticale

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

Notez que les réflexions horizontales et verticales de la grille peuvent être obtenues par une combinaison de celles-ci, elles n'ont donc pas besoin d'être comptées. Il y a une autre symétrie spatiale à considérer, qui est la transposition, qui est un facteur de 2. Cela donne la symétrie spatiale totale de

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

Il y a ensuite une autre symétrie très importante, appelée réétiquetage.

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

Le nombre total de solutions ne peut pas être trouvé simplement en multipliant le nombre de solutions uniques de symétrie par ce nombre, car il existe un certain nombre (moins de 1%) de solutions automorphes. Cela signifie que pour ces solutions spéciales, il existe une opération de symétrie qui les mappe à elles-mêmes, ou plusieurs opérations de symétrie qui les mappent à la même autre solution.

Pour estimer le nombre de solutions, j'aborde le problème en 4 étapes:

1. remplissez un tableau r[362880][12]avec toutes les permutations possibles des nombres 0 à 8. (c'est de la programmation, et c'est en C, donc nous n'allons pas utiliser 1 à 9.) Si vous êtes astucieux, vous remarquerez que le deuxième indice est 12 pas 9. C'est parce que, tout en faisant cela, en gardant à l'esprit que nous allons considérer cela comme une "ligne", nous calculons également trois entiers supplémentaires r[9,10,11] == 1<<a | 1<<b | 1<<coù 9,10,11 se réfèrent à la première, la deuxième et la troisième pile et a, b, c sont les trois nombres présents dans chaque pile pour cette ligne.

Remplissez un tableau bavec toutes les solutions possibles d'une bande de 3 lignes. Pour garder cette taille raisonnablement petite, n'incluez que les solutions où la ligne supérieure est 012 345 678. Je le fais par force brute, en générant toutes les lignes centrales possibles et en faisant un AND r[0][10,11,12]avec r[i][10,11,12]. Toute valeur positive signifie qu'il y a deux nombres identiques dans le même carré et que la bande n'est pas valide. Quand il y a une combinaison valide pour les deux premières lignes, je recherche la 3e ligne (en bas) avec la même technique.

J'ai dimensionné le tableau comme b [2000000] [9] mais le programme ne trouve que 1306368 solutions. Je ne savais pas combien il y en avait, alors j'ai laissé la dimension du tableau comme ça. Ce n'est en fait que la moitié des solutions possibles pour une seule bande (vérifiée sur wikipedia), car je ne balaye la 3e ligne à partir de la valeur actuelle que ivers le haut. La moitié restante des solutions peut être trouvée trivialement en échangeant les 2e et 3e rangées.

La façon dont les informations sont stockées dans un tableau best un peu déroutante au début. au lieu d'utiliser chaque entier pour stocker les nombres 0..8trouvés dans une position donnée, ici chaque entier considère l'un des nombres 0..8et indique dans quelles colonnes il peut être trouvé. ainsi b[x][7]==100100001indiquerait que pour la solution x le nombre 7 se trouve dans les colonnes 0,5 et 8 (de droite à gauche.) La raison de cette représentation est que nous devons générer le reste des possibilités de la bande par réétiquetage, et ce la représentation le rend commode.

Les deux étapes ci-dessus comprennent la configuration et prennent environ une minute (probablement moins si j'ai supprimé la sortie de données inutiles. Les deux étapes ci-dessous sont la recherche réelle.)

3 Recherchez au hasard des solutions pour les deux premières bandes qui ne s'affrontent pas (c.-à-d. N'ont pas le même nombre deux fois dans une colonne donnée. Nous choisissons une solution aléatoire pour la bande 1, en supposant toujours la permutation 0, et une solution aléatoire pour la bande 2 avec une permutation aléatoire. Un résultat se trouve normalement dans moins de 9 999 essais (taux de réussite du premier étage dans la gamme des milliers) et prend une fraction de seconde. Par permutation, je veux dire que pour la deuxième bande, nous prenons une solution de b [] [] où la première ligne est toujours 012 345 678 et la renommer de sorte que toute séquence de nombres possible sur la première ligne soit possible.

4 Lorsqu'un hit est trouvé à l'étape 3, recherchez une solution pour la troisième bande qui ne se heurte pas aux deux autres. Nous ne voulons pas faire un seul essai, sinon le temps de traitement pour l'étape 3 serait perdu. D'un autre côté, nous ne voulons pas y consacrer un effort excessif.

Juste pour le plaisir, hier soir, je l'ai fait de la manière la plus stupide possible, mais c'était toujours intéressant (parce que cela n'a rien pour les âges, puis j'ai trouvé un grand nombre de solutions en rafales.) Il a fallu toute la nuit pour obtenir un point de donnée, même avec le petit hack (!z)J'ai fait avorter la dernière kboucle dès que nous savons que ce n'est pas une solution valide (ce qui la fait fonctionner presque 9 fois plus vite.) Il a trouvé 1186585 solutions pour la grille complète après avoir recherché toutes les 362880 relabellings de toutes les 1306368 solutions canoniques pour la dernière bloc, un total de 474054819840 possibilités. C'est un taux de réussite de 1 sur 400000 pour la deuxième étape. Je vais réessayer bientôt avec une recherche aléatoire plutôt qu'une analyse. Il devrait donner une réponse raisonnable en seulement quelques millions d'essais, ce qui ne devrait prendre que quelques secondes.

La réponse globale devrait être (362880 * (1306368 * 2)) ^ 3 * taux de réussite = 8,5E35 * taux de réussite. En calculant à partir du nombre dans la question, je m'attends à un taux de réussite de 1 / 1.2E14. Ce que j'ai jusqu'à présent avec mon point de donnée unique est 1 / (400000 * 1000), ce qui représente un facteur d'environ un million. Cela pourrait être une anomalie du hasard, une erreur dans mon programme ou une erreur dans mes calculs. Je ne saurai pas de quoi il s'agit avant d'exécuter quelques tests supplémentaires.

Je vais laisser ça ici pour ce soir. Le texte est un peu scrappy, je vais le ranger bientôt et j'espère ajouter d'autres résultats, et peut-être quelques mots sur la façon de le rendre plus rapide et sur la façon d'étendre le concept à N = 4. Je ne pense pas que j'apporterai trop de changements à mon programme, cependant :-)

Ah .. le programme:

#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();
}