Напишите регулярное выражение, которое соответствует любому действующему решению судоку и не соответствует ни одному недействительному решению судоку. Вход является развернутой версией судоку, то есть без разделителей строк. Например, следующая доска:
7 2 5 8 9 3 4 6 1
8 4 1 6 5 7 3 9 2
3 9 6 1 4 2 7 5 8
4 7 3 5 1 6 8 2 9
1 6 8 4 2 9 5 3 7
9 5 2 3 7 8 1 4 6
2 3 4 7 6 1 9 8 5
6 8 7 9 3 5 2 1 4
5 1 9 2 8 4 6 7 3
будет дано как:
725893461841657392396142758473516829168429537952378146234761985687935214519284673
Правила, вероятно, уже известны, но на всякий случай ... доска судоку действительна тогда и только тогда, когда:
- Каждая строка содержит цифры от ровно
1
до9
одного раза. - Каждый столбец содержит цифры от одного
1
до9
одного. - Каждая из девяти подсеток 3х3 содержит цифры от одного
1
до9
одного.
правила
Ваш ответ должен состоять из одного регулярного выражения без какого-либо дополнительного кода (за исключением, необязательно, списка модификаторов регулярного выражения, необходимых для работы вашего решения). Вы не должны использовать функции своего языка regex, которые позволяют вам вызывать код на языке хостинга (например, e
модификатор Perl ).
Вы можете использовать любой аромат regex, который существовал до этого испытания, но, пожалуйста, укажите аромат.
Не предполагайте, что регулярное выражение привязано неявно. Например, если вы используете Python, предположите, что ваше регулярное выражение используется с, re.search
а не с re.match
. Ваше регулярное выражение не должно соответствовать всей строке. Ему просто нужно сопоставить хотя бы одну подстроку (которая может быть пустой) для допустимых решений и не дать совпадений для недействительных решений.
Вы можете предположить, что на входе всегда будет строка из 81 положительной цифры.
Это рег-гольф, поэтому выигрывает самое короткое в байтах. Если вашему языку требуются разделители (обычно /.../
) для обозначения регулярных выражений, не считайте сами разделители. Если вашему решению требуются модификаторы, добавьте один байт на каждый модификатор.
Тестовые случаи
Действительные доски:
123456789456789123789123456231564897564897231897231564312645978645978312978312645
725893461841657392396142758473516829168429537952378146234761985687935214519284673
395412678824376591671589243156928437249735186738641925983164752412857369567293814
679543182158926473432817659567381294914265738283479561345792816896154327721638945
867539142324167859159482736275398614936241587481756923592873461743615298618924375
954217683861453729372968145516832497249675318783149256437581962695324871128796534
271459386435168927986273541518734269769821435342596178194387652657942813823615794
237541896186927345495386721743269158569178432812435679378652914924813567651794283
168279435459863271273415986821354769734692518596781342615947823387526194942138657
863459712415273869279168354526387941947615238138942576781596423354821697692734185
768593142423176859951428736184765923572389614639214587816942375295837461347651298
243561789819327456657489132374192865926845317581673294162758943735914628498236571
243156789519847326687392145361475892724918653895263471152684937436729518978531264
498236571735914628162758943581673294926845317374192865657489132819327456243561789
978531264436729518152684937895263471724918653361475892687392145519847326243156789
341572689257698143986413275862341957495726831173985426519234768734869512628157394
Неверные доски:
519284673725893461841657392396142758473516829168429537952378146234761985687935214
839541267182437659367158924715692843624973518573864192298316475941285736456729381
679543182158926473432817659567381294914256738283479561345792816896154327721638945
867539142324167859159482736275398684936241517481756923592873461743615298618924375
754219683861453729372968145516832497249675318983147256437581962695324871128796534
271459386435168927986273541518734269769828435342596178194387652657942813823615794
237541896186927345378652914743269158569178432812435679495386721924813567651794283
168759432459613278273165984821594763734982516596821347615437829387246195942378651
869887283619214453457338664548525781275424668379969727517385163319223917621449519
894158578962859187461322315913849812241742157275462973384219294849882291119423759
123456789456789123564897231231564897789123456897231564312645978645978312978312645
145278369256389147364197258478512693589623471697431582712845936823956714931764825
243561789829317456657489132374192865916845327581673294162758943735924618498236571
243156789529847316687392145361475892714928653895263471152684937436719528978531264
498236571735924618162758943581673294916845327374192865657489132829317456243561789
978531264436719528152684937895263471714928653361475892687392145529847316243156789
342571689257698143986413275861342957495726831173985426519234768734869512628157394
345678192627319458892451673468793521713524986951862347179246835534187269286935714
341572689257698143986413275862341957495726831173985426519234768734869512628517394
Для дальнейших тестовых случаев вы можете использовать этот сценарий CJam, который принимает действительную доску в качестве входных данных и случайным образом перемешивает ее, чтобы дать новую действительную доску (формат ввода не имеет значения, если он содержит только цифры и, возможно, пробел).
Если ваше регулярное выражение совместимо со вкусом .NET, вы можете проверить его онлайн с помощью Retina. Действительное решение должно печатать 0
для недействительных досок и некоторое положительное целое число для допустимых досок. Чтобы запустить все тестовые сценарии одновременно, используйте этот шаблон и вставьте регулярное выражение во вторую строку. Если вам нужны модификаторы регулярных выражений, добавьте a `
к регулярному выражению и поместите перед ним стандартные буквы модификаторов.
источник
valid boards
?Ответы:
Ruby regex,
717873 байтаЯ действительно не знаю Ruby, но, видимо, он не жалуется на каскадные квантификаторы.
Попробуй это здесь.
.NET регулярное выражение,
797875 или 77 байтПотому что Мартин думает, что это возможно ... Но я думаю, он просто включит и эти изменения.
Требуется завершающий перевод строки во входных данных для работы. Я не уверен, разрешено ли мне это делать (вероятно, нет).
Попробуй это здесь.
77-байтовая вменяемая версия:
Спасибо Нейлу за то, что он указал на ошибку в моей предыдущей версии и отыгрывает 1 байт (для
(...)*
).Попробуй это здесь.
PCRE,
7778 байтПросто для полноты.
Попробуй это здесь.
Другая версия, также 78 байтов:
Попробуй это здесь.
объяснение
источник
PCRE, 117
119 130 133 147байтТакже должен работать в Python, Java и др. Вариантах.Теперь с рекурсией! И функция «рекурсия» использовалась нерекурсивно для «подпрограмм», о которых я полностью забыл, пока не пришлось использовать реальную рекурсию.источник
.{27}*
.^(?!(.{27})*(.{9})?(...){0,2}.?.?(.).?.?(?=(...)*$)(.{9})?.{6,8}\4.{0,17}(.{27})*$|.*(.)((.{9})+|((?!(.{9})*$).)+)(<=\8))
(<=\8)
не похож на правильный синтаксис (он отсутствует?
). Кроме того, единственный известный мне вариант, который поддерживает обратные ссылки в lookbehinds, - это .NET..NET регулярное выражение, 8339 байт
Да, я знаю, что мое решение очень наивно, так как Мартин сказал мне, что он сделал это за 130 байтов. На самом деле, URL, чтобы попробовать его в Интернете, был настолько длинным, что я не смог найти сокращатель URL, который бы его принял.
Ссылка ниже не работает в IE, но работает в Chrome и Firefox.
Попробуйте онлайн - все тестовые случаи сразу, с помощью
!`
в начале, не включенные в число байтов.Вот скрипт Python, который я использовал для его генерации (код ниже):
источник
.NET регулярное выражение, 121 байт
Объяснение:
источник
PCRE, 3579 байт
Абсолютно ужасное решение для грубой силы. Негативный взгляд позади ахой!
Я потратил слишком много времени на это, чтобы отказаться от него, так что вот, ради потомков.
С другой стороны, если судоку вдруг начнет использовать другой набор из 9 символов, это все равно будет работать, я думаю ...
http://pastebin.com/raw/CwtviGkC
Я не знаю, как управлять Retina, но вы также можете вставить его в https://regex101.com или аналогичный, и он будет соответствовать.
Код Ruby, используемый для генерации регулярного выражения:
источник
Рубиновый ароматизатор
7574 байтаСпасибо jimmy23013 за сохранение 1 байта.
Проверьте это здесь.
Теперь, когда это наконец побеждено, я могу поделиться своим собственным решением. :) Я обнаружил интересную (может быть, новую?) Технику регулярных выражений в процессе (
(.|(.)){,8}\3
часть), которая, вероятно, была бы непобедима в тех случаях, когда это нельзя объединить с другими частями регулярного выражения (как это было в ответе jimmy23013) ,объяснение
Как и в других коротких ответах, я использую отрицательный взгляд, который ищет дубликаты в строках, столбцах или блоках. Основной строительный блок решения заключается в следующем:
Обратите внимание, что
\3
повторно используется между тремя различными альтернативами (которые все используют группу3
для обнаружения дубликатов).Эта группа слева (которая является группой
2
, содержащей группу3
) используется для любой позиции, которая может содержать первую половину повторяющейся цифры (в пределах группы, которая не должна содержать повторяющиеся цифры). Затем...
мы получаем следующую позицию, в которой может появиться такая цифра (при необходимости), и\3
пытаются найти вторую половину дубликата с помощью обратной ссылки. Причина, по которой это работает, - возвращение. Когда двигатель впервые совпадает,(.|(.))
он будет просто использовать.
каждый раз и ничего не захватывать. Теперь\3
в конце не получается. Но теперь двигатель будет постепенно пытаться использовать(.)
вместо.
отдельных матчей. В конечном итоге, если есть дубликат, он найдет комбинацию, в которой(.)
последний раз использовался для первой цифры дубликата (так, чтобы захват не перезаписывался позже), а затем использует еще несколько,.
чтобы сократить разрыв с обратной ссылкой. Если есть дубликат, обратный поиск всегда найдет его.Давайте посмотрим на три разные части, где это используется:
Это проверяет наличие дубликатов в некоторой строке. Сначала мы переходим к любому ряду с
.{9}*
. Затем мы сопоставляем до 8 символов (т. Е. Все в этой строке, кроме последней цифры), используя необязательный дублирующий захват, и пытаемся найти\3
после него.Это ищет дубликаты в некотором столбце. Во-первых, обратите внимание, что
\g<2>
это вызов подпрограммы, так что это то же самое, что и:где две группы, которые мы только что вставили, все еще называются
2
и3
.Здесь
.*
просто пропускается по мере необходимости (этого будет достаточно, чтобы соответствовать до 8 символов здесь, но это стоит больше байтов). Затем внешняя группа совпадает с одной полной строкой (которая может охватывать две физические строки) за раз, при желании захватывая первый символ. Поиск\3
будет производиться сразу после этого, что обеспечивает вертикальное выравнивание между захватом и обратной ссылкой.Наконец, проверка блоков:
Опять же,
\g<2>
это вызов подпрограммы, так что это то же самое, что и:Чтобы проверить блоки, обратите внимание, что, поскольку мы уже проверили все строки и столбцы, нам нужно проверить только четыре из блоков 3x3. Когда мы знаем, что все строки и столбцы, а также эти блоки 3х3 являются правильными:
Тогда мы знаем, что в оставшихся блоках не может быть дубликатов. Поэтому я проверяю только эти четыре блока. Кроме того, обратите внимание, что нам не нужно искать дубликаты в одной строке блока 3х3. Достаточно найти первую половину дубликата в одной строке и искать вторую половину подряд ниже.
Теперь для самого кода мы сначала пропускаем начало одного из четырех блоков с помощью
.{27}?.{3}?
(опционально пропускаем три строки, опционально пропускаем три столбца). Затем мы пытаемся сопоставить до двух строк блока 3х3 с тем же приемом, который мы использовали для строк ранее:Мы разрешаем, но не требуем захвата любой из 3 ячеек в текущем ряду блока 3x3, а затем переходим к следующему ряду с помощью
.{6}
. Наконец, мы пытаемся найти дубликат в любой из 3 ячеек строки, в которой мы оказались:Вот и все.
источник
^(?!(.*((.|(.)).{8})*|.{9}*\g<3>{,8}|.{27}?.{3}?(\g<3>{3}.{6}){,2}.?.?)\4)
:; 73:^(?!(.*((.|(.)|\4()).{8})*|.{9}*\g<3>{9}|.{27}?.{3}?(\g<3>{3}.{6}){3})\5)
.\4()
трюк в более ранней версии для блоков 3х3, но в итоге избавился от него, потому что он был длиннее. : D341572689257698143986413275862341957495726831173985426519234768734869512628517394
Регулярное выражение Javascript,
532530481463 символовПроверить строки:
Проверить столбцы:
Подтвердите квадрат по его первому символу:
Установите предварительный просмотр для начала квадрата:
И все выражение:
Соответствует всей строке.
Тест в Javascript ES6:
источник
.
в(.{9})
скобках из-за следующего{0,8}
. Как вы думаете, почему столбцы должны быть короче?