Sudoku solver

[Steven D'Aprano]

On Sat, 28 Mar 2015 01:19 am, Chris Angelico wrote:


> Part of me is quaking in fear... the other part looking on in morbid
> fascination. Can you build a regexp that proves a Sudoku grid
> solvable?

Perl's regular expressions can run arbitrary code using ?{...} which
technically makes them Turing Complete and capable of solving any problem
you can solve in any other language. However the code is written in Perl,
so I call that cheating :-)

Excluding that, the consensus seems to be that Perl's regexes are stronger
than Chomsky regular expressions, but nobody quite knows how much stronger.
It's likely that they are at least as powerful as context-free grammars,
but not as powerful as a Turing machine (excluding embedded Perl code), but
that covers a lot of ground in the hierarchy of language power:

http://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarchy

So it's an open question as to whether or not you could prove a Sudoku grid
solvable using a Perl regex. Python regexes are less powerful than Perl's,
so if you can't do it in Perl, you can't do it in Python.

But, for what its worth, you can test for prime numbers using a regex:

re.match(r'^1?$|^(11+?)\1+$', '1'*n)

matches if the number n is composite, i.e. it's not a prime.

http://code.google.com/p/pyprimes/source/browse/src/pyprimes/awful.py

My intuition is that given a completed Sudoku grid, you should be able to
prove that it is valid using a Python regex, but given an incomplete one,
probably *not* prove that it is solvable. But I can't justify that in any
objective way.




-- 
Steven