Napisz wyrażenie, które pasuje do dowolnego prawidłowego rozwiązania sudoku i nie pasuje do żadnego nieprawidłowego rozwiązania sudoku. Dane wejściowe to rozwinięta wersja sudoku, tzn. Nie ma ograniczników linii. Np. Następująca tablica:

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

byłby podany jako:

725893461841657392396142758473516829168429537952378146234761985687935214519284673

Zasady są już prawdopodobnie powszechnie znane, ale na wszelki wypadek ... plansza sudoku jest ważna wtedy i tylko wtedy, gdy:

• Każdy wiersz zawiera cyfry od 1do 9dokładnie raz.
• Każda kolumna zawiera cyfry od 1do 9dokładnie raz.
• Każda z dziewięciu podsiatek 3x3 zawiera cyfry od 1do 9dokładnie raz.

Zasady

Twoja odpowiedź powinna składać się z jednego wyrażenia regularnego, bez dodatkowego kodu (z wyjątkiem, opcjonalnie, listy modyfikatorów wyrażeń regularnych wymaganych do działania rozwiązania). Nie wolno używać funkcji smaku regularnego swojego języka, które pozwalają na wywołanie kodu w języku hostingowym (np. eModyfikator Perla ).

Możesz użyć dowolnego smaku wyrażenia regularnego, który istniał przed tym wyzwaniem, ale określ go.

Nie zakładaj, że wyrażenie regularne jest zakotwiczone niejawnie. Np. Jeśli używasz Pythona, załóż, że wyrażenie regularne jest używane z, re.searcha nie z re.match. Wyrażenie regularne nie musi pasować do całego łańcucha. Musi tylko dopasować co najmniej jeden podciąg (który może być pusty) dla prawidłowych rozwiązań i nie dawać żadnych dopasowań dla nieprawidłowych rozwiązań.

Możesz założyć, że wejście będzie zawsze ciągiem 81 cyfr dodatnich.

To jest wyrażenie regularne, więc wygrywa najkrótszy wyrażenie regularne w bajtach. Jeśli Twój język wymaga ograniczników (zwykle /.../) do oznaczania wyrażeń regularnych, nie licz samych ograniczników. Jeśli Twoje rozwiązanie wymaga modyfikatorów, dodaj jeden bajt na modyfikator.

Przypadki testowe

Ważne tablice:

123456789456789123789123456231564897564897231897231564312645978645978312978312645
725893461841657392396142758473516829168429537952378146234761985687935214519284673
395412678824376591671589243156928437249735186738641925983164752412857369567293814
679543182158926473432817659567381294914265738283479561345792816896154327721638945
867539142324167859159482736275398614936241587481756923592873461743615298618924375
954217683861453729372968145516832497249675318783149256437581962695324871128796534
271459386435168927986273541518734269769821435342596178194387652657942813823615794
237541896186927345495386721743269158569178432812435679378652914924813567651794283
168279435459863271273415986821354769734692518596781342615947823387526194942138657
863459712415273869279168354526387941947615238138942576781596423354821697692734185
768593142423176859951428736184765923572389614639214587816942375295837461347651298
243561789819327456657489132374192865926845317581673294162758943735914628498236571
243156789519847326687392145361475892724918653895263471152684937436729518978531264
498236571735914628162758943581673294926845317374192865657489132819327456243561789
978531264436729518152684937895263471724918653361475892687392145519847326243156789
341572689257698143986413275862341957495726831173985426519234768734869512628157394

Nieprawidłowe tablice:

519284673725893461841657392396142758473516829168429537952378146234761985687935214
839541267182437659367158924715692843624973518573864192298316475941285736456729381
679543182158926473432817659567381294914256738283479561345792816896154327721638945
867539142324167859159482736275398684936241517481756923592873461743615298618924375
754219683861453729372968145516832497249675318983147256437581962695324871128796534
271459386435168927986273541518734269769828435342596178194387652657942813823615794
237541896186927345378652914743269158569178432812435679495386721924813567651794283
168759432459613278273165984821594763734982516596821347615437829387246195942378651
869887283619214453457338664548525781275424668379969727517385163319223917621449519
894158578962859187461322315913849812241742157275462973384219294849882291119423759
123456789456789123564897231231564897789123456897231564312645978645978312978312645
145278369256389147364197258478512693589623471697431582712845936823956714931764825
243561789829317456657489132374192865916845327581673294162758943735924618498236571
243156789529847316687392145361475892714928653895263471152684937436719528978531264
498236571735924618162758943581673294916845327374192865657489132829317456243561789
978531264436719528152684937895263471714928653361475892687392145529847316243156789
342571689257698143986413275861342957495726831173985426519234768734869512628157394
345678192627319458892451673468793521713524986951862347179246835534187269286935714
341572689257698143986413275862341957495726831173985426519234768734869512628517394

W innych przypadkach testowych możesz użyć tego skryptu CJam, który pobiera prawidłową tablicę jako dane wejściowe i losowo tasuje ją, aby uzyskać nową prawidłową tablicę (format wejściowy nie ma znaczenia, o ile zawiera tylko cyfry i opcjonalnie białe znaki).

Jeśli regex jest zgodny ze smakiem .NET, możesz go przetestować online za pomocą Retina. Prawidłowe rozwiązanie powinno wydrukować 0dla nieprawidłowych kart i pewną dodatnią liczbę całkowitą dla prawidłowych kart. Aby uruchomić wszystkie przypadki testowe jednocześnie, użyj tego szablonu i wstaw wyrażenie regularne w drugim wierszu. Jeśli potrzebujesz modyfikatorów wyrażenia regularnego, dodaj a `do wyrażenia regularnego i umieść przed nim standardowe litery modyfikatora.

Ruby regex, 71 78 73 bajtów

^(?!.*(?=(.))(.{9}+|(.(?!.{9}*$))+|(?>.(?!.{3}*$)|(.(?!.{27}*$)){7})+)\1)

Naprawdę nie znam Rubiego, ale najwyraźniej nie narzeka na kaskadowe kwantyfikatory.

Wypróbuj tutaj.

Wyrażenie regularne .NET, 79 78 75 lub 77 bajtów

Ponieważ Martin uważa, że ​​jest to możliwe ... Ale sądzę, że po prostu uwzględni te zmiany.

^(?!(.)+((.{9})+|(?>(.{9})+
|.)+|(?((...)*
)(?>(.{27})+
|.){7}|.)+)(?<=\1))

Wymaga końcowego znaku nowej linii w danych wejściowych do pracy. Nie jestem pewien, czy wolno mi to zrobić (prawdopodobnie nie).

Wypróbuj tutaj.

Wersja rozsądna 77 bajtów:

^(?!(.)+((.{9})+|((?!(.{9})*$).)+|(?((...)*$)((?!(.{27})*$).){7}|.)+)(?<=\1))

Dzięki Neil za wskazanie błędu w mojej poprzedniej wersji i odłożenie 1 bajtu (dla (...)*).

Wypróbuj tutaj.

PCRE, 77 78 bajtów

^(?!.*(?=(.))((.{9})+|(.(?!(?3)*$))+|(?(?=.(...)*$)(.(?!(.{27})*$)){7}|.)+)\1)

Tylko dla kompletności.

Wypróbuj tutaj.

Inna wersja, również 78 bajtów:

^(?!.*(?=(.))((.{9})+|(.(?!(?3)*$))+|(?>.(?!(...)*$)|(.(?!(.{27})*$)){7})+)\1)

Wypróbuj tutaj.

Wyjaśnienie

^(?!.*                    # Match a string that doesn't contain the pattern,
                          # at any position.
  (?=(.))                 # Capture the next character.
  (
    (.{9})+               # Any 9*n characters. The next character is in
                          # the same column as the captured one.
  |
    (.(?!(.{9})*$))+      # Any n characters not followed by a positions 9*m
                          # to the end. The next character is in the same row
                          # as the captured one.
  |
    (                     # Any n occasions of...
    ?(.(...)*$)           # If it is at a position 3*k+1 to the end:
      (.(?!(.{27})*$)){7} # Then count 7*m characters that are not followed
                          # by a position 27*j to the end,
    |
      .                   # Else count any character.
    )+                    # The next character is in the same block as the
                          # captured one.
  )
  \1                      # Fail if the next character is the captured character.
)

PCRE, 117 119 130 133 147 bajtów

^(?!(.{27})*(...){0,2}(.{9})?.?.?(.).?.?(?=(?2)*$).{6,8}(?3)?\4.{0,17}(?1)*$|.*(.)(.{8}(?3)*|((?!(?3)*$)(|.(?7))))\5)

Powinien również działać w smakach Python, Java itp. Teraz z rekurencją! I funkcja „rekurencji” używana nierekurencyjnie dla „podprogramów”, o której całkowicie zapomniałam, dopóki nie musiałam użyć faktycznej rekurencji.

Wyrażenie regularne .NET, 8339 bajtów

Tak, wiem, że moje rozwiązanie jest bardzo naiwne, ponieważ Martin powiedział mi, że zrobił to w około 130 bajtów. W rzeczywistości adres URL do wypróbowania online jest tak długi, że nie mogłem znaleźć skracacza URL, który by go zaakceptował.

(code removed, since it's so long nobody will read it here, 
and it made the post take forever to load. Just use the "Try it online" link.)

Poniższy link nie działa w IE, ale działa w Chrome i Firefox.

Wypróbuj online - wszystkie przypadki testowe naraz, z pomocą!`na początku, nieuwzględnione w liczbie bajtów.

Oto skrypt Pythona, którego użyłem do wygenerowania go (kod poniżej):

R=range(0,9)
S=range(1,10)

o = ""

# validate rows
T = "(?=.{%s,%s}%s)"
for j in R:
    for i in S:
        o += T % (9*j,9*(j+1)-1, i)

# validate columns
# "(?=(.{%s}|.{%s}|.{%s}|.{%s}|.{%s}|.{%s}|.{%s}|.{%s}|.{%s})%s)"
T = "(?=("+"|".join([".{%s}"]*9)+")%s)"
for j in R:
    for i in S:
        o += T % (j,j+9,j+18,j+27,j+36,j+45,j+54,j+63,j+72, i)

# validate boxes
# (?=.{0,2}1|.{9,11}1|.{18,20}1)(?=.{3,5}1|.{12,14}1|.{21,23}1)
# (?=.{27,29}1|.{36,38}1|.{45,47}1)
T = ".{%s,%s}%s"
for i in S:
    for x in (0,27,54):
        for y in (0,3,6):
            o += "(?="+"|".join(T % (x+y+z,x+y+z+2, i) for z in (0,9,18))+")"

o += ".{81}"

o = o.replace(".{0}","").replace(",80}",",}")
print(o)

Wyrażenie regularne .NET, 121 bajtów

^(?!(.{27})*(.{9})?(...){0,2}.?.?(.).?.?(?=(...)*$)(.{9})?.{6,8}\4.{0,17}(.{27})*$|.*(?=(.))((.{9})+|(.(?!(.{9})*$))+)\8)

Wyjaśnienie:

^(?!                     Invert match (because we're excluding duplicates)
 (.{27})*                Skip 0, 3 or 6 rows
 (.{9})?                 Optionally skip another row
 (...){0,2}              Skip 0, 3 or 6 columns
 .?.?(.).?.?(?=(...)*$)  Choose any of the next three cells
 (.{9})?                 Optionally skip another row
 .{6,8}\4                Match any of the three cells below
 .{0,17}(.{27})*$        As long as they're from the same square
|                        OR
 .*(?=(.))(              Choose any cell
  (.{9})+                Skip at least one row
 |                       or
  (.                     Skip cells
   (?!(.{9})*$)          Without reaching the end of the row
  )+                     For at least one cell (i.e. the cell chosen above)
 )\8)                    Match the chosen cell to the next cell
)

PCRE, 3579 bajtów

Absolutnie okropne rozwiązanie brutalnej siły. Negatywne spojrzenie dotyczy ahoy!

Spędziłem o wiele za dużo czasu, żeby to porzucić, więc oto, na miłość potomną.

Z drugiej strony, jeśli Sudoku nagle zacznie używać innego zestawu 9 znaków, nadal będzie działać, tak myślę ...

http://pastebin.com/raw/CwtviGkC

Nie wiem, jak obsługiwać Retinę, ale możesz też wkleić ją na https://regex101.com lub podobną i będzie pasować.

Kod Ruby używany do generowania wyrażenia regularnego:

# Calculate the block you're in
def block(x)
    x /= 3
    x + x%3 - x%9
end

81.times do |i|
    row, col = i.divmod(9)
    neg = []
    neg += (0...col).map {|e| 9*row + e + 1}
    neg += (0...row).map {|e| 9*e + col + 1}
    neg += (0...i).map {|e| e + 1 if block(e) == block(i)}.compact
    neg = neg.uniq.sort.map {|e| "\\#{e}"}
    if neg.size > 0
        print "(?!#{neg.join '|'})"
    end
    print "(.)"
end

Smak rubinowy, 75 74 bajtów

Dzięki jimmy23013 za oszczędność 1 bajtu.

^(?!(.{9}*(.|(.)){,8}|.*(\g<2>.{8})*|.{27}?.{3}?(\g<2>{3}.{6}){,2}.?.?)\3).

Sprawdź to tutaj.

Teraz, gdy wreszcie został pokonany, mogę udostępnić własne rozwiązanie. :) W tym procesie odkryłem interesującą (może nową?) Technikę wyrażenia regularnego ( (.|(.)){,8}\3część), która prawdopodobnie byłaby nie do pobicia w przypadkach, w których nie można jej połączyć z innymi częściami wyrażenia regularnego (jak miało to miejsce w odpowiedzi jimmy23013) .

Wyjaśnienie

Podobnie jak inne krótkie odpowiedzi, używam negatywnego spojrzenia w przód, które wyszukuje duplikaty w wierszach, kolumnach lub blokach. Podstawowym składnikiem rozwiązania jest:

(.|(.))...\3

Zauważ, że \3jest ponownie wykorzystywany między trzema różnymi alternatywami (wszystkie wykorzystują grupę 3do wykrywania duplikatów).

Ta grupa po lewej stronie (która jest grupą 2zawierającą grupę 3) jest używana dla dowolnej pozycji, która może zawierać pierwszą połowę zduplikowanej cyfry (w grupie, która nie może zawierać zduplikowanych cyfr). To ...jest coś, co prowadzi nas do następnej pozycji, w której taka cyfra może wystąpić (jeśli to konieczne) i \3próbuje znaleźć drugą połowę duplikatu za pomocą odwołania wstecznego. Powodem tego jest cofanie się. Gdy silnik po raz pierwszy pasuje (.|(.)), po prostu użyje go za .każdym razem i niczego nie zarejestruje. Teraz \3koniec się nie udaje. Ale teraz silnik będzie stopniowo próbował używać (.)zamiast .pojedynczych dopasowań. Ostatecznie, jeśli istnieje duplikat, znajdzie kombinację gdzie(.)był ostatnio używany na pierwszej cyfrze duplikatu (tak, że przechwytywanie nie jest później zastępowane), a następnie wykorzystuje trochę więcej, .aby wypełnić lukę do odwołania wstecznego. Jeśli istnieje duplikat, powrót do niego zawsze go znajdzie.

Spójrzmy na trzy różne części, w których jest to używane:

.{9}*(.|(.)){,8}

To sprawdza duplikaty w niektórych wierszach. Najpierw przechodzimy do dowolnego wiersza za pomocą .{9}*. Następnie dopasowujemy do 8 znaków (tj. Cokolwiek w tym wierszu oprócz ostatniej cyfry) przy użyciu opcjonalnego duplikatu przechwytywania i próbujemy znaleźć \3po nim.

.*(\g<2>.{8})*

Szuka duplikatów w niektórych kolumnach. Po pierwsze, pamiętaj, że \g<2>jest to wywołanie podprogramu, więc jest to to samo, co:

.*((.|(.)).{8})*

gdzie dwie grupy, które właśnie wstawiliśmy, są nadal nazywane 2i 3.

Tutaj po .*prostu przeskakuje tak daleko, jak to konieczne (wystarczy dopasować do 8 znaków tutaj, ale to kosztuje więcej bajtów). Następnie grupa zewnętrzna dopasowuje jeden pełny wiersz (który może owijać się w dwa fizyczne rzędy) na raz, opcjonalnie przechwytując pierwszy znak. \3Będzie szukał zaraz po tym, co zapewnia pionowe wyrównanie pomiędzy wychwytywania i Wsteczne.

Na koniec sprawdzanie bloków:

.{27}?.{3}?(\g<2>{3}.{6}){,2}.?.?

Ponownie \g<2>jest to wywołanie podprogramu, więc jest to to samo, co:

.{27}?.{3}?((.|(.)){3}.{6}){,2}.?.?

Aby zweryfikować bloki, pamiętaj, że ponieważ sprawdziliśmy już wszystkie wiersze i kolumny, musimy tylko sprawdzić cztery z bloków 3x3. Kiedy wiemy, że wszystkie wiersze i kolumny, a także te bloki 3x3 są poprawne:

XX.
XX.
...

Wiemy zatem, że w pozostałych blokach nie może być duplikatów. Dlatego sprawdzam tylko te cztery bloki. Ponadto zauważ, że nie musimy szukać duplikatów w tym samym rzędzie bloku 3x3. Wystarczy znaleźć pierwszą połowę duplikatu w jednym rzędzie i wyszukać drugą połowę z rzędu dalej.

Teraz w przypadku samego kodu najpierw przeskakujemy na początek jednego z czterech bloków za pomocą .{27}?.{3}?(opcjonalnie pomiń trzy rzędy, opcjonalnie pomiń trzy kolumny). Następnie próbujemy dopasować do dwóch wierszy bloku 3x3 tą samą sztuczką, której użyliśmy wcześniej dla wierszy:

(.|(.)){3}.{6}

Zezwalamy, ale nie wymagamy przechwytywania żadnej z 3 komórek w bieżącym wierszu bloku 3x3, a następnie przechodzimy do następnego rzędu za pomocą .{6}. Na koniec próbujemy znaleźć duplikat w jednej z 3 komórek wiersza, w którym się znajdujemy:

.?.?

I to wszystko.

Wyrażenia regularne JavaScript, 532 530 481 463 znaków

Sprawdź poprawność wierszy:

/^((?=.{0,8}1)(?=.{0,8}2)(?=.{0,8}3)(?=.{0,8}4)(?=.{0,8}5)(?=.{0,8}6)(?=.{0,8}7)(?=.{0,8}8)(?=.{0,8}9).{9})+$/

Sprawdź poprawność kolumn:

/^((?=(.{9}){0,8}1)(?=(.{9}){0,8}2)(?=(.{9}){0,8}3)(?=(.{9}){0,8}4)(?=(.{9}){0,8}5)(?=(.{9}){0,8}6)(?=(.{9}){0,8}7)(?=(.{9}){0,8}8)(?=(.{9}){0,8}9).){9}/

Sprawdź poprawność kwadratu od pierwszego znaku:

/(?=.?.?(.{9}){0,2}1)(?=.?.?(.{9}){0,2}2)(?=.?.?(.{9}){0,2}3)(?=.?.?(.{9}){0,2}4)(?=.?.?(.{9}){0,2}5)(?=.?.?(.{9}){0,2}6)(?=.?.?(.{9}){0,2}7)(?=.?.?(.{9}){0,2}8)(?=.?.?(.{9}){0,2}9)/

Ustaw podgląd na początek kwadratu:

/^(((?=)...){3}.{18})+$/

I całe wyrażenie:

/^(?=((?=.{0,8}1)(?=.{0,8}2)(?=.{0,8}3)(?=.{0,8}4)(?=.{0,8}5)(?=.{0,8}6)(?=.{0,8}7)(?=.{0,8}8)(?=.{0,8}9).{9})+$)(?=((?=(.{9}){0,8}1)(?=(.{9}){0,8}2)(?=(.{9}){0,8}3)(?=(.{9}){0,8}4)(?=(.{9}){0,8}5)(?=(.{9}){0,8}6)(?=(.{9}){0,8}7)(?=(.{9}){0,8}8)(?=(.{9}){0,8}9).){9})(((?=.?.?(.{9}){0,2}1)(?=.?.?(.{9}){0,2}2)(?=.?.?(.{9}){0,2}3)(?=.?.?(.{9}){0,2}4)(?=.?.?(.{9}){0,2}5)(?=.?.?(.{9}){0,2}6)(?=.?.?(.{9}){0,2}7)(?=.?.?(.{9}){0,2}8)(?=.?.?(.{9}){0,2}9)...){3}.{18})+$/

Pasuje do całego ciągu.

Testuj w Javascript ES6:

r = /^(?=((?=.{0,8}1)(?=.{0,8}2)(?=.{0,8}3)(?=.{0,8}4)(?=.{0,8}5)(?=.{0,8}6)(?=.{0,8}7)(?=.{0,8}8)(?=.{0,8}9).{9})+$)(?=((?=(.{9}){0,8}1)(?=(.{9}){0,8}2)(?=(.{9}){0,8}3)(?=(.{9}){0,8}4)(?=(.{9}){0,8}5)(?=(.{9}){0,8}6)(?=(.{9}){0,8}7)(?=(.{9}){0,8}8)(?=(.{9}){0,8}9).){9})(((?=.?.?(.{9}){0,2}1)(?=.?.?(.{9}){0,2}2)(?=.?.?(.{9}){0,2}3)(?=.?.?(.{9}){0,2}4)(?=.?.?(.{9}){0,2}5)(?=.?.?(.{9}){0,2}6)(?=.?.?(.{9}){0,2}7)(?=.?.?(.{9}){0,2}8)(?=.?.?(.{9}){0,2}9)...){3}.{18})+$/
;`123456789456789123789123456231564897564897231897231564312645978645978312978312645
725893461841657392396142758473516829168429537952378146234761985687935214519284673
395412678824376591671589243156928437249735186738641925983164752412857369567293814
679543182158926473432817659567381294914265738283479561345792816896154327721638945
867539142324167859159482736275398614936241587481756923592873461743615298618924375
954217683861453729372968145516832497249675318783149256437581962695324871128796534
271459386435168927986273541518734269769821435342596178194387652657942813823615794
237541896186927345495386721743269158569178432812435679378652914924813567651794283
168279435459863271273415986821354769734692518596781342615947823387526194942138657
863459712415273869279168354526387941947615238138942576781596423354821697692734185
768593142423176859951428736184765923572389614639214587816942375295837461347651298`
.split`
`.every(r.test.bind(r))
&&
`519284673725893461841657392396142758473516829168429537952378146234761985687935214
839541267182437659367158924715692843624973518573864192298316475941285736456729381
679543182158926473432817659567381294914256738283479561345792816896154327721638945
867539142324167859159482736275398684936241517481756923592873461743615298618924375
754219683861453729372968145516832497249675318983147256437581962695324871128796534
271459386435168927986273541518734269769828435342596178194387652657942813823615794
237541896186927345378652914743269158569178432812435679495386721924813567651794283
168759432459613278273165984821594763734982516596821347615437829387246195942378651
869887283619214453457338664548525781275424668379969727517385163319223917621449519
894158578962859187461322315913849812241742157275462973384219294849882291119423759
123456789456789123564897231231564897789123456897231564312645978645978312978312645
145278369256389147364197258478512693589623471697431582712845936823956714931764825`
.split`
`.every(s => !r.test(s))