Победитель найден
Кажется, у нас есть победитель! Если никто не планирует оспаривать самый быстрый в мире решатель судоку, пользователь 53x15 выигрывает с потрясающе быстрым решателем Tdoku. Для тех, кто все еще работает над своими решателями, я по-прежнему буду тестировать новые работы, когда у меня будет время.
Соревнование
Цель игры в судоку состоит в том, чтобы заполнить игровое поле числами 1-9, по одному в каждой ячейке, таким образом, чтобы каждая строка, столбец и поле содержали каждое число только один раз. Очень важный аспект головоломки Судоку состоит в том, что должно быть только одно правильное решение.
Цель этого задания проста: вы должны решить множество головоломок судоку как можно быстрее. Тем не менее, вы не просто решите какую-то старую судоку, вы будете решать самые сложные из существующих головоломок судоку, судоку с 17 подсказками. Вот пример:
правила
язык
Вы можете свободно использовать любой язык. Если у меня не установлен компилятор для вашего языка, вы сможете предоставить набор команд командной строки, необходимых для установки среды, в которой ваш скрипт может быть запущен в Linux .
Эталонная машина
Тест будет выполняться на Dell XPS 9560, 2,8 ГГц Intel Core i7-7700HQ (3,8 ГГц), 4 ядра, 8 потоков, 16 ГБ ОЗУ. GTX 1050 4ГБ. На машине работает Ubuntu 19.04. Вот uname
вывод, для всех, кто заинтересован.
Linux 5.0.0-25-generic #26-Ubuntu SMP Thu Aug 1 12:04:58 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
вход
Ввод будет предоставлен в виде файла. Это можно найти здесь . Файл содержит 49151 головоломок судоку. Первая строка файла содержит количество головоломок, а каждая строка длиной 81 символ представляет собой головоломку. Неизвестные клетки есть 0
, а известные клетки есть 1-9
.
Ваша программа должна иметь возможность принимать имя файла в качестве аргумента или иметь входной файл из STDIN , чтобы облегчить ручную проверку вашего решения. Пожалуйста, включите инструкцию о том, как ваша программа принимает данные.
Сроки / оценка
Из обсуждений в комментариях и некоторых размышлений критерии оценки были изменены, чтобы соответствовать времени всей вашей программы. Ваша программа должна создать выходной файл с правильным хэшем даже во время официального подсчета очков. Это не мешает существующему решению и не меняет рейтинг в его нынешнем виде. Любые мысли о системе оценки приветствуются.
Если два решения имеют одинаковые оценки для отдельных прогонов, я проведу несколько тестов, и среднее время будет окончательным. Если средние оценки отличаются менее чем на 2%, я буду считать это ничьей.
Если ваше решение занимает больше часа, оно не будет официально оценено. В этих случаях вы несете ответственность за сообщение о машине, на которой он работал, и за ваш счет. Для оптимизированного решателя это не должно быть проблемой.
РЕДАКТИРОВАТЬ : Мне было доведено до сведения, что, хотя трудно, поставленная задача не самая сложная из существующих. Если будет время, я постараюсь сравнить представленные здесь решения с более сложным набором головоломок и добавить оценку к каждой заявке. Однако это не будет официальным подсчетом очков, а просто для удовольствия.
верификация
Ваше решение будет проверено контрольной суммой MD5 / SHA256. Ваш скрипт должен иметь возможность генерировать файл, содержащий все головоломки и их решения. Однако файл также будет проверяться вручную, поэтому не пытайтесь получить коллизию хеша. Ваш выходной файл должен соответствовать:
MD5: 41704fd7d8fd0723a45ffbb2dbbfa488
SHA256:0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05
Файл будет в формате:
<num_puzzles>
<unsolved_puzzle#1>,<solved_puzzle#1>
<unsolved_puzzle#2>,<solved_puzzle#2>
...
<unsolved_puzzle#n>,<solved_puzzle#n>
с одним завершающим переводом строки.
Что не разрешено
Вам никоим образом не разрешено использовать жесткие решения . Ваш алгоритм должен быть применим к любому набору головоломок судоку, как простому, так и сложному. Тем не менее, это вполне нормально, если ваше решение медленно для более простых головоломок.
Вам не разрешено иметь недетерминированную программу . Вам разрешено использовать генератор случайных чисел, но начальное число генератора должно быть исправлено. Это правило должно гарантировать, что измерения более точны и имеют меньшую дисперсию. (Спасибо Питеру Тейлору за подсказку)
Вы не можете использовать какие-либо внешние ресурсы или веб-запросы во время выполнения вашей программы. Все должно быть автономным. Это не относится к установленным библиотекам и пакетам, которые разрешены.
Другая информация
Если вы хотите, чтобы другой тестовый набор проверил ваше решение, вот вам 10000 упрощенных Судоку . Вот их решения .
MD5: 3cb465ef6077c4fcab5bd6ae3bc50d62
SHA256:0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05
Если у вас есть какие-либо вопросы, не стесняйтесь спрашивать, и я постараюсь уточнить любые недоразумения.
Ответы:
C ++ - официальный счет 0.201
Использование Tdoku ( код ; дизайн ; тесты ) дает следующие результаты:
Tdoku был оптимизирован для сложных случаев судоку. Но обратите внимание, вопреки постановке проблемы, 17 загадочных головоломок далеки от самой сложной судоку. На самом деле они одни из самых простых, большинство из них вообще не требуют возврата. Посмотрите на другие тестовые наборы данных в проекте Tdoku, чтобы найти действительно сложные головоломки.
Также обратите внимание, что, хотя Tdoku является самым быстрым решателем, который я знаю для сложных головоломок, он не самый быстрый для 17 разгадочных головоломок. Для них, я думаю, самым быстрым является этот проект ржавчины , производный от JCZSolve, который был оптимизирован для 17 разгадок в процессе разработки. В зависимости от платформы это может быть на 5-25% быстрее, чем Tdoku для этих головоломок.
источник
Node.js ,
8,231 с6,735 с официальным счетомПринимает имя файла в качестве аргумента. Входной файл может уже содержать решения в формате, описанном в задании, и в этом случае программа будет сравнивать их с собственными решениями.
Результаты сохраняются в «sudoku.log» .
Код
Пример вывода
Протестировано на Intel Core i7 7500U при 2,70 ГГц.
источник
Python 3 (с dlx ) 4 минуты 46.870с официальный счет
(одноядерный i7-3610QM здесь)
Очевидно, что можно победить на скомпилированном языке, таком как C, и использовать потоки, но это только начало ...
sudoku
это модуль, который я поместил на github (скопирован в нижний колонтитул этого поста), который используетсяdlx
под капотом.использование
sudoku.py
где-нибудь на своем пути (из ссылки на git hub или скопируйте ее снизу)testSolver.py
нибудь на своем путиПередайте вывод в соответствии с требованиями спецификации вызова в файл, если это необходимо:
sudoku.py (да, здесь есть дополнительные функции, помимо решения)
источник
Python 3 + Z3 - 10 мин.
около 1000 на моем ноутбуке.
Установить зависимость
Бегать
Я не уверен, как улучшить его производительность, так как он просто решен волшебным образом ...
источник
C -
2.228 с1.690 с официальным счетомоснованный на @ Arnauld's
скомпилируйте и запустите:
источник
C - 12 минут 28,374 с официального счета
работает около
30 м15 м на моем i5-7200U и выдает правильный хэш md5скомпилируйте (желательно с clang v6) и запустите:
источник
memcpy
и продолжается некоторая рекурсия. Я попробую проверить это сегодня.Java - официальный рейтинг 4.056s
Основная идея этого состоит в том, чтобы никогда не выделять память, когда она не нужна. Единственным исключением являются примитивы, которые в любом случае должны быть оптимизированы компилятором. Все остальное хранится в виде масок и массивов операций, выполняемых на каждом шаге, которые можно отменить после завершения шага рекурсии.
Около половины всех судоку решается полностью без возврата, но если я нажму на это число выше, общее время будет медленнее. Я планирую переписать это на C ++ и оптимизировать еще дальше, но этот решатель становится чудовищным.
Я хотел реализовать как можно больше кэширования, что привело к некоторым проблемам. Например, если в одной строке есть две ячейки, которые могут иметь только номер 6, то мы достигли невозможного случая и должны вернуться к возврату. Но так как я вычислил все параметры за один цикл, а затем поместил числа в ячейки только с одной возможностью, я не проверял дважды, что я поместил число в той же строке непосредственно перед этим. Это приводит к невозможным решениям.
Со всем, что содержится в массивах, определенных сверху, использование памяти фактическим решателем составляет около 216 КБ. Основная часть использования памяти поступает из массива, содержащего все головоломки, и обработчиков ввода / вывода в Java.
РЕДАКТИРОВАТЬ : У меня есть версия, которая переведена на C ++ сейчас, но она не намного быстрее. Официальное время составляет около 3,5 секунд, что не является значительным улучшением. Я думаю, что основная проблема с моей реализацией заключается в том, что я сохраняю свои маски как массивы, а не как битовые маски. Я попытаюсь проанализировать решение Арно, чтобы посмотреть, что можно сделать, чтобы улучшить его.
источник
C ++ с Minisat (2.2.1-5) - официальный счет 11.735
Это далеко не так быстро, как специализированный алгоритм, но это другой подход, интересная точка отсчета и легко понять.
$ clang ++ -o решить -lminisat solver_minisat.cc
источник