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

    sudoku250title
    Доброго времени суток!

    Думаю, головоломка Судоку не нуждается в представлении. Многие из нас проводят за её решением достаточно много времени. Например, когда нужно убить время в дороге или просто поворочать мозги, чтобы не сохли. На хабре есть довольно много постов о решении головоломки. Но когда человек решает с десяток, а может и сотню головоломок, то найдётся пытливый ум, который задаст себе вопрос «А как же получается таблица Судоку, имеющая единственное решение? И как можно описать алгоритм для сетки 9x9?».

    Приведённый алгоритм является вполне логичным. Но моей задачей было описание и реализация. Обо всём этом написано под катом.

    Основные правила Судоку
    1. Цифра может появиться только один раз в каждой строчке
    2. Цифра может появиться только один раз в каждом столбике
    3. Цифра может появиться только один раз в каждом районе (Район — меньший квадрат со стороной 3х3, на изображении ниже выделен фиолетовым цветом)




    Шаг 1. Взять за основу базовую сетку


    Сетка должна подчинятся правилам Судоку. Размещаем в первую строку 1 2… 8 9, в строках ниже смещаем на 3 позиции влево, т.е. 4 5… 2 3 и 7 8… 5 6.
    Далее переходя в следующий район по вертикали смещаем на 1 позицию влево предыдущий район.

    В итоге должна получиться вот такая сетка, её я и назову базовой:


    Для реализации создадим класс grid. Заполним его в соответствии с Шагом 1, в котором table — список значений таблицы, метод show — просто наглядный вывод таблицы.

    class grid:
    	def __init__(self,n = 3):
    		"""Generation of the base table"""
    		self.n = n
    		self.table = [[((i*n + i/n + j) % (n*n) + 1) for j in range(n*n)] for i in range(n*n)]
    		print "The base table is ready!"
    
    	def __del__(self):
    		pass
    	
    	def show(self):
    		for i in range(self.n*self.n):
    			print self.table[i]
    

    Шаг 2. Перетасовать сетку


    Есть несколько видов перестановок, выполнив которые таблица Судоку останется в допустимом состоянии.
    К ним относятся:

    • Транспонирование всей таблицы — столбцы становятся строками и наоборот (transposing)



    • Обмен двух строк в пределах одного района (swap_rows_small)
    • Обмен двух столбцов в пределах одного района (swap_colums_small)



    • Обмен двух районов по горизонтали (swap_rows_area)
    • Обмен двух районов по вертикали (swap_colums_area)



    Для каждой из перестановок напишем метод:
    transposing

    	def transposing(self):
    		""" Transposing the whole grid """
    		self.table = map(list, zip(*self.table))
    

    swap_rows_small

    	def swap_rows_small(self):
    		""" Swap the two rows """
    		area = random.randrange(0,self.n,1)
    		line1 = random.randrange(0,self.n,1)
    		#получение случайного района и случайной строки
    		N1 = area*self.n + line1
    		#номер 1 строки для обмена
    
    		line2 = random.randrange(0,self.n,1)
    		while (line1 == line2):
    			line2 = random.randrange(0,self.n,1)
    
    		N2 = area*self.n + line2
    		#номер 2 строки для обмена
    
    		self.table[N1],self.table[N2] = self.table[N2], self.table[N1]
    

    swap_colums_small

    Для обмена столбцов можно поменять строки у транспонированной таблицы:
    	def swap_colums_small(self):
    		grid.transposing(self)
    		grid.swap_rows_small(self)
    		grid.transposing(self)
    

    swap_rows_area

    	def swap_rows_area(self):
    		""" Swap the two area horizon """
    		area1 = random.randrange(0,self.n,1)
    		#получение случайного района
    
    		area2 = random.randrange(0,self.n,1)
    		while (area1 == area2):
    			area2 = random.randrange(0,self.n,1)
    
    		for i in range(0, self.n):
    			N1, N2 = area1*self.n + i, area2*self.n + i
    			self.table[N1], self.table[N2] = self.table[N2], self.table[N1]
    

    swap_colums_area

    	def swap_colums_small(self):
    		grid.transposing(self)
    		grid.swap_rows_area(self)
    		grid.transposing(self)
    

    Может быть есть ещё более сложные преобразования, но, думаю, можно ограничиться этими. Этот каркас инвариантен своей структуре, такие перестановки есть почти тоже самое, что и действия над матрицами относительно определителя или вращение Кубика Рубика.

    Теперь, для того чтобы получить случайную комбинацию, достаточно запустить в случайном порядке функции перемешивания. Так и поступим, amt — количество перемешиваний:
    	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 xrange(1, amt):
    			id_func = random.randrange(0,len(mix_func),1)
    			eval(mix_func[id_func])
    

    Пример 10 итераций перемешивания
    base
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    [4, 5, 6, 7, 8, 9, 1, 2, 3]
    [7, 8, 9, 1, 2, 3, 4, 5, 6]
    [2, 3, 4, 5, 6, 7, 8, 9, 1]
    [5, 6, 7, 8, 9, 1, 2, 3, 4]
    [8, 9, 1, 2, 3, 4, 5, 6, 7]
    [3, 4, 5, 6, 7, 8, 9, 1, 2]
    [6, 7, 8, 9, 1, 2, 3, 4, 5]
    [9, 1, 2, 3, 4, 5, 6, 7, 8]
    
    swap_colums_area
    [7, 8, 9, 4, 5, 6, 1, 2, 3]
    [1, 2, 3, 7, 8, 9, 4, 5, 6]
    [4, 5, 6, 1, 2, 3, 7, 8, 9]
    [8, 9, 1, 5, 6, 7, 2, 3, 4]
    [2, 3, 4, 8, 9, 1, 5, 6, 7]
    [5, 6, 7, 2, 3, 4, 8, 9, 1]
    [9, 1, 2, 6, 7, 8, 3, 4, 5]
    [3, 4, 5, 9, 1, 2, 6, 7, 8]
    [6, 7, 8, 3, 4, 5, 9, 1, 2]
    
    swap_colums_small
    [7, 8, 9, 4, 5, 6, 2, 1, 3]
    [1, 2, 3, 7, 8, 9, 5, 4, 6]
    [4, 5, 6, 1, 2, 3, 8, 7, 9]
    [8, 9, 1, 5, 6, 7, 3, 2, 4]
    [2, 3, 4, 8, 9, 1, 6, 5, 7]
    [5, 6, 7, 2, 3, 4, 9, 8, 1]
    [9, 1, 2, 6, 7, 8, 4, 3, 5]
    [3, 4, 5, 9, 1, 2, 7, 6, 8]
    [6, 7, 8, 3, 4, 5, 1, 9, 2]
    
    swap_colums_small
    [7, 8, 9, 4, 5, 6, 1, 2, 3]
    [1, 2, 3, 7, 8, 9, 4, 5, 6]
    [4, 5, 6, 1, 2, 3, 7, 8, 9]
    [8, 9, 1, 5, 6, 7, 2, 3, 4]
    [2, 3, 4, 8, 9, 1, 5, 6, 7]
    [5, 6, 7, 2, 3, 4, 8, 9, 1]
    [9, 1, 2, 6, 7, 8, 3, 4, 5]
    [3, 4, 5, 9, 1, 2, 6, 7, 8]
    [6, 7, 8, 3, 4, 5, 9, 1, 2]
    
    transposing
    [7, 1, 4, 8, 2, 5, 9, 3, 6]
    [8, 2, 5, 9, 3, 6, 1, 4, 7]
    [9, 3, 6, 1, 4, 7, 2, 5, 8]
    [4, 7, 1, 5, 8, 2, 6, 9, 3]
    [5, 8, 2, 6, 9, 3, 7, 1, 4]
    [6, 9, 3, 7, 1, 4, 8, 2, 5]
    [1, 4, 7, 2, 5, 8, 3, 6, 9]
    [2, 5, 8, 3, 6, 9, 4, 7, 1]
    [3, 6, 9, 4, 7, 1, 5, 8, 2]
    
    swap_colums_small
    [7, 1, 4, 8, 2, 5, 6, 3, 9]
    [8, 2, 5, 9, 3, 6, 7, 4, 1]
    [9, 3, 6, 1, 4, 7, 8, 5, 2]
    [4, 7, 1, 5, 8, 2, 3, 9, 6]
    [5, 8, 2, 6, 9, 3, 4, 1, 7]
    [6, 9, 3, 7, 1, 4, 5, 2, 8]
    [1, 4, 7, 2, 5, 8, 9, 6, 3]
    [2, 5, 8, 3, 6, 9, 1, 7, 4]
    [3, 6, 9, 4, 7, 1, 2, 8, 5]
    
    swap_rows_small
    [7, 1, 4, 8, 2, 5, 6, 3, 9]
    [8, 2, 5, 9, 3, 6, 7, 4, 1]
    [9, 3, 6, 1, 4, 7, 8, 5, 2]
    [5, 8, 2, 6, 9, 3, 4, 1, 7]
    [4, 7, 1, 5, 8, 2, 3, 9, 6]
    [6, 9, 3, 7, 1, 4, 5, 2, 8]
    [1, 4, 7, 2, 5, 8, 9, 6, 3]
    [2, 5, 8, 3, 6, 9, 1, 7, 4]
    [3, 6, 9, 4, 7, 1, 2, 8, 5]
    
    swap_rows_small
    [7, 1, 4, 8, 2, 5, 6, 3, 9]
    [8, 2, 5, 9, 3, 6, 7, 4, 1]
    [9, 3, 6, 1, 4, 7, 8, 5, 2]
    [5, 8, 2, 6, 9, 3, 4, 1, 7]
    [4, 7, 1, 5, 8, 2, 3, 9, 6]
    [6, 9, 3, 7, 1, 4, 5, 2, 8]
    [2, 5, 8, 3, 6, 9, 1, 7, 4]
    [1, 4, 7, 2, 5, 8, 9, 6, 3]
    [3, 6, 9, 4, 7, 1, 2, 8, 5]
    
    swap_rows_area
    [7, 1, 4, 8, 2, 5, 6, 3, 9]
    [8, 2, 5, 9, 3, 6, 7, 4, 1]
    [9, 3, 6, 1, 4, 7, 8, 5, 2]
    [2, 5, 8, 3, 6, 9, 1, 7, 4]
    [1, 4, 7, 2, 5, 8, 9, 6, 3]
    [3, 6, 9, 4, 7, 1, 2, 8, 5]
    [5, 8, 2, 6, 9, 3, 4, 1, 7]
    [4, 7, 1, 5, 8, 2, 3, 9, 6]
    [6, 9, 3, 7, 1, 4, 5, 2, 8]
    
    swap_colums_small
    [7, 1, 4, 8, 2, 5, 6, 9, 3]
    [8, 2, 5, 9, 3, 6, 7, 1, 4]
    [9, 3, 6, 1, 4, 7, 8, 2, 5]
    [2, 5, 8, 3, 6, 9, 1, 4, 7]
    [1, 4, 7, 2, 5, 8, 9, 3, 6]
    [3, 6, 9, 4, 7, 1, 2, 5, 8]
    [5, 8, 2, 6, 9, 3, 4, 7, 1]
    [4, 7, 1, 5, 8, 2, 3, 6, 9]
    [6, 9, 3, 7, 1, 4, 5, 8, 2]
    


    Шаг 3. Удаление клеток


    После полученного решения нам необходимо получить задачу (именно в такой последовательности мы можем гарантировать однозначность решения). И это самая сложная часть. Какое количество можно убрать, чтобы гарантировать однозначность решения? Это один из важных факторов, от которого зависит сложность Судоку. Всего в Судоку 81 клетка, обычно считают лёгким когда на поле есть 30-35 «подсказок», средним — 25-30, и сложным — 20-25. Это данные большого набора реальных примеров. Нет никаких законов для сложности. Можно сделать 30-клеточный неразрешимый вариант и 22 клеточный «лёгкий».

    • Случайный подход — можно попробовать выкинуть 50-60 клеток наугад, но где вероятность что Судоку можно будет решить? Например, если заполнены 3 строки ( = 27 клеток)
    • Случайно с простым ограничением — для примера можно взять некое число N в качестве предела, так что N строк и столбцов могут быть пустыми. Принимая N = 0 — для лёгких уровней, N=1 — средний, N=2 — сложный

    Итак, приступим к вычёркиванию ячеек (все варианты равнозначны, поэтому у нас 81 ячейка, которую можно вычеркнуть, поэтому проверим все перебором):

    1. Выбрать случайную ячейку N
    2. Отметить N просмотренной
    3. Удалить N
    4. Посчитать решения. Если оно не единственное, то вернуть N обратно

    На выходе получится самая сложная из возможных вариантов Судоку для данного перемешивания. Переменная difficult оценивает сложность — количество оставшихся элементов.

    
    flook = [[0 for j in range(example.n*example.n)] for i in range(example.n*example.n)]
    iterator = 0
    difficult = example.n ** 4 #Первоначально все элементы на месте
    
    while iterator < example.n ** 4:
    	i,j = random.randrange(0, example.n*example.n ,1), random.randrange(0, example.n*example.n ,1) # Выбираем случайную ячейку
    	if flook[i][j] == 0:	#Если её не смотрели
    		iterator += 1
    		flook[i][j] = 1 	#Посмотрим
    
    		temp = example.table[i][j]	#Сохраним элемент на случай если без него нет решения или их слишком много
    		example.table[i][j] = 0
    		difficult -= 1 #Усложняем, если убрали элемент
    
    		table_solution = []
    		for copy_i in range(0, example.n*example.n):
    			table_solution.append(example.table[copy_i][:]) #Скопируем в отдельный список
    
    		i_solution = 0
    		for solution in solver.solve_sudoku((example.n, example.n), table_solution):
    			i_solution += 1 #Считаем количество решений
    
    		if i_solution != 1: #Если решение не одинственное -- вернуть всё обратно
    			example.table[i][j] = temp
    			difficult += 1  #Облегчаем
    
    example.show()
    print "difficult = ",difficult
    


    sudoku_generator.py
    # coding=utf-8
    import random
    import solver
    
    class grid:
    	def __init__(self,n = 3):
    		""" Generation of the base table """
    		self.n = n
    		self.table = [[ ((i*n + i/n + j) % (n*n) + 1) for j in range(n*n)] for i in range(n*n)]
    		print "The base table is ready!"
    
    	def __del__(self):
    		pass
    	
    	def show(self):
    		for i in range(self.n*self.n):
    			print self.table[i]
    
    	def transposing(self):
    		""" Transposing the whole grid """
    		self.table = map(list, zip(*self.table))
    
    	def swap_rows_small(self):
    		""" Swap the two rows """
    		area = random.randrange(0,self.n,1)
    		line1 = random.randrange(0,self.n,1)
    		#получение случайного района и случайной строки
    		N1 = area*self.n + line1
    		#номер 1 строки для обмена
    
    		line2 = random.randrange(0,self.n,1)
    		#случайная строка, но не та же самая
    		while (line1 == line2):
    			line2 = random.randrange(0,self.n,1)
    
    		N2 = area*self.n + line2
    		#номер 2 строки для обмена
    
    		self.table[N1],self.table[N2] = self.table[N2], self.table[N1]
    
    
    	def swap_colums_small(self):
    		grid.transposing(self)
    		grid.swap_rows_small(self)
    		grid.transposing(self)
    
    
    	def swap_rows_area(self):
    		""" Swap the two area horizon """
    		area1 = random.randrange(0,self.n,1)
    		#получение случайного района
    
    		area2 = random.randrange(0,self.n,1)
    		#ещё район, но не такой же самый
    		while (area1 == area2):
    			area2 = random.randrange(0,self.n,1)
    
    		for i in range(0, self.n):
    			N1, N2 = area1*self.n + i, area2*self.n + i
    			self.table[N1], self.table[N2] = self.table[N2], self.table[N1]
    
    
    	def swap_colums_area(self):
    		grid.transposing(self)
    		grid.swap_rows_area(self)
    		grid.transposing(self)
    	
    	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 xrange(1, amt):
    			id_func = random.randrange(0,len(mix_func),1)
    			eval(mix_func[id_func])
    
    example = grid()
    example.mix()
    
    flook = [[0 for j in range(example.n*example.n)] for i in range(example.n*example.n)]
    iterator = 0
    difficult = example.n ** 4 #Первоначально все элементы на месте
    
    example.show() 
    print "---------------------------"
    
    while iterator < example.n ** 4:
    	i,j = random.randrange(0, example.n*example.n ,1), random.randrange(0, example.n*example.n ,1) # Выбираем случайную ячейку
    	if flook[i][j] == 0:	#Если её не смотрели
    		iterator += 1
    		flook[i][j] = 1 	#Посмотрим
    
    		temp = example.table[i][j]	#Сохраним элемент на случай если без него нет решения или их слишком много
    		example.table[i][j] = 0
    		difficult -= 1 #Усложняем если убрали элемент
    
    		table_solution = []
    		for copy_i in range(0, example.n*example.n):
    			table_solution.append(example.table[copy_i][:]) #Скопируем в отдельный список
    
    		i_solution = 0
    		for solution in solver.solve_sudoku((example.n, example.n), table_solution):
    			i_solution += 1 #Считаем количество решений
    
    		if i_solution != 1: #Если решение не одинственное вернуть всё обратно
    			example.table[i][j] = temp
    			difficult += 1 # Облегчаем
    
    example.show()
    print "difficult = ",difficult
    


    solver.py
    #!/usr/bin/env python3
    
    # Author: Ali Assaf <ali.assaf.mail@gmail.com>
    # Copyright: (C) 2010 Ali Assaf
    # License: GNU General Public License <http://www.gnu.org/licenses/>
    
    from itertools import product
    
    def solve_sudoku(size, grid):
        """ An efficient Sudoku solver using Algorithm X.
    
        >>> grid = [
        ...     [5, 3, 0, 0, 7, 0, 0, 0, 0],
        ...     [6, 0, 0, 1, 9, 5, 0, 0, 0],
        ...     [0, 9, 8, 0, 0, 0, 0, 6, 0],
        ...     [8, 0, 0, 0, 6, 0, 0, 0, 3],
        ...     [4, 0, 0, 8, 0, 3, 0, 0, 1],
        ...     [7, 0, 0, 0, 2, 0, 0, 0, 6],
        ...     [0, 6, 0, 0, 0, 0, 2, 8, 0],
        ...     [0, 0, 0, 4, 1, 9, 0, 0, 5],
        ...     [0, 0, 0, 0, 8, 0, 0, 7, 9]]
        >>> for solution in solve_sudoku((3, 3), grid):
        ...     print(*solution, sep='\\n')
        [5, 3, 4, 6, 7, 8, 9, 1, 2]
        [6, 7, 2, 1, 9, 5, 3, 4, 8]
        [1, 9, 8, 3, 4, 2, 5, 6, 7]
        [8, 5, 9, 7, 6, 1, 4, 2, 3]
        [4, 2, 6, 8, 5, 3, 7, 9, 1]
        [7, 1, 3, 9, 2, 4, 8, 5, 6]
        [9, 6, 1, 5, 3, 7, 2, 8, 4]
        [2, 8, 7, 4, 1, 9, 6, 3, 5]
        [3, 4, 5, 2, 8, 6, 1, 7, 9]
        """
        R, C = size
        N = R * C
        X = ([("rc", rc) for rc in product(range(N), range(N))] +
             [("rn", rn) for rn in product(range(N), range(1, N + 1))] +
             [("cn", cn) for cn in product(range(N), range(1, N + 1))] +
             [("bn", bn) for bn in product(range(N), range(1, N + 1))])
        Y = dict()
        for r, c, n in product(range(N), range(N), range(1, N + 1)):
            b = (r // R) * R + (c // C) # Box number
            Y[(r, c, n)] = [
                ("rc", (r, c)),
                ("rn", (r, n)),
                ("cn", (c, n)),
                ("bn", (b, n))]
        X, Y = exact_cover(X, Y)
        for i, row in enumerate(grid):
            for j, n in enumerate(row):
                if n:
                    select(X, Y, (i, j, n))
        for solution in solve(X, Y, []):
            for (r, c, n) in solution:
                grid[r][c] = n
            yield grid
    
    def exact_cover(X, Y):
        X = {j: set() for j in X}
        for i, row in Y.items():
            for j in row:
                X[j].add(i)
        return X, Y
    
    def solve(X, Y, solution):
        if not X:
            yield list(solution)
        else:
            c = min(X, key=lambda c: len(X[c]))
            for r in list(X[c]):
                solution.append(r)
                cols = select(X, Y, r)
                for s in solve(X, Y, solution):
                    yield s
                deselect(X, Y, r, cols)
                solution.pop()
    
    def select(X, Y, r):
        cols = []
        for j in Y[r]:
            for i in X[j]:
                for k in Y[i]:
                    if k != j:
                        X[k].remove(i)
            cols.append(X.pop(j))
        return cols
    
    def deselect(X, Y, r, cols):
        for j in reversed(Y[r]):
            X[j] = cols.pop()
            for i in X[j]:
                for k in Y[i]:
                    if k != j:
                        X[k].add(i)
    
    if __name__ == "__main__":
        import doctest
        doctest.testmod()
    


    Результат работы
    The base table is ready!
    [5, 4, 6, 8, 7, 9, 2, 1, 3]
    [8, 7, 9, 2, 1, 3, 5, 4, 6]
    [2, 1, 3, 5, 4, 6, 8, 7, 9]
    [6, 5, 7, 9, 8, 1, 3, 2, 4]
    [9, 8, 1, 3, 2, 4, 6, 5, 7]
    [3, 2, 4, 6, 5, 7, 9, 8, 1]
    [7, 6, 8, 1, 9, 2, 4, 3, 5]
    [1, 9, 2, 4, 3, 5, 7, 6, 8]
    [4, 3, 5, 7, 6, 8, 1, 9, 2]
    ---------------------------
    [0, 0, 6, 0, 0, 0, 0, 0, 0]
    [8, 7, 0, 0, 1, 0, 0, 0, 6]
    [0, 0, 0, 5, 4, 0, 0, 0, 9]
    [6, 0, 0, 0, 8, 1, 3, 0, 4]
    [0, 0, 0, 3, 0, 0, 0, 5, 0]
    [0, 0, 0, 0, 0, 7, 0, 0, 0]
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
    [0, 9, 0, 4, 0, 0, 0, 0, 8]
    [0, 0, 5, 0, 6, 0, 1, 0, 0]
    difficult =  22
    


    Скачать в zip

    Я уверен, что есть и более сложные подходы в построении таблицы Судоку. Моя цель была достигнута, получился рабочий алгоритм. Теперь мне не нужно искать новые выпуски, я могу их генерировать :)
    В принципе, здесь был приведён частный случай Судоку 9х9. Но нет ограничений для использования его на 16х16 и 25х25.


    Если у кого есть лучшие предложения — не стесняйтесь оставить комментарий.
    Спасибо за внимание.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 22

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

      Исходник
      #include <stdio.h>
      #include <stdint.h>
      #include <stdlib.h>
      #include <string.h>
      #include <time.h>
      
      #define setBit(var, bit)    var |= 1 << bit
      #define checkBit(var, bit)  var & (1 << bit)
      
      enum { CLEAN = -1, LINE, ROW, SECTOR };
      
      struct _cell {
        uint8_t  value, line, row, sector;
        uint16_t used;
      };
      
      typedef struct _cell t_cell;
      
      t_cell *checkBox[3][9][9];
      t_cell  sol[81];
      
      int checkCell(int cell);
      
      int
      main(int argc, char **argv)
      {
        register int i, j = 0;
        int u = 0;
      
        memset(checkBox, 0, sizeof(checkBox));
        memset(sol, 0, sizeof(sol));
      
        /* Initialization */
        for(i = 0; i < 81; i++) {
          sol[i].line   = i / 9;
          sol[i].row    = i % 9;
          sol[i].sector = (((i / 9) / 3) * 3) + ((i % 9) / 3);
          checkBox[LINE][i / 9][i % 9] = &sol[i];
          checkBox[ ROW][i % 9][i / 9] = &sol[i];
          while(checkBox[SECTOR][sol[i].sector][j])
            ++j;
          checkBox[SECTOR][sol[i].sector][j] = &sol[i];
          j = 0;
        }
      
        srand(time(NULL));
      
        /* Generate solution */
        for(i = 0; i < 81; i++) {
          do {
            do {
              u = 0;
              if(sol[i].used == 511) {
                setBit(sol[i-1].used, (sol[i-1].value - 1));
                sol[i].used = sol[i].value = 0;
                i -= 2;
                u = 1;
                break;
              }
              sol[i].value = 1 + rand() % 9;
            } while((checkBit(sol[i].used, (sol[i].value - 1))));
            if(u)
              break;
          } while(checkCell(i) != CLEAN);
        }
      
        /* Display result */
        for(i = 0; i < 9; i++) {
          if(i%3 == 0)
            printf("-------------------------\n");
          printf("| %d %d %d | %d %d %d | %d %d %d |\n",
            sol[i*9].value,   sol[i*9+1].value, sol[i*9+2].value,
            sol[i*9+3].value, sol[i*9+4].value, sol[i*9+5].value,
            sol[i*9+6].value, sol[i*9+7].value, sol[i*9+8].value
          );
        }
        printf("-------------------------\n");
      
        return 0;
      }
      
      int
      checkCell(int cell)
      {
        register int i;
        int result = CLEAN;
      
        for(i = 0; i < 9; i++) {
          if(&sol[cell] != checkBox[LINE][sol[cell].line][i]) {
            if(sol[cell].value == checkBox[LINE][sol[cell].line][i]->value)
              result = LINE;
          }
          if(&sol[cell] != checkBox[ROW][sol[cell].row][i]) {
            if(sol[cell].value == checkBox[ROW][sol[cell].row][i]->value)
              result = ROW;
          }
          if(&sol[cell] != checkBox[SECTOR][sol[cell].sector][i]) {
            if(sol[cell].value == checkBox[SECTOR][sol[cell].sector][i]->value)
              result = SECTOR;
          }
        }
        if(result != CLEAN) {
          setBit(sol[cell].used, (sol[cell].value - 1));
        }
      
        return result;
      }
      



      P.S. Сразу хочу извиниться за качество кода, т.к. «я — не волшебник, а только учусь».
        0
        Но ведь при достаточно большом количестве «перемешиваний» разными методами можно получить совершенно любой вариант судоку. Также и ваш метод может дать любой вариант, в том числе и с видимостью «системы перестановки». Зато приведённый в посте метод, как вы уже отметили, выигрывает в производительности.

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

        Я это к тому, что судоку может быть очень сложным с 30 открытыми ячейками а может быть и элементарным с тем-же количеством открытых ячеек.
          +3
          Решение должно быть единственным по правилам судоку. Есть методы решения, которые опираются на этот факт.
          +3
          Жаль, что в конечном итоге всё равно пришлось решать судоку.
            0
            Мне кажется, что хороший генератор судоку должен уметь генерировать задачи заданной сложности. Вы пишете, что критериев оценки сложности нет. Но они есть. Сложность судоку определяется методами, которые необходимо применить, чтобы решить его. Количество открытых ячеек при этом не очень важно.

            В идеале нужно написать алгоритм решения судоку человеческими методами, а затем с помощью этого алгоритма оценивать сложность сгенерированного судоку. Но такая программа будет значительно сложнее.
              0
              Да, возможно стоит задуматься над методами оценки сложности Судоку и написать про это отдельный пост.
              +22
              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, похоже, принадлежит перу другого автора :) К нему претензий нет, написан очень хорошо.
                0
                3. Избегайте использования прямых вызовов print(). Если требуется отладочный вывод, дайте возможность пользователю задать свой собственный print_callback в __init__-е: …

                4. Используйте from __future__ import print_function в целях увеличения переносимости кода. Таким образом, print() станет функцией и код будет переносим между Python 2 и Python 3.
                Если использовать print только для отладочного вывода, то простого правила «всегда писать скобки после print» достаточно для переносимости. Мне никогда не приходило в голову передавать print как функцию куда‐либо: для этого есть logging (имею ввиду передачу экземпляров logging.Logger, если имеющийся настраиваемый глобальный Logger чем‐то не нравиться). И вместо print_callback тоже есть logging.

                Ко всем остальным пунктам сложно прицепиться.
                  +3
                  «Всегда писать скобки после print» чревато этим:
                  >>> print('Hello', 'world')
                  ('Hello', 'world')
                  >>> from __future__ import print_function
                  >>> print('Hello', 'world')
                  Hello world
                  


                  Насчет logging разумно, но это если нужно полноценное логгирование. Для целей отладки, как мне кажется, callback достаточно, но тут мы истины не найдем, т.к. любой подход хорош по своему.
                    0
                    А, понятно. Мне такое не встречалось: я всё время свожу аргументы print к одному. Возможно, правда, я их начал сводить именно по той причине, что вы здесь написали; не помню.
                  +6
                  Распечатаю комментарий и повешу на стену. Ожидал притензии по коду питона. Я новичок в этом деле и этот код в первой десятке написанного. Думаю, теперь все будет лучше.
                  +2
                  Наверное и не лучший вариант, но внятный, законченный и простой. Визуализация хорошая.

                  А как строят судоку существующие компьютерные программы вы не разбирали? Таким же способом?
                    0
                    По тому как строят Судоку ничего толкого не нашёл, собственно так и появился этот пост.
                    • UFO just landed and posted this here
                    0
                    Так и просится рандомный маппинг (неважно, перед перемешиванием, или после него).
                    То есть, как один из этапов — заменяем одни цифры на другие случайным образом. Естественно, с однозначным соответствием.
                      0
                      > неважно, перед перемешиванием, или после него

                      Или вместо… :)
                      0
                      Когда-то использовал именно этот алгоритм. Когда искал алгоритмы, из вменяемых нашел только этот.
                        +2
                        <оффтоп>
                        В прошлом году финский математик (Арто Инкала) создал самую сложную судоку.
                        Вот она:
                        image

                        з.ы. если хабрасторидж глючит с вставляевыми картинками, вот прямая ссылка
                        img.gawkerassets.com/img/18wd1m6020o3tpng/original.png
                          0
                          Ответ
                          8 1 2 | 7 5 3 | 6 4 9
                          9 4 3 | 6 8 2 | 1 7 5
                          6 7 5 | 4 9 1 | 2 8 3
                          ------+-------+------
                          1 5 4 | 2 3 7 | 8 9 6
                          3 6 9 | 8 4 5 | 7 2 1
                          2 8 7 | 1 6 9 | 5 3 4
                          ------+-------+------
                          5 2 1 | 9 7 4 | 3 6 8
                          4 3 8 | 5 2 6 | 9 1 7
                          7 9 6 | 3 1 8 | 4 5 2
                          +1
                          Как профессиональный решатель и автор разных головоломок могу сказать, что «хэнд-мэйд» задачи всегда лучше, чем автоматически сгенерированные. Хотя и среди автоматически сгенерированных изредка попадаются интересные экземпляры. Посему в соревнованиях по решению головоломок очень редко используются «автосгенеренные» задачи (а если кто-то из организаторов использует, то обычно получает немалую долю крититки от участников).
                          А вот для тренировочных целей генерация позволяет получить некий материал (я и сам имею пару сотен программ-генераторов) — решение таких задач позволяет приспособиться к задаче и «почуствовать» ее закономерности.
                            0
                            Кстати, если интересно и вы об этом еще не знаете — посмотрите на судоку от Gnome Games. Раньше она была на Питоне написана. Не знаю, правда, как сейчас. Вот там и есть генерация судоку (в заднем фоне) различных степеней сложности.

                            Only users with full accounts can post comments. Log in, please.