Comments 23
Ваш способ, вероятно, наиболее быстрый, но я предпочитаю жесткий рандом!
Я изучаю Си и очень люблю судоку, так что написал свой генератор судоку, который можно использовать и для решения при совсем небольшой доработке. В отличии от Вашего генератора я не использую готовую матрицу, а генерирую первую строку и «решаю» остальную часть путем перебора. Конечно, мой вариант очень сильно проигрывает по производительности Вашему, зато всегда оригинальное судоку, а в варианте с перестановкой строк часто при решении замечаешь систему перестановки и судоку уже становится очень простым в решении.
P.S. Сразу хочу извиниться за качество кода, т.к. «я — не волшебник, а только учусь».
Я изучаю Си и очень люблю судоку, так что написал свой генератор судоку, который можно использовать и для решения при совсем небольшой доработке. В отличии от Вашего генератора я не использую готовую матрицу, а генерирую первую строку и «решаю» остальную часть путем перебора. Конечно, мой вариант очень сильно проигрывает по производительности Вашему, зато всегда оригинальное судоку, а в варианте с перестановкой строк часто при решении замечаешь систему перестановки и судоку уже становится очень простым в решении.
Исходник
#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. Сразу хочу извиниться за качество кода, т.к. «я — не волшебник, а только учусь».
+2
Но ведь при достаточно большом количестве «перемешиваний» разными методами можно получить совершенно любой вариант судоку. Также и ваш метод может дать любой вариант, в том числе и с видимостью «системы перестановки». Зато приведённый в посте метод, как вы уже отметили, выигрывает в производительности.
P.S. Сейчас пишу свой судоку-велосипед дабы поупражняться в JavaScript и поломать себе мозг. Планировал сначала решить вопрос генерации как и вы, но затем нашёл этот пост и был очарован этим решением.
P.S. Сейчас пишу свой судоку-велосипед дабы поупражняться в JavaScript и поломать себе мозг. Планировал сначала решить вопрос генерации как и вы, но затем нашёл этот пост и был очарован этим решением.
0
Я бы сложность конкретного экземпляра оценивал минимальной глубиной бэктрекинга (backtracking) необходимого для решения этого экземпляра. Ну и не опирался бы на то, что решение должно быть единственным. Зачем?
Я это к тому, что судоку может быть очень сложным с 30 открытыми ячейками а может быть и элементарным с тем-же количеством открытых ячеек.
Я это к тому, что судоку может быть очень сложным с 30 открытыми ячейками а может быть и элементарным с тем-же количеством открытых ячеек.
0
Жаль, что в конечном итоге всё равно пришлось решать судоку.
+3
Мне кажется, что хороший генератор судоку должен уметь генерировать задачи заданной сложности. Вы пишете, что критериев оценки сложности нет. Но они есть. Сложность судоку определяется методами, которые необходимо применить, чтобы решить его. Количество открытых ячеек при этом не очень важно.
В идеале нужно написать алгоритм решения судоку человеческими методами, а затем с помощью этого алгоритма оценивать сложность сгенерированного судоку. Но такая программа будет значительно сложнее.
В идеале нужно написать алгоритм решения судоку человеческими методами, а затем с помощью этого алгоритма оценивать сложность сгенерированного судоку. Но такая программа будет значительно сложнее.
0
1. Классы лучше называть с большой буквы, чтобы визуально отличать их от переменных, содержащих экземпляры классов этого типа. Т.е.
2. Наследуйте объекты от
3. Избегайте использования прямых вызовов
4. Используйте
5. Не делайте публичными те поля класса, изменение которых после создания экземпляра класса может сломать его работу. Если хотите предоставить пользователю возможность узнать значение поля после создания экземпляра, используйте свойства:
6. Не используйте обычное деление
7. Пустой метод
8. Код вида
9. В
10. В Python 2
11. В
12. В
13. То же относится к
14. Вместо косвенного вызова вида
15. Метод
16. В функции выше я также заменил выбор элемента по случайному индексу
17. В функции выше неправильно использован range — при отсчете от 1 количество раз, которые была применена трансформация, будет на 1 меньше. Т.е. при amt = 1 вообще ничего не произойдет.
18. Старайтесь использовать
19. Для создания повторяющихся строк можно использовать умножение —
20. Код в конце модуля
21. Именовать методы, как и описывать docstring-и лучше в present indefinite —
22. Код модуля
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
, похоже, принадлежит перу другого автора :) К нему претензий нет, написан очень хорошо. +22
3. Избегайте использования прямых вызовов print(). Если требуется отладочный вывод, дайте возможность пользователю задать свой собственный print_callback в __init__-е: …Если использовать print только для отладочного вывода, то простого правила «всегда писать скобки после
4. Используйте from __future__ import print_function в целях увеличения переносимости кода. Таким образом, print() станет функцией и код будет переносим между Python 2 и Python 3.
print
» достаточно для переносимости. Мне никогда не приходило в голову передавать print
как функцию куда‐либо: для этого есть logging
(имею ввиду передачу экземпляров logging.Logger
, если имеющийся настраиваемый глобальный Logger
чем‐то не нравиться). И вместо print_callback
тоже есть logging
.Ко всем остальным пунктам сложно прицепиться.
0
«Всегда писать скобки после
Насчет
print
» чревато этим:>>> print('Hello', 'world')
('Hello', 'world')
>>> from __future__ import print_function
>>> print('Hello', 'world')
Hello world
Насчет
logging
разумно, но это если нужно полноценное логгирование. Для целей отладки, как мне кажется, callback достаточно, но тут мы истины не найдем, т.к. любой подход хорош по своему. +3
Распечатаю комментарий и повешу на стену. Ожидал притензии по коду питона. Я новичок в этом деле и этот код в первой десятке написанного. Думаю, теперь все будет лучше.
+6
Наверное и не лучший вариант, но внятный, законченный и простой. Визуализация хорошая.
А как строят судоку существующие компьютерные программы вы не разбирали? Таким же способом?
А как строят судоку существующие компьютерные программы вы не разбирали? Таким же способом?
+2
Так и просится рандомный маппинг (неважно, перед перемешиванием, или после него).
То есть, как один из этапов — заменяем одни цифры на другие случайным образом. Естественно, с однозначным соответствием.
То есть, как один из этапов — заменяем одни цифры на другие случайным образом. Естественно, с однозначным соответствием.
0
Когда-то использовал именно этот алгоритм. Когда искал алгоритмы, из вменяемых нашел только этот.
0
<оффтоп>
В прошлом году финский математик (Арто Инкала) создал самую сложную судоку.
Вот она:

з.ы. если хабрасторидж глючит с вставляевыми картинками, вот прямая ссылка
img.gawkerassets.com/img/18wd1m6020o3tpng/original.png
В прошлом году финский математик (Арто Инкала) создал самую сложную судоку.
Вот она:

з.ы. если хабрасторидж глючит с вставляевыми картинками, вот прямая ссылка
img.gawkerassets.com/img/18wd1m6020o3tpng/original.png
+2
Как профессиональный решатель и автор разных головоломок могу сказать, что «хэнд-мэйд» задачи всегда лучше, чем автоматически сгенерированные. Хотя и среди автоматически сгенерированных изредка попадаются интересные экземпляры. Посему в соревнованиях по решению головоломок очень редко используются «автосгенеренные» задачи (а если кто-то из организаторов использует, то обычно получает немалую долю крититки от участников).
А вот для тренировочных целей генерация позволяет получить некий материал (я и сам имею пару сотен программ-генераторов) — решение таких задач позволяет приспособиться к задаче и «почуствовать» ее закономерности.
А вот для тренировочных целей генерация позволяет получить некий материал (я и сам имею пару сотен программ-генераторов) — решение таких задач позволяет приспособиться к задаче и «почуствовать» ее закономерности.
+1
Кстати, если интересно и вы об этом еще не знаете — посмотрите на судоку от Gnome Games. Раньше она была на Питоне написана. Не знаю, правда, как сейчас. Вот там и есть генерация судоку (в заднем фоне) различных степеней сложности.
0
Генерируемые сетки получаются донельзя простыми, т.к. цифры перемещаются группами по три. Решать такие будет неинтересно.
0
Only those users with full accounts are able to leave comments. Log in, please.
Алгоритм генерации судоку