Thursday, July 13, 2006

shortest sudoku solver

bearophile sent me a link to this really cool program:

def r(a):i=a.find('0');~i or exit(a);[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import*;r(argv[1])

apparently it's a sudoku solver (couldn't you guess?). here's more information about it:
ShortestSudokuSolver

unfortunately, it mixes integers and strings ((i-j).. or a[j]) and arbitrary-size arithmetic (5**18), both of which are currently not supported by shed skin. the arbitrary-size arithmetic could be supported in this case, but I rewrote it for now. here's a version that works with shed skin CVS:

def r(a):
i=a.find('0')
if not ~i: print a; exit()
[m in [a[j] for j in range(81) if not (i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)] or r(a[:i]+m+a[i+1:]) for m in '3814697265625']
from sys import *;r(argv[1])

it's 211 characters, versus the 178 of the one above, so that's not too bad :) and it becomes 18 times faster here.

6 comments:

matthanlon said...

I believe the expression
'%d'%5**18
is just a clever way to produce a string containing all the digits 1 through 9. You could replace it in your version with
'123456789'
and save a few characters with the same results.

srepmub said...

lol. it looks like they save one character that way?? :D thanks for letting me know.

srepmub said...

this looks nicer, imo:

str(5**18)

and it would be more straightforward for shed skin to 'constant fold' the large number away..

Daivd said...

Why the silly '%d'% ? Backquotes are two characters less and look nicer. `5**18` Or am I missing something?

Daivd said...

Aha.. my suggestion will only work in a 64-bit environment. For those unfortunate 32-bitters, `5**18` prints an L at the end.

Bruce Fredman said...

Hi,
We at Chessboss.com strongly believe in necessity of chess to increase both knowledge and understanding. It is unfortunate that the oldest game in the world (Chess) has a very little fan base, ChessBoss.com aims to change that. We understand the importance of blogs and the information made available on them. We are working towards building a strong fan base around our FREE chess server to better increase the use of Chess online. Your blog seems to have a large viewing public and seems to hold great information which I would love to make available to my viewing public.

I have included the code for the ChessBoss.com banner within the body of this email along with textual link information. I would be pleased to offer you the ChessBoss.com featured blogger badge to post on your site, recognizeing your blog as a leading contributor to the Chess community. Thank you for your great work and dedication, we look forward to your response!Please reply me back with subject line of your Url to avoid spam and to make sure YOU get the Award.

Thank you.