Алгоритм генерации судоку

Ваш способ, вероятно, наиболее быстрый, но я предпочитаю жесткий рандом!
Я изучаю Си и очень люблю судоку, так что написал свой генератор судоку, который можно использовать и для решения при совсем небольшой доработке. В отличии от Вашего генератора я не использую готовую матрицу, а генерирую первую строку и «решаю» остальную часть путем перебора. Конечно, мой вариант очень сильно проигрывает по производительности Вашему, зато всегда оригинальное судоку, а в варианте с перестановкой строк часто при решении замечаешь систему перестановки и судоку уже становится очень простым в решении.



P.S. Сразу хочу извиниться за качество кода, т.к. «я — не волшебник, а только учусь».

Я бы сложность конкретного экземпляра оценивал минимальной глубиной бэктрекинга (backtracking) необходимого для решения этого экземпляра. Ну и не опирался бы на то, что решение должно быть единственным. Зачем?

Я это к тому, что судоку может быть очень сложным с 30 открытыми ячейками а может быть и элементарным с тем-же количеством открытых ячеек.

Жаль, что в конечном итоге всё равно пришлось решать судоку.

Мне кажется, что хороший генератор судоку должен уметь генерировать задачи заданной сложности. Вы пишете, что критериев оценки сложности нет. Но они есть. Сложность судоку определяется методами, которые необходимо применить, чтобы решить его. Количество открытых ячеек при этом не очень важно.

В идеале нужно написать алгоритм решения судоку человеческими методами, а затем с помощью этого алгоритма оценивать сложность сгенерированного судоку. Но такая программа будет значительно сложнее.

1. Классы лучше называть с большой буквы, чтобы визуально отличать их от переменных, содержащих экземпляры классов этого типа. Т.е. sudoku_generator.Grid вместо sudoku_generator.grid.

2. Наследуйте объекты от object — в Python 2 это избавит от неожиданностей в виде ограниченного поведения old-style classes, тогда как в Python 3 классы и так наследуются от object по-умолчанию.

3. Избегайте использования прямых вызовов print(). Если требуется отладочный вывод, дайте возможность пользователю задать свой собственный print_callback в __init__-е:

	def __init__(self, n = 3, print_callback = lambda *args, **kwarg: None):
		self.__print_callback = print_callback
		...
		self.__print_callback('The base table is ready!')

4. Используйте from __future__ import print_function в целях увеличения переносимости кода. Таким образом, print() станет функцией и код будет переносим между Python 2 и Python 3.

5. Не делайте публичными те поля класса, изменение которых после создания экземпляра класса может сломать его работу. Если хотите предоставить пользователю возможность узнать значение поля после создания экземпляра, используйте свойства:

class Grid(object):
	n = property(lambda self: self.__n)
	
	def __init__(self, n = 3):
		self.__n = n

6. Не используйте обычное деление x / y там, где вам точно нужен целочисленный результат — используйте целочисленное деление x // y. from __future__ import division включит это поведение в Python 2 для облегчения перехода.

7. Пустой метод sudoku_generator.Grid.__del__ кроме бесполезности, еще и немножко вреден — в зависимости от реализации, __del__ либо затрудняет, либо делает невозможной сборку мусора. В данном случае от метода лучше избавиться.

8. Код вида for x in range(len(foo)): bar(foo[x]) как правило, можно заменить на for x in foo: bar(x).

9. В random.randrange не нужен третий аргумент, если он равен 1, и не нужен первый аргумент, если он равен 0, т.к. это значения по умолчанию. Таким образом, random.randrange(0, N, 1) равноценно random.randrange(N).

10. В Python 2 xrange более эффективен, чем range, т.к. возвращает итератор, а не список, но в Python 3 range ведет себя, как xrange, а xrange не существует. Следует заменить все вхождения range(...) на list(range(...)), а xrange(...) на range(...), и постараться использовать range (бывший xrange) везде, где не используются методы list-а.

11. В if и while необязательны скобки вокруг условий.

12. В sudoku_generator.Grid.swap_rows_small цикл по выбору line2 может длиться сколько угодно долго, плюс имеет место дублирование кода. Возможно, было бы лучше переписать функцию следующим образом?

	def swap_rows_small(self):
		r'''Swap two rows.
		
		'''
		
		# случайные разные строки в пределах района
		line1, line2 = random.sample(range(self.__n), 2)
		
		# получение случайного района
		area = random.randrange(self.__n)
		
		# строки для обмена
		N1 = area * self.__n + line1
		N2 = area * self.__n + line2
		
		self.__table[N1], self.__table[N2] = self.__table[N2], self.__table[N1]

13. То же относится к sudoku_generator.Grid.swap_rows_area:

	def swap_rows_area(self):
		r'''Swap two area horizon.
		
		'''
		
		# случайные разные районы
		area1, area2 = random.sample(range(self.__n), 2)
		
		for i in range(self.__n):
			N1, N2 = area1 * self.__n + i, area2 * self.__n + i
			self.__table[N1], self.__table[N2] = self.__table[N2], self.__table[N1]

14. Вместо косвенного вызова вида Grid.foo(self) лучше использовать прямой вызов self.foo().

15. Метод sudoku_generator.Grid.mix использует eval — это не очень хорошая идея, т.к. каждый вызов заново дергает компилятор со всей обвязкой. Вообще eval, compile и exec в прикладных задачах нужны, как правило, крайне редко. Функцию можно переписать следующим образом:

	def mix(self, amt = 10):
		mix_func = (
			self.transposing,
			self.swap_rows_small,
			self.swap_colums_small,
			self.swap_rows_area,
			self.swap_colums_area,
		)
		
		for i in range(amt):
			random.choice(mix_func)()

16. В функции выше я также заменил выбор элемента по случайному индексу array[random.randrange(len(array))] на прямой выбор элемента random.choice(array) — меньше промежуточных шагов и понятнее решение.

17. В функции выше неправильно использован range — при отсчете от 1 количество раз, которые была применена трансформация, будет на 1 меньше. Т.е. при amt = 1 вообще ничего не произойдет.

18. Старайтесь использовать tuple ((a, b, c)) вместо list ([a, b, c]) в статических структурах — там, где не потребуется последующая модификация. Это позволит компилятору уменьшить объем памяти, потребляемой структурой, и создавать ее единожды вместо пересоздания при каждом вызове mix()

19. Для создания повторяющихся строк можно использовать умножение — "-" * 10 == "----------", а "-*=" * 3 == "-*=-*=-*=".

20. Код в конце модуля sudoku_generator лучше было бы сделать частью класса sudoku_generator.Grid.

21. Именовать методы, как и описывать docstring-и лучше в present indefinite — def transpose(self): '''Transpose grid''' вместо def transposing(self): '''Transposing grid''', таким образом, вызовы методов звучат, как действия.

22. Код модуля solver, похоже, принадлежит перу другого автора :) К нему претензий нет, написан очень хорошо.

Наверное и не лучший вариант, но внятный, законченный и простой. Визуализация хорошая.

А как строят судоку существующие компьютерные программы вы не разбирали? Таким же способом?

Так и просится рандомный маппинг (неважно, перед перемешиванием, или после него).
То есть, как один из этапов — заменяем одни цифры на другие случайным образом. Естественно, с однозначным соответствием.

Когда-то использовал именно этот алгоритм. Когда искал алгоритмы, из вменяемых нашел только этот.

<оффтоп>
В прошлом году финский математик (Арто Инкала) создал самую сложную судоку.
Вот она:


з.ы. если хабрасторидж глючит с вставляевыми картинками, вот прямая ссылка
img.gawkerassets.com/img/18wd1m6020o3tpng/original.png

Как профессиональный решатель и автор разных головоломок могу сказать, что «хэнд-мэйд» задачи всегда лучше, чем автоматически сгенерированные. Хотя и среди автоматически сгенерированных изредка попадаются интересные экземпляры. Посему в соревнованиях по решению головоломок очень редко используются «автосгенеренные» задачи (а если кто-то из организаторов использует, то обычно получает немалую долю крититки от участников).
А вот для тренировочных целей генерация позволяет получить некий материал (я и сам имею пару сотен программ-генераторов) — решение таких задач позволяет приспособиться к задаче и «почуствовать» ее закономерности.

Кстати, если интересно и вы об этом еще не знаете — посмотрите на судоку от Gnome Games. Раньше она была на Питоне написана. Не знаю, правда, как сейчас. Вот там и есть генерация судоку (в заднем фоне) различных степеней сложности.

Генерируемые сетки получаются донельзя простыми, т.к. цифры перемещаются группами по три. Решать такие будет неинтересно.