Генератор случайных судоку

13

Я хочу создать совершенно случайную судоку .

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

Как я могу создать случайную головоломку судоку, чтобы все головоломки судоку были равновероятными?

Джастин
источник
Это выглядит как жизнеспособное решение: dryicons.com/blog/2009/08/14/…
Джо
1
Теперь есть мета вопрос по этому поводу. Пожалуйста, обсудите там или в чате.
Кевин

Ответы:

15

Генерация точного равномерного распределения всех головоломок судоку может быть выполнена следующим образом: вы можете просто случайным образом сгенерировать сетку 9x9, а затем сохранить ее, только если это правильная сетка судоку, в противном случае повторите попытку.

Такой подход грубой силы гарантирует вам равномерное распределение, но он явно не эффективен, поскольку вы можете умножить вероятность того, что сетка будет правильной, на только генерируя случайную сетку 8x8 и затем заполняя оставшиеся две строки. Это все еще случайное распределение, но все еще слишком неэффективное.917

Вы также можете заставить первую строку быть , затем случайным образом генерировать оставшуюся часть сетки и затем случайным образом выбрать перестановку всех цифр. Вы все равно выберете все сетки с той же вероятностью, но 9 ! Быстрее.[1,2,,,9]9!

Возможно, вы понимаете, куда я иду: умный ответ на эту проблему, вероятно, заставит вас задуматься о лежащей в основе симметрии сеток судоку. В этом направлении была проделана большая работа, чтобы доказать тот факт, что 17 - это минимальное количество ключей к судоку ( см. Эту статью ), и вы можете перейти здесь, чтобы увидеть точное перечисление 5 472 730 538 классов из 3 359 232 похожих сеток, в которых используются эти симметрий:

  1. Перестановки цифр
  2. Перестановки строк (полосы и строки внутри каждой полосы)
  3. То же самое для столбцов
  4. перестановка

С помощью этого фреймворка вы можете случайным образом выбрать один из 5 472 730 538 классов (их можно сжать до 6 ГБ), а затем выбрать одного представителя для каждой симметрии, соответственно один из .9!,64,64,2

РЕДАКТИРОВАТЬ: чтобы адаптировать это к неполным головоломкам, вы можете случайно выбрать подмножество вашей сетки, проверить, является ли решение уникальным с помощью решателя судоку, и повторите попытку, если нет. Это не является равномерным распределением, поскольку число неполных головоломок с уникальным решением может быть различным для двух сеток. (В противном случае я был бы очень удивлен)

jmad
источник
Но Джастин просит создать неполную головоломку так, чтобы у нее был уникальный способ ее завершения. Даже если вы сгенерируете сетку 9x9, удовлетворяющую ограничениям Судоку, непонятно, почему удаление определенного подмножества ячеек даст вам головоломку, которую можно решить уникальным способом.
Яном
1
@Janoma: о, плохо, я буду редактировать. Но это не очень важно, если не определить, что такое правильная головоломка. (Сетка только с одной пустой ячейкой - головоломка?). Нужна ли нам минимальная сетка (т.е. если вы удалите цифру, решение больше не будет уникальным?) Это интересный вопрос.
jmad
«Некоторые элементы могут быть опущены» достаточно точно (т.е. «один или несколько» элементов могут быть удалены). Например, допустимая головоломка с одной пустой ячейкой может быть завершена уникальным способом, а пустая головоломка не может, поскольку существует более одной действительной головоломки. Кроме того, законченная действительная головоломка может быть завершена уникальным (тривиальным, пустым) способом. Вопрос о минимальной сетке тоже интересен, но отличается от этого.
Janoma
@Janoma, jmad: допустимая головоломка обычно минимальна, я забыл упомянуть об этом.
Жиль "ТАК - перестань быть злым"
@ Жиль Это определение? Интересно, действительно ли это подразумевается под ФП. Это делает проблему намного сложнее :-)
Janoma