|
>>
|
No. 6159
http://pastebin.com/bUhYu1za
Так вот, это генератор латинских квадратов 9х9, короче говоря судоку. Захотелось написать его, потому что во время чтения книжки, которую упоминал в ОП посте мне в голову пришла идея, которая быстро оформилась в алгоритм генерирования судоку, который, как мне казалось, должен был заполнять все ячейки с первого раза, т.е. ровно за 81 итерацию.
Если бегло подумать о задаче судоку, то первое, что приходит на ум, это просто случайно вносить числа поочередно во все ячейки матрицы и каждый раз проверять, не стоит ли это число в соответствующей вертикали/горизонтали/блоке (области 3х3). И если стоит, выбрать число заново. И так каждый раз. Пока не заполнится вся матрица.
Как- то не очень.
Короче говоря, я вот что придумал.
У нас есть мешочек с шариками от 1 до 9. Мешаем, вытягиваем шарик, записываем число в первую ячейку матрицы. Затем берем три таких же как вытянутый шарика и добавляем в три дополнительных мешочка - один отвечает за соответствующую горизонталь (для первого элемента она первая) другой- вертикаль (то же первая) и третий за соответствующий блок. Затем сдвигаемся на одну ячейку вправо и проверяем соответствующие ей мешочки... Оба на, а мешочка то только два- отвечающий за первую горизонталь и за первый блок! И число в них одно и то же! Мы шарим в нём рукой и достаем шарики которые в нем есть (для второго элемента шарик только один). Смотрим, что это за шарик, убираем его обратно в мешочек и достаем из нашего главного мешочка точно такой же. Теперь в главном мешочке только 8 шариков и мы можем смело тянуть один из них наугад и он совершенно точно не совпадет с тем, который мы вытянули в первой ячейке! После того, как мы его вытянули, мы, естественно, кладем шарики с той же цифрой в мешочек первой горизонтали, мешочек второй вертикали и мешочек первого блока (представьте, что мы пронумеровали блоки 3 на 3 как на пикрелейтеде). Вносим число в ячейку, добавляем шарики в мешочке из которого тянем. Затем сдвигаемся ещё на одну ячейку вправо и проводим ту же операцию. И так для каждого элемента в матрице. Что у нас получается?
К концу матрицы, у нас будет куча почти полностью забитых мешочков,
|
