Вызов Кода: Создайте Программу Для Решения Судоку С Минимальным Набором Подсказок.

Моя попытка изложить этот вопрос, но с более объективным критерием решения.

Ваша задача — создать программу или функцию, которая использует решенную сетку судоку. S in the format of your choice and attempts to generate a problem grid with as few clues as possible that has S как его уникальное решение. (Неважно, какой метод S is the unique solution by, including brute force, as long as the solution is provably unique.)

Ваша программа будет оценена путем ее запуска через набор из 100 000 сеток решений, найденных в этот файл (загрузка 7,82 МБ) и суммирование количества подсказок во всех 100 000 сетках задач, которые создает ваше решение.

Решения судоку в приведенном выше тестовом файле выражаются в виде строки из 81 символа слева направо, а затем сверху вниз. Код, необходимый для преобразования входных данных тестового файла в пригодное для использования решение, не будет учитываться при подсчете байтов вашего решения.

Как в моем Заливная краска Чтобы решить эту задачу, ваша программа должна фактически выдать действительный результат для всех 100 000 головоломок. Программа, которая выдает наименьшее количество подсказок для всех 100 000 тестовых случаев, становится победителем, а более короткий код разрешает ничью.

Текущее табло:

1. 2,361,024 - нутки, С
2. 2,580,210 - es1024, PHP
3. 6,000,000 - КоверPython, Python 2
4. 7,200,000 - Джо З., Питон

#вызов кода #оптимизация #судоку #тест-батарея

C - 2 361 024 2 509 949 подсказок

Удалите подсказки, начиная с последней ячейки, если метод грубой силы находит только одно уникальное решение.

Вторая попытка: используйте эвристику, чтобы решить, в каком порядке удалять подсказки, а не начинать с последней. Из-за этого код работает намного медленнее (20 минут вместо 2 для вычисления результата). Я мог бы сделать решатель быстрее, поэкспериментировать с разными эвристиками, но пока сойдет.

 
 
 
 
 
 
 
 #!/bin/bash

concurrency=$1

killall minimize 2>/dev/null
rm -f ppcg_?? ppcg_??.done
split -n l/$concurrency ppcg_sudoku_testing.txt ppcg_

for p in {0..20}; do

t1=$(date +%s)

lim=$((2**p))

for f in ppcg_??; do

./minimize $lim $f > $f.done &

done

wait

t2=$(date +%s)

cat *.done | awk -F' ' -v t=$((t2 - t1)) -v n=$lim '{ x += $2 } END { printf("%5d: d  %d sec\n",n,x,t); }'
done
 
 
 
 
 
 
 
 

Питон — 7 200 000 подсказок

Как обычно, вот эталонное решение на последнем месте:

Удаление нижнего ряда чисел, очевидно, оставляет головоломку разрешимой во всех случаях, поскольку в каждом столбце по-прежнему заполнено 8 из 9 чисел, а каждое число в нижнем ряду — это просто девятое число, оставшееся в столбце.

Если какому-либо серьезному сопернику удастся по закону набрать худший результат, чем этот, я буду удивлен.

Python 2 — 6 000 000 подсказок

Простое решение, использующее 3 распространенных метода решения этих головоломок:

Эта функция создает такие форматы подсказок:

Это всегда можно решить. Сначала решаются 4 детали 3х3, затем 8 столбцов, затем 9 рядов.

PHP — 2 580 210 подсказок

Сначала удаляется последняя строка и столбец, а также нижний правый угол каждого поля. Затем он пытается очистить каждую ячейку, пропуская доску через простой решатель после каждого изменения, чтобы убедиться, что доска по-прежнему однозначно разрешима.

Большая часть приведенного ниже кода была изменена с один из моих старых ответов. printBoard uses 0s for empty cells.

C++/Tdoku — 2 081 604 подсказки

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

Следует отметить тот факт, что кривая не выравнивается быстро, и меньшие числа явно могут быть достигнуты без каких-либо умений, просто стремясь к большему N.

минимизировать.cc:

run.sh