Вы думали, что обычное судоку было трудно, теперь попробуйте Killer Sudoku !
В игре Killer Sudoku вам вообще не дают никаких чисел. Вместо этого вам дают регионы, которые, как говорят, складываются до определенного числа. Рассмотрим следующий пример из Википедии:
И его решение:
Программа, которую вы напишите, будет иметь формат, состоящий из последовательности из 81 буквы, представляющей регионы, за которой следует последовательность чисел. Затем каждое число в последовательности представляет собой сумму чисел в каждой из буквенных областей, начиная с «A», «B» и т. Д.
Затем он выведет последовательность из 81 цифры, представляющую решение.
Например, в приведенном выше примере головоломки будет иметь следующий вход:
AABBBCDEFGGHHCCDEFGGIICJKKFLMMINJKOFLPPQNJOORSPTQNUVVRSTTQWUUXXSYZWWaaXXSYZWbbbcc
3 15 22 4 16 15 25 17 9 8 20 6 14 17 17 13 20 12 27 6 20 6 10 14 8 16 15 13 17
И полученный результат будет:
215647398368952174794381652586274931142593867973816425821739546659428713437165289
Вы можете предположить, что ввод действителен, и что регионы всегда будут отображаться в порядке A, B, ..., Y, Z, a, b, ..., z.
(Самый короткий код, который работает, выигрывает.)
источник
Ответы:
R - 378 символов
Если предположить,
378 символов:
на моем скромном ПК требуется около часа, чтобы достичь ожидаемого решения после 2 964 690 итераций.
Де-golfed:
источник
GolfScript, 138 символов
Это решатель убийц судоку в GolfScript. Он ожидает ввода в STDIN в две строки, как указано в примере выше.
Обратите внимание: поскольку описание головоломки не накладывает никаких ограничений на время выполнения, я предпочел небольшой размер кода, а не скорость. Код проверяет все 9 ^ 81 сеточные конфигурации для решения, которое может занять некоторое время на медленном компьютере ;-)
источник
AABBCADEFFDDGGGG
6 7 4 8 2 3 10
Рубин, 970 знаков
Приведенный выше код рубина противоположен моей подписке на GolfScript. Это довольно долго (и еще не полностью гольф), но оптимизировано для скорости. Приведенный выше убийственный судоку решается за считанные секунды (с моей оригинальной версией Java это было всего несколько миллисекунд). Сам решатель является базовой реализацией алгоритма Кнута DLX.
Ввод должен быть представлен в виде двух строк на STDIN. Пример ( онлайн ):
источник