To nie jest solver Sudoku ani sprawdzanie Sudoku.

Twoim wyzwaniem jest napisanie funkcji lub skryptu, który podając jako dane wejściowe rozmiar „bloku” łamigłówki 2D Sudoku (czyli 3 dla klasycznej planszy 9x9 , 4 dla planszy 16x16 itp.) Obliczy przybliżoną liczbę różnych łamigłówek (rozwiązań), które istnieją dla tego rozmiaru.

Na przykład, biorąc pod uwagę wejście 3, twój program powinien wypisać przybliżenie, z pożądaną precyzją, liczby 6,670,903,752,021,072,936,960, która jest znaną liczbą różnych łamigłówek Sudoku 9x9 , lub 5 472 730 538, biorąc pod uwagę różne symetrie. Twoje rozwiązanie powinno określać, czy symetrie są liczone, czy ignorowane.

„Pożądana precyzja” pozostaje niezdefiniowana: program może działać przez określony czas, a następnie wyświetlać wynik lub obliczyć go do określonej liczby cyfr znaczących, a nawet działać wiecznie, drukując coraz lepsze przybliżenia. Chodzi o to, że powinno być możliwe obliczenie wyniku z dowolną wymaganą precyzją, w skończonym czasie. (Zatem „42” nie jest akceptowalną odpowiedzią.) Dopuszczalne jest ograniczenie dokładności wyniku do dostępnych liczb zmiennoprzecinkowych maszyny.

Brak dostępu do zasobów online, brak przechowywania kodu źródłowego w nazwie pliku itp.

PS: Wiem, że jest to trudny problem (NP-zupełne, jeśli się nie mylę). Ale to pytanie wymaga jedynie przybliżonego, statystycznego rozwiązania. Na przykład możesz wypróbować losowe konfiguracje, które spełniają jedno (lub lepiej dwa) ograniczenia, obliczyć, ile z nich istnieje, a następnie sprawdzić, jak często otrzymujesz układankę, która spełnia wszystkie trzy ograniczenia. Będzie to działać w przyzwoitym czasie dla małych rozmiarów (z pewnością dla rozmiaru = 3 i ewentualnie 4), ale algorytm powinien być wystarczająco ogólny, aby działał dla dowolnego rozmiaru.

Najlepszy algorytm wygrywa.

PS2: Zmieniłem kod-golfa na kod-wyzwanie, aby lepiej odzwierciedlić trudność problemu i zachęcić do mądrzejszych rozwiązań, zamiast głupich, ale dobrze grających. Ale ponieważ najwyraźniej „najlepszy algorytm” jest niejasny, pozwól mi spróbować go poprawnie zdefiniować.

Biorąc pod uwagę wystarczającą ilość czasu i pomijając stałe czynniki (w tym szybkość procesora i szybkość interpretera), lub równoważnie, biorąc pod uwagę ich asymptotyczne zachowanie, które rozwiązanie uzyskałoby najszybszy dokładny wynik?

C ++

Przedstawię tutaj algorytm, zilustrowany przykładem przypadku 3x3. Teoretycznie można by go rozszerzyć na obudowę NxN, ale wymagałoby to znacznie mocniejszego komputera i / lub kilku genialnych poprawek. Będę wspominał o niektórych ulepszeniach w miarę przechodzenia.

Zanim przejdziemy dalej, zwróćmy uwagę na symetrie siatki Sudoku, czyli transformacje, które prowadzą do innej siatki w trywialny sposób. Dla wielkości bloku 3 symetrie są następujące:

Pozioma symetria

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

Symetria pionowa

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

Należy pamiętać, że poziome i pionowe odbicia siatki można uzyskać przez ich połączenie, więc nie trzeba ich liczyć. Należy wziąć pod uwagę jeszcze jedną symetrię przestrzenną, która jest transponowana, co jest czynnikiem 2. Daje to całkowitą symetrię przestrzenną

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

Potem jest inna, bardzo ważna symetria, zwana ponownym znakowaniem.

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

Całkowitej liczby rozwiązań nie można znaleźć po prostu przez pomnożenie liczby unikalnych dla symetrii rozwiązań przez tę liczbę, ponieważ istnieje liczba (mniej niż 1%) rozwiązań automorficznych. Oznacza to, że dla tych specjalnych rozwiązań istnieje operacja symetrii, która odwzorowuje je na siebie, lub wiele operacji symetrii, które odwzorowują je na to samo inne rozwiązanie.

Aby oszacować liczbę rozwiązań, podchodzę do problemu w 4 krokach:

1. Wypełnij tablicę r[362880][12]wszystkimi możliwymi kombinacjami liczb od 0 do 8. (to jest programowanie, i jest w C, więc nie będziemy używać od 1 do 9.) Jeśli jesteś bystry, zauważysz, że drugi indeks dolny wynosi 12, a nie 9. Jest tak, ponieważ robiąc to, pamiętając, że będziemy uważać to za „rząd”, obliczamy również trzy kolejne liczby całkowite, r[9,10,11] == 1<<a | 1<<b | 1<<cgdzie 9,10,11 odnoszą się do pierwszego, drugiego i trzeciego stosu a a, b, c są trzema liczbami obecnymi w każdym stosie dla tego rzędu.

2. Wypełnij tablicę bwszystkimi możliwymi rozwiązaniami pasma 3 rzędów. Aby zachować ten stosunkowo mały rozmiar, należy uwzględniać tylko te rozwiązania, w których górny rząd to 012 345 678. Robię to brutalną siłą, generując wszystkie możliwe środkowe rzędy i ANDing r[0][10,11,12]z r[i][10,11,12]. Każda wartość dodatnia oznacza, że ​​na tym samym kwadracie znajdują się dwie identyczne liczby, a pasmo jest nieprawidłowe. Gdy istnieje poprawna kombinacja dla pierwszych dwóch wierszy, przeszukuję trzeci (dolny) rząd tą samą techniką.

Zwymiarowałem tablicę na b [2000000] [9], ale program znajduje tylko 1306368 rozwiązań. Nie wiedziałem, ile ich było, więc zostawiłem taki wymiar tablicy. To właściwie tylko połowa możliwych rozwiązań dla pojedynczego pasma (zweryfikowane na wikipedii), ponieważ skanuję tylko trzeci rząd od bieżącej wartości w igórę. Pozostałą połowę rozwiązań można znaleźć trywialnie, wymieniając drugi i trzeci rząd.

Sposób przechowywania informacji w tablicy bjest na początku nieco mylący. zamiast używać każdej liczby całkowitej do przechowywania liczb 0..8znalezionych na danej pozycji, tutaj każda liczba całkowita uwzględnia jedną z liczb 0..8i wskazuje, w których kolumnach można ją znaleźć. zatem b[x][7]==100100001wskazuje, że do sporządzania roztworu x numer 7 znajduje się w kolumnach 0,5 i 8 (od prawej do lewej). Powodem tej reprezentacji jest to, że trzeba wygenerować resztę możliwości zespołu przez zmiany etykiet, a to reprezentacja sprawia, że ​​jest to wygodne.

Dwa powyższe kroki obejmują konfigurację i zajmują około minuty (prawdopodobnie mniej, jeśli usunę niepotrzebne dane wyjściowe. Dwa poniższe kroki to wyszukiwanie).

3 Wyszukuj losowo rozwiązania dla pierwszych dwóch pasm, które się nie kolidują (tzn. Nie mają tej samej liczby dwa razy w danej kolumnie. Wybieramy losowe rozwiązanie dla pasma 1, zakładając zawsze permutację 0, i losowe rozwiązanie dla pasma 2 z losowa permutacja. Wynik zwykle znajduje się w mniej niż 9999 próbach (wskaźnik trafień w pierwszym etapie w zakresie tysięcy) i zajmuje ułamek sekundy. Przez permutację rozumiem, że dla drugiego pasma bierzemy rozwiązanie z b [] [] gdzie pierwszy wiersz to zawsze 012 345 678 i należy go ponownie oznakować, aby możliwa była dowolna sekwencja liczb w pierwszym rzędzie.

4 Po znalezieniu trafienia w kroku 3 wyszukaj rozwiązanie dla trzeciego pasma, które nie koliduje z pozostałymi dwoma pasmami. Nie chcemy podejmować tylko jednej próby, w przeciwnym razie czas przetwarzania dla kroku 3 zostałby zmarnowany. Z drugiej strony nie chcemy wkładać w to nadmiernej ilości wysiłku.

Dla zabawy, ostatniej nocy zrobiłem to najgłupszy możliwy sposób, ale wciąż było to interesujące (ponieważ nic nie było przez wieki, a potem znalazłem dużą liczbę rozwiązań w seriach.) Całą noc zajęło uzyskanie jednego punktu danych, nawet przy małym włamaniu (!z)Zrobiłem przerwanie ostatniej kpętli, gdy tylko wiemy, że nie jest to prawidłowe rozwiązanie (co sprawia, że ​​działa prawie 9 razy szybciej). Znaleziono 1186585 rozwiązań dla pełnej siatki po przeszukaniu wszystkich 362880 ponownych oznakowań wszystkich 1306368 rozwiązań kanonicznych dla ostatniego blok, w sumie 474054819840 możliwości. To wskaźnik trafień 1 na 400000 dla drugiego etapu. Spróbuję wkrótce ponownie z losowym wyszukiwaniem zamiast skanem. Powinien dać rozsądną odpowiedź w ciągu zaledwie kilku milionów prób, co powinno zająć tylko kilka sekund.

Ogólna odpowiedź powinna wynosić (362880 * (1306368 * 2)) ^ 3 * wskaźnik trafień = 8,5E35 * wskaźnik trafień. Obliczając wstecz z liczby w pytaniu, oczekuję wskaźnika trafień 1 / 1.2E14. To, co do tej pory mam z moim pojedynczym punktem danych, to 1 / (400000 * 1000), który jest około milion razy większy. Może to być anomalia przypadku, błąd w moim programie lub błąd w matematyce. Nie będę wiedział, co to jest, dopóki nie przeprowadzę jeszcze kilku testów.

Zostawię to tutaj na wieczór. Tekst jest nieco skąpy, wkrótce go uporządkuję i mam nadzieję, że dodam więcej wyników, a może kilka słów o tym, jak przyspieszyć i rozszerzyć koncepcję do N = 4. Jednak nie sądzę, że wprowadzę zbyt wiele zmian w moim programie :-)

Ach .. program:

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