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

в 14:42, , рубрики: python, алгоритм, Алгоритмы, судоку, метки: , ,

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.

Если у кого есть лучшие предложения — не стесняйтесь оставить комментарий.
Спасибо за внимание.

Автор: hashspark

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js