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

[elanc]

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

Исходник

#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. Сразу хочу извиниться за качество кода, т.к. «я — не волшебник, а только учусь».

[lvx]

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

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

[TheHorse]

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

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

[Riateche]

Решение должно быть единственным по правилам судоку. Есть методы решения, которые опираются на этот факт.

[Sayonji]

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

[Riateche]

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

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

[hashspark]

Да, возможно стоит задуматься над методами оценки сложности Судоку и написать про это отдельный пост.

[mwizard]

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, похоже, принадлежит перу другого автора :) К нему претензий нет, написан очень хорошо.

[ZyXI]

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.

Ко всем остальным пунктам сложно прицепиться.

[mwizard]

«Всегда писать скобки после print» чревато этим:

>>> print('Hello', 'world')
('Hello', 'world')
>>> from __future__ import print_function
>>> print('Hello', 'world')
Hello world

Насчет logging разумно, но это если нужно полноценное логгирование. Для целей отладки, как мне кажется, callback достаточно, но тут мы истины не найдем, т.к. любой подход хорош по своему.

[ZyXI]

А, понятно. Мне такое не встречалось: я всё время свожу аргументы print к одному. Возможно, правда, я их начал сводить именно по той причине, что вы здесь написали; не помню.

[hashspark]

Распечатаю комментарий и повешу на стену. Ожидал притензии по коду питона. Я новичок в этом деле и этот код в первой десятке написанного. Думаю, теперь все будет лучше.

[dnovikoff]

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

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

[hashspark]

По тому как строят Судоку ничего толкого не нашёл, собственно так и появился этот пост.

[Sergey40a]

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

[sophist]

> неважно, перед перемешиванием, или после него

Или вместо… :)

[AxisPod]

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

[timukas]

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


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

[x0wl]

Ответ

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

[bay73]

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

[Vest]

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

[SpBerkut]

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