Это не решатель судоку и не проверка судоку.

Ваша задача состоит в том, чтобы написать функцию или сценарий, который, учитывая в качестве входных данных размер блока «2D» головоломки Судоку (3 для классической доски 9x9 , 4 для доски 16x16 и т. Д.), Будет вычислять приблизительное число различных головоломок (решений), которые существуют для этого размера.

Например, с учетом ввода 3 ваша программа должна напечатать с требуемой точностью приблизительное число 6 670 903 752 021 072 936 960, которое является известным числом различных головоломок 9х9 Судоку , или 5 472 730 538 с учетом различных симметрий. Ваше решение должно указывать, учитываются ли симметрии или игнорируются.

«Требуемая точность» остается неопределенной: ваша программа может работать в течение определенного времени, а затем выводить свой результат или вычислять его до заданного числа значащих цифр, или даже работать вечно, печатая все более и более приближенные значения. Дело в том, что должна быть возможность заставить его вычислять результат с любой необходимой точностью за конечное время. (Таким образом, «42» не является приемлемым ответом.) Допускается ограничение точности вашего результата доступными числами с плавающей запятой машины.

Нет доступа к онлайн-ресурсам, нет сохранения исходного кода в имени файла и т. Д.

PS: я знаю, что это трудная проблема (если я не ошибаюсь, если вы не ошиблись), этот вопрос требует только приблизительного статистического решения. Например, вы можете попробовать случайные конфигурации, которые удовлетворяют одному (или лучше двум) ограничениям, вычислить, сколько из них существует, а затем проверить, как часто вы получаете головоломку, которая удовлетворяет всем трем ограничениям. Это будет работать в приличное время для небольших размеров (конечно, для размера = 3 и, возможно, 4), но алгоритм должен быть достаточно универсальным, чтобы работать для любого размера.

Лучший алгоритм побеждает.

PS2: я перешел с кода-гольфа на код-вызов, чтобы лучше отражать сложность проблемы и поощрять более разумные решения, а не тупые, но хорошо сыгранные в гольф. Но поскольку, по-видимому, «лучший алгоритм» неясен, позвольте мне попытаться определить его правильно.

Учитывая достаточное количество времени и игнорируя постоянные факторы (в том числе процессор и скорость интерпретатора) или, что то же самое, учитывая их асимптотическое поведение, какое решение приведет к точному результату быстрее всего?

C ++

Здесь я приведу алгоритм, иллюстрированный примером для случая 3x3. Теоретически его можно распространить на случай NxN, но для этого потребуется гораздо более мощный компьютер и / или некоторые хитрые настройки. Я упомяну некоторые улучшения по мере прохождения.

Прежде чем идти дальше, давайте отметим симметрии сетки Судоку, то есть преобразования, которые приводят к другой сетке тривиальным образом. Для размера блока 3 симметрии следующие:

Горизонтальная симметрия

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

Вертикальная симметрия

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

Обратите внимание, что горизонтальные и вертикальные отражения сетки могут быть достигнуты с помощью их комбинации, поэтому их не нужно считать. Существует еще одна пространственная симметрия, которая должна быть рассмотрена, это транспонирование, которое является фактором 2. Это дает общую пространственную симметрию

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

Тогда есть другая, очень важная симметрия, называемая релабелингом.

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

Общее количество решений не может быть найдено просто путем умножения числа уникальных по симметрии решений на это число, поскольку существует число (менее 1%) автоморфных решений. Это означает, что для этих специальных решений существует операция симметрии, которая отображает их на себя, или множественные операции симметрии, которые сопоставляют их с тем же другим решением.

Чтобы оценить количество решений, я подхожу к проблеме в 4 этапа:

1. Заполните массив r[362880][12]всеми возможными перестановками чисел от 0 до 8. (Это программирование, и это в C, поэтому мы не будем использовать от 1 до 9.) Если вы проницательны, вы заметите, что второй индекс 12, а не 9. Это потому, что, делая это, имея в виду, что мы будем считать это «строкой», мы также вычисляем еще три целых числа, r[9,10,11] == 1<<a | 1<<b | 1<<cгде 9,10,11 относятся к первому, второму и третьему стеку. и a, b, c - три числа, присутствующие в каждом стеке для этой строки.

2. Заполните массив bвсеми возможными решениями группы из 3 строк. Чтобы сохранить это достаточно маленьким, включайте только те решения, в которых верхний ряд равен 012 345 678. Я делаю это с помощью грубой силы, генерируя все возможные средние строки и Андинг r[0][10,11,12]с r[i][10,11,12]. Любое положительное значение означает, что в одном квадрате два одинаковых числа, а полоса неверна. Когда есть правильная комбинация для первых двух строк, я ищу 3-ю (нижнюю) строку тем же методом.

Я измерил массив как b [2000000] [9], но программа находит только 1306368 решений. Я не знал, сколько их было, поэтому я оставил размер массива таким образом. На самом деле это только половина возможных решений для одной полосы (проверено в википедии), потому что я сканирую только 3-ю строку от текущего значения iвверх. Оставшуюся половину решений можно найти тривиально, поменяв 2-й и 3-й ряды.

То, как информация хранится в массиве, bпоначалу немного сбивает с толку. вместо использования каждого целого числа для хранения чисел, 0..8найденных в данной позиции, здесь каждое целое число рассматривает одно из чисел 0..8и указывает, в каких столбцах оно может быть найдено. таким образом b[x][7]==100100001, указывало бы, что для решения x число 7 находится в столбцах 0,5 и 8 (справа налево). Причина этого представления состоит в том, что нам нужно генерировать оставшиеся возможности для полосы путем перемаркировки, и это Представление делает это удобным.

Два вышеупомянутых шага составляют настройку и занимают около минуты (возможно, меньше, если я удалил ненужные выходные данные. Два шага ниже - это фактический поиск.)

3 Произведите случайный поиск решений для первых двух полос, которые не конфликтуют (т.е. не имеют одно и то же число дважды в данном столбце. Мы выбираем случайное решение для полосы 1, предполагая, что всегда перестановка 0, и случайное решение для полосы 2 с случайная перестановка. Результат обычно находится менее чем в 9999 попытках (частота попаданий на первой стадии в диапазоне тысяч) и занимает доли секунды. Под перестановкой я подразумеваю, что для второй полосы мы берем решение из b [] [] где первая строка всегда 012,345,678 и пометить ее так, чтобы возможна любая возможная последовательность чисел в первой строке.

4 Если на шаге 3 найдено попадание, найдите решение для третьей полосы, которая не конфликтует с двумя другими. Мы не хотим делать только одну попытку, иначе время обработки для шага 3 будет потрачено впустую. С другой стороны, мы не хотим вкладывать в это чрезмерное количество усилий.

Просто для забавы, прошлой ночью я сделал это самым глупым из возможных способов, но он все еще был интересным (потому что ничего не стоило, а затем нашел большое количество решений в пакетах). Потребовалась вся ночь, чтобы получить одно назначение данных, даже с небольшим взломом (!z)Я сделал, чтобы прервать последний kцикл, как только мы узнаем, что это недопустимое решение (что делает его работающим почти в 9 раз быстрее). Он нашел 1186585 решений для полной сетки после поиска всех 362880 релейных разрядов всех 1306368 канонических решений для последнего блок, всего 474054819840 возможностей. Это показатель успеха 1 на 400000 для второго этапа. Я скоро попробую снова со случайным поиском, а не сканированием. Он должен дать разумный ответ всего за несколько миллионов попыток, что должно занять всего несколько секунд.

Общий ответ должен быть (362880 * (1306368 * 2)) ^ 3 * коэффициент попадания = 8.5E35 * коэффициент попадания. Возвращаясь к подсчету числа, о котором идет речь, я ожидаю, что показатель попаданий составит 1 / 1.2E14. То, что я до сих пор получил с моей единственной точкой данных, это 1 / (400000 * 1000), что примерно в миллион раз меньше. Это может быть случайная аномалия, ошибка в моей программе или ошибка в моей математике. Я не буду знать, что это такое, пока не проведу еще несколько тестов.

Я оставлю это здесь на сегодня. Текст немного неаккуратный, я скоро приведу его в порядок и, надеюсь, добавлю еще несколько результатов и, возможно, несколько слов о том, как сделать это быстрее и как расширить концепцию до N = 4. Я не думаю, что внесу в свою программу слишком много изменений :-)

Ах .. программа:

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