Фон
Судоку - это головоломка с числами, где с учетом сетки разделенной на блоки размером , каждое число от до должно появляться ровно один раз в каждой строке, столбце и поле.
В игре в шахматы король может перейти в любую из (максимум) 8 соседних клеток за ход. «Смежный» здесь означает смежный по горизонтали, вертикали или диагонали.
В тур короля аналогия тура рыцаря; это (возможно, открытый) путь, который посещает каждую клетку ровно один раз на данной доске с помощью движений шахматного короля.
задача
Рассмотрим сетку судоку 6 на 6:
654 | 321
123 | 654
----+----
462 | 135
315 | 246
----+----
536 | 412
241 | 563
и тур короля (от 01
до 36
):
01 02 03 | 34 35 36
31 32 33 | 04 05 06
---------+---------
30 23 28 | 27 26 07
22 29 24 | 25 09 08
---------+---------
21 19 16 | 10 14 13
20 17 18 | 15 11 12
Тур формирует 36-значный номер 654654564463215641325365231214123321
.
Принимая другой тур короля дает большие цифры; например, я могу найти путь, который начинается с, 65<6>56446556...
который определенно больше, чем выше. Вы можете изменить доску судоку, чтобы получить еще большее число:
... | ...
.6. | ...
----+----
..6 | ...
.5. | 6..
----+----
.45 | .6.
6.. | 5..
Эта неполная доска дает начальную последовательность, 666655546...
которая является оптимальной последовательностью из 9 начальных цифр.
Ваша задача - найти наибольшее такое число для стандартного судоку 9 на 9 с блоками 3 на 3 , т.е.
... | ... | ...
... | ... | ...
... | ... | ...
----+-----+----
... | ... | ...
... | ... | ...
... | ... | ...
----+-----+----
... | ... | ...
... | ... | ...
... | ... | ...
Обратите внимание, что это не код-гольф ; главное - найти решения, а не написать небольшую программу, которая теоретически работает.
Критерий оценки и выигрыша
Счет подачи - это 81-значный номер, найденный вашей программой. Представление с наибольшим количеством очков выигрывает. Ваша программа должна также выводить сетку Судоку и тур Короля в удобочитаемой форме; пожалуйста, включите их в ваше представление.
Ваша программа может выводить несколько результатов; ваш счет является максимальным из них.
Там нет ограничения по времени для вашей программы. Если ваша программа продолжает работать и впоследствии находит большее число, вы можете обновить счет за отправку, отредактировав сообщение. Tiebreaker - это самое раннее время для достижения оценки, т.е. либо время публикации (если оно еще не редактировалось), либо время редактирования, когда оценка была обновлена (в противном случае).
источник
Ответы:
Python + Z3 , 999899898789789787876789658767666545355432471632124566352413452143214125313214321, оптимальный
Работает около получаса, производя
Код
источник