Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path: <davea@davea.name>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.008
X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'python.': 0.02; 'stops': 0.07; 'overflow': 0.09; 'stack.': 0.09; 'python': 0.11; 'bug': 0.12; 'posted': 0.15; 'entries.': 0.16; 'exit()': 0.16; 'parameter.': 0.16; 'received:74.208.4.195': 0.16; 'say)': 0.16; 'supplied': 0.16; 'wrote:': 0.18; 'stack': 0.19; 'header:User- Agent:1': 0.23; 'entries': 0.24; "i've": 0.25; 'pass': 0.26; 'least': 0.26; 'header:In-Reply-To:1': 0.27; 'function': 0.29; 'code': 0.31; 'crash': 0.31; 'depth': 0.31; 'run': 0.32; 'running': 0.33; 'problem': 0.35; 'described': 0.36; 'explains': 0.36; 'found.': 0.36; 'example,': 0.37; 'too': 0.37; 'sometimes': 0.38; 'filled': 0.38; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'to:addr:python.org': 0.39; 'even': 0.60; 'tell': 0.60; 'first': 0.61; 'such': 0.63; 'soon': 0.63; 'maximum': 0.63; 'more': 0.64; '2000': 0.65; 'received:74.208': 0.68
Date: Fri, 29 Mar 2013 18:11:08 -0400
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130308 Thunderbird/17.0.4
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Sudoku
References: <e45b8b75-ff89-4ee1-9ada-bfda3d06d05d@googlegroups.com> <9dla2a-kql.ln1@satorlaser.homedns.org> <5ce10a13-be58-4548-85df-e1d865d3304e@googlegroups.com> <mailman.3857.1364445382.2939.python-list@python.org> <f160e316-e2f6-4314-827e-9d48007f7f70@googlegroups.com> <mailman.3946.1364556269.2939.python-list@python.org> <17da5afc-7a9b-40ea-a544-6012dfeef3ce@googlegroups.com>
In-Reply-To: <17da5afc-7a9b-40ea-a544-6012dfeef3ce@googlegroups.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Provags-ID: V02:K0:R53Z73ES4GgaS0dBASs42gLc4xz6FmGZIiBcRKOSxG/ 9SVxSxjvzGkasjTuQ3jaV49LUo8zyb10D7D1q8M/PR5nMyIqN1 dut5h8CWJw2w+ak+Gmv09F8rw10J/fhe1oS6+55vnZ1FXfuZc/ UP8/Xzgm9aFETLcIjl3WqL3wjMQHIggUSeTwFlXdheXSuVcapT X+PqRUMsPuBnegdWzC2PXO+0q/K78wzaX9k+L+4b9qyfKY2X92 UaLru5b621RC5tuwq7l8Os8XLkua0BGYOwcJcXwYh4MhYmo8sG nKokhLx1sw8juMF3UnPTQVLL/uSkJjGmv4mYeg65yK1AIvx5Q= =
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.3970.1364595086.2939.python-list@python.org>
Lines: 28
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1364595086 news.xs4all.nl 6865 [2001:888:2000:d::a6]:54621
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:42286

On 03/29/2013 05:47 PM, Eric Parry wrote:
>
>>   <SNIP>
>>
> That explains why the program keeps running after a solution is found.

A recursive function can be designed to find all solutions, in which 
case it would (as you say) keep running.

The function you posted in the first place uses exit() to avoid keeping 
running.  It stops as soon as a solution is found.

Sometimes a problem cannot be solved in the number of stack entries 
supplied by Python.  So even though such a function will terminate, it 
may crash first if the problem is too big.  Example, the factorial 
problem I described earlier, if you pass it 2000 as a parameter.  If 
this is a problem, one can tell the Python to give you more stack entries.

Given a 9x9 matrix, and at least some of them filled in, the maximum 
depth your code can use is less than 81.  So it won't get a stack 
overflow in any implementation of Python I've seen.  Perhaps in an 8051.

Sometimes a bug in such a function will cause it to run indefinitely, 
and/or to overflow the stack.  I don't see such a bug in this function.


-- 
DaveA