Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Help deciphering a code

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
elioncho

Joined: 04 Apr 2008
Posts: 1
:

Items
PostPosted: Fri Apr 04, 2008 6:41 am    Post subject: Help deciphering a code Reply with quote

Hi, I have this python code for a sudoku solver. Can anyone help me understand it line by line. Thanks
Code:


03:
04: Usage: python sudoku.py filename
05:
06: where `filename' contains a textual representation of the sudoku, with unknown
07: values replaced by zeros. Something like:
08:
09: 5 3 0 0 7 0 0 0 0
10: 6 0 0 1 9 5 0 0 0
11: 0 9 8 0 0 0 0 6 0
12: 8 0 0 0 6 0 0 0 3
13: 4 0 0 8 0 3 0 0 1
14: 7 0 0 0 2 0 0 0 6
15: 0 6 0 0 0 0 2 8 0
16: 0 0 0 4 1 9 0 0 5
17: 0 0 0 0 8 0 0 7 9
18:
19: would be valid.
20:
21: This implements a _very_ simple backtracking recursive solver, using in-place,
22: iterative value replacement -- this problem is NP-hard anyway. Please note that
23: the solver will always find the first solution assuming there is one, then stop.
24: """
25: class Sudoku(list):
26:     def __init__(self, filename):
27:         list.__init__(self,
28:             [d[i*9:(i+1)*9]
29:              for i in range(9)
30:              for d in [[int(e) for e in file(filename,'r').read().split()]]])
31:     def __repr__(self):
32:         return '\n'.join([' '.join([str(c) for c in r]) for r in self])
33:     def grp(self, i, j):
34:         return set((self[i][:] +
35:                     [self[k][j] for k in range(9)] +
36:                     [self[k][l]
37:                      for k in range(i/3*3, i/3*3+3)
38:                      for l in range(j/3*3, j/3*3+3)]))
39:     def next(self, i, j): return (i*9+j+1)/9, (i*9+j+1)%9
40:     def loop(self, i, j):
41:         if i<9>=9: break
45:             yield i, j
46:     
47: def solve(s, k=0, l=0):
48:     """Backtracking solver"""
49:     for i, j in s.loop(k, l):
50:         if s[i][j] is 0:
51:             for val in set(range(1, 10)).difference(s.grp(i, j)):
52:                 s[i][j]=val
53:                 if solve(s,*s.next(i, j)): return s
54:             s[i][j]=0
55:             return
56:     return s
57:
58: # Now, let's roll
59: from sys import argv
60: print solve(Sudoku(argv[1]))
[/code]
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron