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