Este não é um solucionador de Sudoku, nem um verificador de Sudoku.

Seu desafio é escrever uma função ou script que, dado como entrada o tamanho "bloco" de um quebra-cabeça 2D de Sudoku (que é 3 para o quadro 9x9 clássico , 4 para um quadro 16x16 , etc.), calcule uma aproximação do número de quebra-cabeças (soluções) distintos que existem para esse tamanho.

Por exemplo, dada a entrada 3, seu programa deve imprimir uma aproximação, com a precisão desejada, do número 6.670.903.752.021.072.936.960, que é o número conhecido de quebra-cabeças de Sudoku 9x9 distintos , ou 5.472.730.538, considerando as várias simetrias. Sua solução deve indicar se simetrias são contadas ou ignoradas.

A "precisão desejada" é deixada indefinida: seu programa pode ser executado por um determinado tempo e, em seguida, gerar o resultado, ou computá-lo até um número determinado de dígitos significativos, ou mesmo executar para sempre, imprimindo aproximações cada vez melhores. A questão é que deve ser possível calcular o resultado com a precisão necessária, em um tempo finito. (Portanto, "42" não é uma resposta aceitável.) Restringir a precisão do seu resultado às flutuações disponíveis da máquina é aceitável.

Sem acesso a recursos online, sem armazenamento do código-fonte no nome do arquivo, etc.

PS: Eu sei que este é um problema difícil (NP-completo, se não me engano). Mas essa pergunta está apenas pedindo uma solução estatística aproximada. Por exemplo, você pode tentar configurações aleatórias que atendam a uma (ou duas melhores) restrições, calcule quantas delas existem e verifique com que frequência você obtém um quebra-cabeça que atenda às três restrições. Isso funcionará em um tempo decente para tamanhos pequenos (certamente para tamanho = 3 e possivelmente 4), mas o algoritmo deve ser genérico o suficiente para funcionar para qualquer tamanho.

O melhor algoritmo vence.

PS2: mudei de code-golf para code-challenge para refletir melhor a dificuldade do problema e incentivar soluções mais inteligentes, do que as idiotas, mas bem-treinadas. Mas, como aparentemente o "melhor algoritmo" não é claro, deixe-me tentar defini-lo corretamente.

Dado tempo suficiente e desconsiderando fatores constantes (incluindo CPU e velocidade do intérprete), ou equivalente, considerando seu comportamento assintótico, qual solução convergiria para o resultado exato mais rapidamente?

C ++

O que apresentarei aqui é um algoritmo, ilustrado com um exemplo para um caso 3x3. Teoricamente, poderia ser estendido ao caso NxN, mas isso exigiria um computador muito mais poderoso e / ou alguns ajustes engenhosos. Vou mencionar algumas melhorias à medida que passo.

Antes de prosseguir, vamos observar as simetrias da grade do Sudoku, ou seja , as transformações que levam a outra grade de maneira trivial. Para o tamanho do bloco 3, as simetrias são as seguintes:

Simetria 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

Simetria vertical

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

Observe que os reflexos horizontais e verticais da grade podem ser alcançados por uma combinação destes, portanto, eles não precisam ser contados. Há mais uma simetria espacial a ser considerada, que é a transposição, que é um fator de 2. Isso fornece a simetria espacial total de

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

Depois, há outra simetria muito importante, chamada de nova etiquetagem.

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

O número total de soluções não pode ser encontrado simplesmente multiplicando o número de soluções exclusivas de simetria por esse número, porque há um número (menos de 1%) de soluções automórficas. Isso significa que, para essas soluções especiais, há uma operação de simetria que as mapeia para si mesmas, ou várias operações de simetria que as mapeiam para a mesma outra solução.

Para estimar o número de soluções, abordo o problema em 4 etapas:

1. Preencha uma matriz r[362880][12]com todas as permutações possíveis dos números de 0 a 8. (isso é programação e está em C, portanto, não usaremos 1 a 9.) Se você for esperto, notará que o segundo subscrito é 12 e não 9. Isso ocorre porque, ao fazer isso, tendo em mente que consideraremos isso uma "linha", também calculamos mais três números inteiros, r[9,10,11] == 1<<a | 1<<b | 1<<conde 9,10,11 se referem à primeira, segunda e terceira pilha e a, b, c são os três números presentes em cada pilha para essa linha.

2. Preencha uma matriz bcom todas as soluções possíveis de uma banda de 3 linhas. Para manter isso razoavelmente pequeno, inclua apenas as soluções em que a linha superior é 012.345.678. Eu faço isso por força bruta, gerando todas as linhas do meio possíveis e AND r[0][10,11,12]com r[i][10,11,12]. Qualquer valor positivo significa que existem dois números idênticos no mesmo quadrado e a banda é inválida. Quando há uma combinação válida para as duas primeiras linhas, pesquiso a terceira linha (inferior) com a mesma técnica.

Eu dimensionei a matriz como b [2000000] [9], mas o programa encontra apenas 1306368 soluções. Eu não sabia quantas havia, então deixei a dimensão da matriz assim. Na verdade, essa é apenas a metade das soluções possíveis para uma única banda (verificada na wikipedia), porque apenas digitalizo a terceira linha do valor atual para icima. A metade restante das soluções pode ser encontrada trivialmente trocando a 2ª e a 3ª linhas.

A maneira como as informações são armazenadas na matriz bé um pouco confusa no começo. em vez de usar cada número inteiro para armazenar os números 0..8encontrados em uma determinada posição, aqui cada número inteiro considera um dos números 0..8e indica em quais colunas ele pode ser encontrado. portanto b[x][7]==100100001, indicaria que, para a solução x, o número 7 é encontrado nas colunas 0,5 e 8 (da direita para a esquerda). O motivo dessa representação é que precisamos gerar o restante das possibilidades para a banda, re-rotulando, e isso representação torna conveniente fazer isso.

As duas etapas acima compreendem a configuração e demoram cerca de um minuto (possivelmente menos se eu removi a saída de dados desnecessária. As duas etapas abaixo são a pesquisa real).

3 Procure aleatoriamente soluções para as duas primeiras bandas que não se chocam (ou seja, não têm o mesmo número duas vezes em uma determinada coluna. Escolhemos uma solução aleatória para a banda 1, assumindo sempre a permutação 0, e uma solução aleatória para a banda 2 com uma permutação aleatória.O resultado é normalmente encontrado em menos de 9999 tentativas (taxa de acerto do primeiro estágio na faixa de milhares) e leva uma fração de segundo. Por permutação, quero dizer que para a segunda banda usamos uma solução de b [] [] onde a primeira linha é sempre 012,345,678 e re-rotule-a para que seja possível qualquer sequência possível de números na primeira linha.

4 Quando um hit for encontrado na etapa 3, procure uma solução para a terceira banda que não colidir com as outras duas. Não queremos fazer apenas uma tentativa, caso contrário, o tempo de processamento da etapa 3 seria desperdiçado. Por outro lado, não queremos colocar um esforço excessivo nisso.

Só por diversão, ontem à noite eu fiz da maneira mais burra possível, mas ainda era interessante (porque não há muito tempo, depois encontrei um grande número de soluções em rajadas.) Levou a noite toda para obter um ponto de dados, mesmo com o pequeno truque (!z)Fiz para abortar o último kloop assim que soubermos que essa não é uma solução válida (o que a torna quase 9 vezes mais rápida.) Ele encontrou 1186585 soluções para a grade completa depois de pesquisar todas as re-rotulagens 362880 de todas as 1306368 soluções canônicas pela última bloco, um total de 474054819840 possibilidades. Essa é uma taxa de acerto de 1 em 400000 para o segundo estágio. Em breve, tentarei novamente com uma pesquisa aleatória em vez de uma verificação. Deveria dar uma resposta razoável em apenas alguns milhões de tentativas, o que levaria apenas alguns segundos.

A resposta geral deve ser (362880 * (1306368 * 2)) ^ 3 * taxa de acerto = 8,5E35 * taxa de acerto. Ao calcular novamente a partir do número da pergunta, espero uma taxa de acerto de 1 / 1.2E14. O que eu tenho até agora com meu único ponto de dados é 1 / (400000 * 1000), que sai por um fator de cerca de um milhão. Isso pode ser uma anomalia de chance, um erro no meu programa ou um erro na minha matemática. Não saberei qual é até executar mais alguns testes.

Vou deixar isso aqui hoje à noite. O texto é um pouco complicado, eu vou arrumá-lo em breve e espero acrescentar mais alguns resultados, e talvez algumas palavras sobre como torná-lo mais rápido e como estender o conceito para N = 4. Acho que não vou fazer muitas outras alterações no meu programa :-)

Ah .. o 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();
}