Ini bukan pemecah Sudoku, atau pemeriksa Sudoku.

Tantangan Anda adalah menulis fungsi atau skrip yang, diberikan sebagai input ukuran "blok" dari teka-teki Sudoku 2D (yaitu 3 untuk papan 9x9 klasik , 4 untuk papan 16x16 , dll.) Akan menghitung perkiraan angka teka-teki berbeda (solusi) yang ada untuk ukuran itu.

Misalnya, diberi input 3, program Anda harus mencetak perkiraan, dengan ketepatan yang diinginkan, dari angka 6.670.903.752.021.072.936.960 yang merupakan jumlah yang diketahui dari teka-teki 9x9 Sudoku yang berbeda , atau 5.472.730.538 ketika memperhitungkan berbagai simetri. Solusi Anda harus menyatakan apakah simetri dihitung atau diabaikan.

"Presisi yang diinginkan" dibiarkan tidak terdefinisi: program Anda mungkin berjalan untuk waktu tertentu dan kemudian mengeluarkan hasilnya, atau menghitungnya hingga sejumlah digit signifikan, atau bahkan berjalan selamanya, mencetak perkiraan yang lebih baik dan lebih baik. Intinya adalah bahwa ia harus memungkinkan untuk menghitung hasilnya dengan presisi yang diperlukan, dalam waktu yang terbatas. (Jadi "42" bukan jawaban yang bisa diterima.) Membatasi ketepatan hasil Anda dengan mengapung mesin yang tersedia dapat diterima.

Tidak mengakses sumber daya online, tidak menyimpan kode sumber dalam nama file, dll.

PS: Saya tahu ini Masalah Sulit (NP-lengkap kalau saya tidak salah.) Tetapi pertanyaan ini hanya menanyakan perkiraan, solusi statistik. Misalnya Anda dapat mencoba konfigurasi acak yang memenuhi satu (atau lebih baik dua) kendala, hitung berapa banyak yang ada dan kemudian periksa seberapa sering Anda mendapatkan puzzle yang memenuhi ketiga kendala. Ini akan bekerja dalam waktu yang layak untuk ukuran kecil (tentu saja untuk ukuran = 3 dan mungkin 4) tetapi algoritma harus cukup umum untuk bekerja untuk ukuran apa pun.

Algoritma terbaik menang.

PS2: Saya berubah dari kode-golf ke kode-tantangan untuk lebih mencerminkan kesulitan dari masalah dan mendorong solusi yang lebih pintar, lebih bodoh daripada yang golf dengan baik. Tetapi karena tampaknya "algoritma terbaik" tidak jelas, izinkan saya mencoba mendefinisikannya dengan benar.

Diberi cukup waktu dan mengabaikan faktor-faktor konstan (termasuk CPU dan kecepatan intepreter), atau yang setara, dengan mempertimbangkan perilaku asimptotisnya, solusi mana yang akan konvergen ke hasil yang tepat paling cepat?

C ++

Apa yang akan saya sajikan di sini adalah algoritma, diilustrasikan dengan contoh untuk kasus 3x3. Secara teoritis dapat diperluas ke kasus NxN, tetapi itu akan membutuhkan komputer yang jauh lebih kuat dan / atau beberapa penyesuaian cerdas. Saya akan menyebutkan beberapa peningkatan saat saya melewati.

Sebelum melangkah lebih jauh, mari kita perhatikan simetri kisi Sudoku, yaitu transformasi yang mengarah ke kisi lain dengan cara yang sepele. Untuk ukuran blok 3, simetri adalah sebagai berikut:

Simetri horisontal

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

Simetri vertikal

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

Perhatikan bahwa refleksi horizontal dan vertikal dari grid dapat dicapai dengan kombinasi ini, sehingga mereka tidak perlu dihitung. Ada satu lagi simetri spasial yang perlu dipertimbangkan, yaitu transposing, yang merupakan faktor 2. Ini memberikan total simetri spasial dari

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

Lalu ada simetri lain yang sangat penting, yang disebut relabelling.

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

Jumlah total solusi tidak dapat ditemukan hanya dengan mengalikan jumlah solusi unik simetri dengan nomor ini, karena ada sejumlah (kurang dari 1%) solusi automorfik. Itu berarti bahwa untuk solusi khusus ini ada operasi simetri yang memetakannya sendiri, atau operasi simetri ganda yang memetakannya ke solusi lain yang sama.

Untuk memperkirakan jumlah solusi, saya mendekati masalah dalam 4 langkah:

1. Isi sebuah array r[362880][12]dengan semua kemungkinan permutasi dari angka 0 hingga 8. (ini adalah pemrograman, dan ini dalam C, jadi kita tidak akan menggunakan 1 hingga 9.) Jika Anda lihai, Anda akan melihat bahwa subscript kedua adalah 12 bukan 9. Ini karena, saat melakukan ini, mengingat bahwa kami akan menganggap ini sebagai "baris" kami juga menghitung tiga bilangan bulat lainnya di r[9,10,11] == 1<<a | 1<<b | 1<<cmana 9,10,11 merujuk pada tumpukan pertama, kedua dan ketiga dan a, b, c adalah tiga angka yang ada di setiap tumpukan untuk baris itu.

2. Isi sebuah array bdengan semua solusi yang memungkinkan dari pita 3 baris. Untuk menjaga ini cukup kecil, hanya sertakan solusi tersebut di mana baris teratas adalah 012.345.678. Saya melakukan ini dengan kekerasan, dengan menghasilkan semua kemungkinan baris tengah dan AND r[0][10,11,12]dengan r[i][10,11,12]. Nilai positif apa pun berarti ada dua angka identik dalam kotak yang sama dan pita tidak valid. Ketika ada kombinasi yang valid untuk dua baris pertama, saya mencari baris ke-3 (bawah) dengan teknik yang sama.

Saya mengukur array sebagai b [2000000] [9] tetapi program ini hanya menemukan 1306368 solusi. Saya tidak tahu ada berapa, jadi saya meninggalkan dimensi array seperti itu. Ini sebenarnya hanya setengah dari solusi yang mungkin untuk satu band (diverifikasi di wikipedia), karena saya hanya memindai baris ke-3 dari nilai saat ini untuk ike atas. Separuh sisanya dari solusi dapat ditemukan sepele dengan menukar baris 2 dan 3.

Cara informasi disimpan dalam array bagak membingungkan pada awalnya. alih-alih menggunakan setiap bilangan bulat untuk menyimpan angka yang 0..8ditemukan di posisi tertentu, di sini setiap bilangan bulat mempertimbangkan salah satu angka 0..8dan menunjukkan di mana kolom itu dapat ditemukan. dengan demikian b[x][7]==100100001akan menunjukkan bahwa untuk solusi x angka 7 ditemukan dalam kolom 0,5 dan 8 (dari kanan ke kiri.) Alasan untuk representasi ini adalah bahwa kita perlu menghasilkan sisa kemungkinan untuk band dengan relabelling, dan ini representasi memudahkan untuk melakukan ini.

Dua langkah di atas terdiri dari pengaturan dan membutuhkan waktu sekitar satu menit (mungkin lebih sedikit jika saya menghapus output data yang tidak perlu. Dua langkah di bawah adalah pencarian yang sebenarnya.)

3 Cari secara acak untuk solusi untuk dua band pertama yang tidak berbenturan (yaitu tidak memiliki nomor yang sama dua kali dalam kolom tertentu. Kami memilih solusi acak untuk band 1, dengan asumsi selalu permutasi 0, dan solusi acak untuk band 2 dengan permutasi acak. Hasilnya biasanya ditemukan dalam kurang dari 9999 percobaan (tingkat hit tahap pertama dalam rentang ribuan) dan mengambil sepersekian detik. Dengan permutasi, maksud saya untuk pita kedua kami mengambil solusi dari b [] [] di mana baris pertama selalu 012.345.678 dan memberi label ulang sehingga urutan angka yang mungkin pada baris pertama adalah mungkin.

4 Ketika hit ditemukan pada langkah 3, cari solusi untuk band ketiga yang tidak berbenturan dengan dua lainnya. Kami tidak ingin melakukan satu percobaan saja, jika tidak, waktu pemrosesan untuk langkah 3 akan sia-sia. Di sisi lain, kita tidak ingin melakukan upaya yang berlebihan.

Hanya untuk bersenang-senang, tadi malam aku melakukannya dengan cara terbodoh mungkin, tapi itu tetap menarik (karena tidak ada artinya selama berabad-abad, kemudian menemukan sejumlah besar solusi dalam semburan). Butuh sepanjang malam untuk mendapatkan satu titik data, bahkan dengan sedikit hack (!z)Saya melakukan untuk membatalkan kloop terakhir segera setelah kami tahu ini bukan solusi yang valid (yang membuatnya berjalan hampir 9 kali lebih cepat.) Ia menemukan solusi 1186585 untuk grid lengkap setelah mencari semua 362880 relabellings dari semua 1306368 solusi kanonik untuk yang terakhir blok, total 474054819840 kemungkinan. Itu adalah hit rate 1 dalam 400000 untuk tahap kedua. Saya akan mencoba lagi segera dengan pencarian acak daripada pemindaian. Itu harus memberikan jawaban yang masuk akal hanya dalam beberapa juta percobaan, yang seharusnya hanya memakan waktu beberapa detik.

Jawaban keseluruhan harus (362880 * (1306368 * 2)) ^ 3 * hit rate = 8.5E35 * hit rate. Dengan kembali menghitung dari angka dalam pertanyaan, saya mengharapkan hit rate 1 / 1.2E14. Apa yang saya dapatkan sejauh ini dengan satu titik data saya adalah 1 / (400000 * 1000) yang keluar dengan faktor sekitar satu juta. Ini bisa menjadi anomali peluang, kesalahan dalam program saya, atau kesalahan dalam matematika saya. Saya tidak akan tahu yang mana sampai saya menjalankan beberapa tes lagi.

Saya akan meninggalkan ini di sini untuk malam ini. Teksnya agak acak-acakan, saya akan segera membereskannya dan mudah-mudahan menambahkan beberapa hasil lagi, dan mungkin beberapa kata tentang cara membuatnya lebih cepat dan bagaimana memperluas konsep ke N = 4. Saya tidak berpikir saya akan membuat terlalu banyak perubahan pada program saya, meskipun :-)

Ah .. programnya:

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