Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!newsfeed.freenet.ag!news2.euro.net!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.004 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'python.': 0.04; 'subject:based': 0.07; 'url:py': 0.07; 'url:pypi': 0.08; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:80.91.229.12': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'received:lo.gmane.org': 0.09; 'thrown': 0.09; 'forgotten': 0.15; 'looked': 0.15; 'answer,': 0.16; 'outputs': 0.16; 'solver': 0.16; 'solves': 0.16; 'url:ics': 0.16; 'wrote:': 0.16; 'solution.': 0.17; 'trace': 0.18; 'written': 0.19; 'header:In-Reply-To:1': 0.22; 'code': 0.25; 'url:edu': 0.27; 'column': 0.28; 'assuming': 0.28; 'pure': 0.32; 'url:ie': 0.32; 'thanks': 0.32; 'implement': 0.32; "can't": 0.32; 'header:User- Agent:1': 0.33; 'to:addr:python-list': 0.33; 'match': 0.33; 'from:addr:yahoo.co.uk': 0.34; 'someone': 0.34; 'header:X -Complaints-To:1': 0.34; 'help,': 0.35; 'sets': 0.35; "i'll": 0.35; 'url:python': 0.36; 'run': 0.37; 'but': 0.37; 'received:org': 0.37; 'another': 0.37; 'some': 0.38; 'possible.': 0.39; "i'd": 0.39; 'url:org': 0.39; 'received:78': 0.39; 'subject:: ': 0.39; 'did': 0.39; 'to:addr:python.org': 0.40; 'full': 0.62; 'back': 0.62; 'frank': 0.64; 'arrive': 0.66; 'exact': 0.68; 'tough': 0.82; 'reasoning': 0.84; 'received:as13285.net': 0.84; 'row,': 0.84; 'sum': 0.88; 'look.': 0.93 X-Injected-Via-Gmane: http://gmane.org/ To: python-list@python.org From: Blockheads Oi Oi Subject: Re: constraint based killer sudoku solver performance improvements Date: Fri, 27 Jan 2012 07:47:35 +0000 References: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Gmane-NNTP-Posting-Host: host-78-147-24-139.as13285.net User-Agent: Mozilla/5.0 (Windows NT 6.0; rv:9.0) Gecko/20111222 Thunderbird/9.0.1 In-Reply-To: X-Antivirus: avast! (VPS 120126-2, 26/01/2012), Outbound message X-Antivirus-Status: Clean X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 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: 36 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1327650437 news.xs4all.nl 6900 [2001:888:2000:d::a6]:39264 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:19521 On 27/01/2012 06:57, Frank Millman wrote: > > "Blockheads Oi Oi" wrote: > >> I have a working program based on [1] that sets up all different >> constraints for each row, column and box and then sets exact sum >> constraints for each cage. It'll run in around 0.2 secs for a simple >> problem, but a tough one takes 2 hours 45 minutes. I did some research >> into improving the performance and found [2] but can't work out how to >> implement the constraints given. Can someone please help, assuming that >> it's even possible. >> >> [1] http://pypi.python.org/pypi/python-constraint/1.1 >> [2] http://4c.ucc.ie/~hsimonis/sudoku.pdf > > I don't have an answer, but are you aware of this - > > http://www.ics.uci.edu/~eppstein/PADS/Sudoku.py > > It is a sudoko solver written in pure python. > > I don't know what you call a tough problem, but this one solves the hardest > one I have thrown at it in the blink of an eye. It also outputs a full trace > of the reasoning it used to arrive at a solution. > > Frank Millman > I'd looked at this years back and forgotten all about it so thanks for the reminder :) Some of the code names directly match ideas given in my [2] above so I'll take another look. -- Cheers. Mark Lawrence.