Sudoku solver

[Ian Kelly]

On Fri, Mar 27, 2015 at 7:40 PM, Steven D'Aprano
<steve+comp.lang.python at pearwood.info> wrote:
> 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:

Intuitively, I should think that the combination of recursive
subpatterns and assertions would make them able to generate at least
the context-sensitive languages.

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

As somebody else in the thread pointed out, the set of all valid
Sudoku grids is a finite language, and all finite languages are
regular. QED.