Regex Golf: Verify a Sudoku Solution

Write a regex which matches any valid sudoku solution and doesn't match any invalid sudoku solution. The input is an unrolled version of the sudoku, i.e. there are no line delimiters. E.g. the following board:

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


would be given as:

725893461841657392396142758473516829168429537952378146234761985687935214519284673


The rules are probably common knowledge by now, but just in case... a sudoku board is valid if and only if:

• Each row contains the digits from 1 to 9 exactly once.
• Each column contains the digits from 1 to 9 exactly once.
• Each of the nine 3x3 subgrids contains the digits from 1 to 9 exactly once.

Rules

Your answer should consist of a single regex, without any additional code (except, optionally, a list of regex modifiers required to make your solution work). You must not use features of your language's regex flavour that allow you to invoke code in the hosting language (e.g. Perl's e modifier).

You can use any regex flavour which existed before this challenge, but please specify the flavour.

Do not assume that the regex is anchored implicitly. E.g. if you're using Python, assume that your regex is used with re.search and not with re.match. Your regex does not need to match the entire string. It just needs to match at least one substring (which may be empty) for valid solutions and yield no matches for invalid solutions.

You may assume that the input will always be a string of 81 positive digits.

This is regex golf, so the shortest regex in bytes wins. If your language requires delimiters (usually /.../) to denote regular expressions, don't count the delimiters themselves. If your solution requires modifiers, add one byte per modifier.

Test Cases

Valid boards:

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


Invalid boards:

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


For further test cases, you can use this CJam script which takes a valid board as input and randomly shuffles it to give a new valid board (input format irrelevant as long as it contains only digits and optionally whitespace).

If your regex is compatible with the .NET flavour, you can test it online using Retina. A valid solution should print 0 for invalid boards and some positive integer for valid boards. To run all test cases at once, use this template and insert the regex on the second line. If you need regex modifiers, prepend a  to the regex and put the standard modifier letters in front of it.

• – Level River St Apr 21 '16 at 21:51
• If only this were [code-bowling], lol. – mbomb007 Apr 21 '16 at 23:59
• Wait...If we are using Python, we can only use regular expressions, and nothing else? Also, how big is each board? Is there a specific size? If not, how should we extract each board out of the clump of digits under valid boards? – R. Kap Apr 22 '16 at 6:47
• @R.Kap Regardless of which flavour you're using, you should submit only the regex (and possibly some modifiers), yes. Each input is exactly 81 digits and represents a full board. (Each line in the test cases is a separate board.) – Martin Ender Apr 22 '16 at 6:49
• I wrote a script to solve simple sudoku's in SQL. I am sure it can be rewritten for this question. However SQL doesn't have much REGEX. Does that disqualify the answer ? (Script would probably be a bit below 400 characters) – t-clausen.dk Oct 11 '16 at 7:11

^(?!.*(?=(.))(.{9}+|(.(?!.{9}*$))+|(?>.(?!.{3}*$)|(.(?!.{27}*$)){7})+)\1)  I don't really know Ruby but apparently it doesn't complain about cascaded quantifiers. Try it here. .NET regex, 7978 75 or 77 bytes Because Martin thinks this is possible... But I guess he will just incorporate these changes too. ^(?!(.)+((.{9})+|(?>(.{9})+ |.)+|(?((...)* )(?>(.{27})+ |.){7}|.)+)(?<=\1))  Requires a trailing newline in the input to work. I'm not sure whether I'm allowed to do this (probably not). Try it here. The 77 byte sane version: ^(?!(.)+((.{9})+|((?!(.{9})*$).)+|(?((...)*$)((?!(.{27})*$).){7}|.)+)(?<=\1))


Thanks Neil for pointing out the error in my previous version and golfing off 1 byte (for the (...)*).

Try it here.

PCRE, 77 78 bytes

^(?!.*(?=(.))((.{9})+|(.(?!(?3)*$))+|(?(?=.(...)*$)(.(?!(.{27})*$)){7}|.)+)\1)  Just for completeness. Try it here. Another version, also 78 bytes: ^(?!.*(?=(.))((.{9})+|(.(?!(?3)*$))+|(?>.(?!(...)*$)|(.(?!(.{27})*$)){7})+)\1)


Try it here.

Explanation

^(?!.*                    # 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. )  • Wow nice job. I only got it to 83 in .NET and had to switch to PCRE for 78. I have no doubt you'll end up beating that as well. :) – Martin Ender Apr 22 '16 at 21:41 • @MartinBüttner Yep. – Fund Monica's Lawsuit Apr 22 '16 at 21:56 • I thought my use of lookahead to beat @MartinBüttner by (at the time) 4 bytes was neat but you've taken that to the next level. – Neil Apr 22 '16 at 23:46 • Sorry, but this doesn't detect whether the cells at (1, 2) and (2, 1) are the same, and similarly for all other cells in squares where the duplicate is below and to the left. – Neil Apr 23 '16 at 0:43 • @MartinBüttner I just realized that I can translate my second PCRE version into Ruby... I guess you could post your answer now... – jimmy23013 Apr 24 '16 at 14:54 PCRE, 117 119 130 133 147 bytes ^(?!(.{27})*(...){0,2}(.{9})?.?.?(.).?.?(?=(?2)*$).{6,8}(?3)?\4.{0,17}(?1)*$|.*(.)(.{8}(?3)*|((?!(?3)*$)(|.(?7))))\5)


Should also work in Python, Java, etc. flavors. Now with recursion! And the "recursion" feature used non-recursively for "subroutines", which I totally forgot about until I had to use actual recursion.

• Cool idea - avoid repeats instead of matching norepeats! – Qwertiy Apr 21 '16 at 23:13
• It's a shame you can't write .{27}*. – Neil Apr 22 '16 at 9:50
• Bah, I'd golfed your 133 byte solution down to 121 bytes only to find that you'd rewritten it, but here it is anyway: ^(?!(.{27})*(.{9})?(...){0,2}.?.?(.).?.?(?=(...)*$)(.{9})?.{6,8}\4.{0,17}(.{27})*$|.*(.)((.{9})+|((?!(.{9})*$).)+)(<=\8)) – Neil Apr 22 '16 at 10:37 • @Neil What flavor is that? PCRE or others I know don't allow backreferences in a lookbehind. – feersum Apr 22 '16 at 10:56 • @Neil (<=\8) doesn't look like valid syntax (it's missing a ?). Also, the only flavour I know that supports backreferences in lookbehinds is .NET. – Martin Ender Apr 22 '16 at 11:12 .NET regex, 8339 bytes Yes, I know my solution is very naive, since Martin told me he did it in like 130 bytes. In fact, the URL to try it online is so long that I couldn't find a URL shortener that would accept it. (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.)  The below link does not work in IE, but does work in Chrome and Firefox. Try it online - All test cases at once, with the help of ! at the beginning, not included in byte count. Here's the Python script I used to generate it (code below): 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)  • I'm rooting for you – Martijn Apr 21 '16 at 23:39 • Know what's funny? The try it online link will crash IE because it's too long :P – cat Apr 22 '16 at 2:10 • @cat That's why IE's only real purpose is allowing the user to download Firefox (or Chromium). – Byte Commander Apr 22 '16 at 7:06 • @cat It doesn't crash IE11 on Windows 8.1 though, although the Regex does not get processed properly. – Nzall Apr 22 '16 at 7:27 • @cat It doesn't crash my IE 11 on Windows 7. It just truncates the URL. – mbomb007 Apr 22 '16 at 15:41 .NET regex, 121 bytes ^(?!(.{27})*(.{9})?(...){0,2}.?.?(.).?.?(?=(...)*$)(.{9})?.{6,8}\4.{0,17}(.{27})*$|.*(?=(.))((.{9})+|(.(?!(.{9})*$))+)\8)


Explanation:

^(?!                     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 )  • Nice, your combination of rows and columns is pretty clever. That saves 4 bytes on my own solution. :) – Martin Ender Apr 22 '16 at 11:55 PCRE, 3579 bytes An absolutely terrible brute force solution. Negative lookbehinds ahoy! I spent way too much time on this to abandon it, so here it is, for posterity's sake. On the bright side, if Sudoku suddenly starts using a different set of 9 characters, this'll still work, I guess... http://pastebin.com/raw/CwtviGkC I don't know how to operate Retina, but you can also paste it into https://regex101.com or similar and it'll match. Ruby code used to generate the regex: # 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  Ruby flavour, 75 74 bytes Thanks to jimmy23013 for saving 1 byte. ^(?!(.{9}*(.|(.)){,8}|.*(\g<2>.{8})*|.{27}?.{3}?(\g<2>{3}.{6}){,2}.?.?)\3).  Test it here. Now that it's finally beaten, I can share my own solution. :) I discovered an interesting (maybe new?) regex technique in the process (the (.|(.)){,8}\3 part), which would probably be unbeatable in cases where this can't be combined with other parts of the regex (as was the case in jimmy23013's answer). Explanation Like the other short answers I'm using a negative lookahead which searches for duplicates in rows, columns or blocks. The basic building block of the solution is this: (.|(.))...\3  Note that the \3 is reused between three different alternatives (which all use group 3 for duplicate detection). That group on the left (which is group 2, containing group 3) is used for any position that can contain the first half of a duplicate digit (within a group that must not contain duplicate digits). Then ... is something that gets us the the next position where such a digit might occur (if necessary) and \3 tries to find the second half of the duplicate via backreference. The reason this works is backtracking. When the engine first matches (.|(.)) it will simply use . every time and not capture anything. Now the \3 at the end fails. But now the engine will gradually try using (.) instead of . for individual matches. Ultimately, if there's a duplicate, it will find the combination where (.) was last used on the first digit of the duplicate (such that the capture isn't overwritten later), and then uses some more . to bridge the gap to the backreference. If there is a duplicate, backtracking will always find it. Let's look at the three different parts where this is used: .{9}*(.|(.)){,8}  This checks for duplicates in some row. First we skip to any row with .{9}*. Then we match up to 8 characters (i.e. anything in that row except the last digit) using the optional duplicate capture and try to find the \3 after it. .*(\g<2>.{8})*  This looks for duplicates in some column. First, note that \g<2> is a subroutine call, so this is the same as: .*((.|(.)).{8})*  where the two groups we've just inserted are still referred to as 2 and 3. Here, the .* simply skips as far as necessary (it would be sufficient to match up to 8 characters here, but that costs more bytes). Then the outer group matches one complete row (which may wrap across two physical rows) at a time, optionally capturing the first character. The \3 will be looked for right after this, which ensures vertical alignment between the capture and the backreference. Finally, checking the blocks: .{27}?.{3}?(\g<2>{3}.{6}){,2}.?.?  Again, the \g<2> is a subroutine call, so this is the same as: .{27}?.{3}?((.|(.)){3}.{6}){,2}.?.?  To verify the blocks, note that since we've already checked all the rows and columns, we only need to check four of the 3x3 blocks. When we know that all rows and columns as well as these 3x3 blocks are correct: XX. XX. ...  Then we know that there can't possibly be duplicates in the remaining blocks. Hence I'm only checking these four blocks. Furthermore, note that we don't have to look for duplicates within the same row of a 3x3 block. It's enough to find the first half of the duplicate in one row and search for the second half in a row further down. Now for the code itself, we first skip to the beginning of one of the four blocks with .{27}?.{3}? (optionally skip three rows, optionally skip three columns). Then we try to match up to two of the rows of the 3x3 block with the same trick we used for the rows earlier: (.|(.)){3}.{6}  We allow but don't require capturing of any of the 3 cells in the current row of the 3x3 block and then skip to the next row with .{6}. Finally, we try to find a duplicate in either of the 3 cells of the row we end up on: .?.?  And that's it. • 74: ^(?!(.*((.|(.)).{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). – jimmy23013 Apr 24 '16 at 16:43 • @jimmy23013 I was actually using the \4() trick in an earlier version for the 3x3 blocks, but ended up getting rid of it, because it was longer. :D – Martin Ender Apr 24 '16 at 16:46 • @jimmy23013 The 73 one doesn't check the last row though: 341572689257698143986413275862341957495726831173985426519234768734869512628517394 – Martin Ender Apr 24 '16 at 16:48 Javascript regex, 532530481 463 chars Validate rows: /^((?=.{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})+/


Validate columns:

/^((?=(.{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}/


Validate square from its first char:

/(?=.?.?(.{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)/


Set preview to start of the square:

/^(((?=)...){3}.{18})+$/  And the whole expression: /^(?=((?=.{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})+$/  Matches the whole string. Test in 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))

• I think columns should be much easier than rows, so I find it curious that your column regex is longer than your row one. – Peter Taylor Apr 21 '16 at 22:56
• @PeterTaylor, they have the same structure, but for columns I have to skip 9 chars instead of 1, so . gets into (.{9}) with brackets because of the next {0,8}. Why do you think columns should be shorter? – Qwertiy Apr 21 '16 at 22:59
• @PeterTaylor, yep, columns would've been simplier if I guessed to check negation. – Qwertiy Apr 21 '16 at 23:22
• @SuperJedi224, why javascript? I expect this regex to be valid everywhere. – Qwertiy Apr 21 '16 at 23:34
• @Qwertiy While your regex should work in many flavors, it relies on lookaheads (not available in Lua or OCaml, for example). It is also an invalid basic or extended regular expression, which use an entirely different syntax. It is best to pick on flavor for the validity claim, even if the solution works in many others. – Dennis Apr 22 '16 at 0:41