Regex Golf: Verify a Sudoku Solution

Question

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.

Answer 1

Ruby regex, 71 78 73 bytes

^(?!.*(?=(.))(.{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, 79 78 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.
)

Answer 2

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.

Answer 3

.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)

Answer 4

.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
)

Answer 5

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

Answer 6

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.

Answer 7

Javascript regex, 532 530 481 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))