Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.007 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'python.': 0.02; 'languages.': 0.04; 'perl,': 0.07; 'excluding': 0.09; 'grid': 0.09; 'python': 0.11; 'language,': 0.12; 'thread': 0.14; '(excluding': 0.16; 'code),': 0.16; 'expressions,': 0.16; 'finite': 0.16; 'hierarchy': 0.16; 'language': 0.16; 'wrote:': 0.18; 'pointed': 0.19; 'seems': 0.21; 'machine': 0.22; 'question': 0.24; 'least': 0.26; 'header:In-Reply-To:1': 0.27; 'message- id:@mail.gmail.com': 0.30; "d'aprano": 0.31; 'perl': 0.31; 'steven': 0.31; 'languages': 0.32; 'regular': 0.32; 'quite': 0.32; 'open': 0.33; 'fri,': 0.33; 'could': 0.34; "can't": 0.35; 'knows': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'combination': 0.36; 'should': 0.36; 'somebody': 0.38; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'that,': 0.38; 'embedded': 0.39; 'to:addr:python.org': 0.39; 'how': 0.40; 'ground': 0.60; 'mar': 0.68; 'covers': 0.68; 'nobody': 0.68; '2015': 0.84; 'solvable': 0.84; 'stronger': 0.84; 'stronger.': 0.84 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=XVikuLKEzmMoeKimwvWlixcGVEZXoPBZQ9BcriyZj10=; b=jxhDLD6Wx2TW22P6GqtalY1FNI8W50nTnqvwlyzMm7HJ7jKU3pf4tOqxVDPjB3HRtA FvNU7xVK7jWdwih4OWAR0TAigrxNiqJluB9K0/gNQnZUskGnfpHZKP5xSWTPgeAQYOnN sMBVPBxlseWAsw5gH5hwoeqV4UPszsxI3rTNNiOh6m0m5RYiGYyHzskNXWpyD5nnh2Mu iZLkMGG8XSKR42p373i1S4Gaa+Qdc9uWSLbJiWmumVEvMiIKJbKsECdFvYXgAMiKzhGm mLBzU7mDNMEPKiF642j2/FSrkslXHnciVRwG+MTOt5wVtCd5T1gL5Vy2D25obc3+I+Dc nPxw== X-Received: by 10.66.164.98 with SMTP id yp2mr41424281pab.114.1427531135636; Sat, 28 Mar 2015 01:25:35 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <551606a9$0$13009$c3e8da3$5496439d@news.astraweb.com> References: <87r3sdnw5t.fsf@elektro.pacujo.net> <87fv8sndw1.fsf@elektro.pacujo.net> <551557B3.5090102@davea.name> <87twx6lf15.fsf@elektro.pacujo.net> <55156489.9050200@davea.name> <551606a9$0$13009$c3e8da3$5496439d@news.astraweb.com> From: Ian Kelly Date: Sat, 28 Mar 2015 02:24:55 -0600 Subject: Re: Sudoku solver To: Python Content-Type: text/plain; charset=UTF-8 X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.19 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 19 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1427531143 news.xs4all.nl 2879 [2001:888:2000:d::a6]:43838 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:88211 On Fri, Mar 27, 2015 at 7:40 PM, Steven D'Aprano 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.