Sudoku resolver in Python

A simple Sudoku resolver written in Python.

Sorry for the Italian code comments. Please add a comment below if you don't get parts of the algorithm.

# -*- coding: cp1252 -*-

# esercizio di pdp07 SUDOKU


import copy

#list of all numbers

num = ['1','2','3','4','5','6','7','8','9']
        

class sset(set):
	def rem(self, x):
		if x in self: self.remove(x)


	#adds elements of list
	def addlist(self,l):
		for a in l:
			self.add(a)

	def compl(self):
		s1=sset(num)
		for k in self:
			s1.remove(k)
		return s1

# define no repetitions
def alldiff(l):
        s = set(l)
        return len(l)==len(s)


#defines the squares from the upperleft angle
def sqg(a,b):
	a1 = a/3*3    
	b1 = b/3*3 
	l = [[i,j] for i in range(a1,a1+3) for j in range(b1,b1+3)]
	return l



class sudo:

	def __init__(self):
		self.boa = [['#' for i in range(0,9)] for j in range(0,9)]
		self.indices = (0,0)
		self.pos = [[sset(num) for i in range(0,9)] for j in range(0,9)]
		self.free = 81
	
	def __iter__(self):
		return(self)

	def setchange(self, sudo2):
		self.pos = sudo2.getpos()
		self.boa = sudo2.getboa()
		self.free = sudo2.getfree()

	def getpos(self):
		return self.pos

	def getboa(self):
		return self.boa

	def getfree(self):
		return self.free

	def add(self, i, j, d):
		if((self.boa[i][j]=='#') and (d in self.pos[i][j])):
			self.boa[i][j] = d
			self.remx(j, d)
			self.remy(i, d)
			self.pos[i][j]=sset([])
			self.remsqr(i, j, d)
			self.free = self.free - 1
		else:
			# print "eccezione add"
			raise ValueError


	def remx(self, j, d):
		for i in range(0, 9):
			self.pos[i][j].rem(d)
                

	def remy(self, i, d):
		for j in range(0, 9):
			self.pos[i][j].rem(d)

	def remsqr(self, i, j, d):
		for l in sqg(i,j):
  			self.pos[l[0]][l[1]].rem(d)

	def dcopy(self):
		b1=sudo()
		b1.boa = copy.deepcopy(self.boa)
		b1.indices = (0,0)
		return b1

	def minpos(self):
		m = 0
		n = 0
		for i in range(0,9):
			for j in range(0,9):
				#print "boa: " + repr(self.boa[i][j])
				if ((self.boa[i][j]=='#') and ((len(self.pos[i][j])< len(self.pos[m][n]) or (self.boa[m][n]!='#')))):
					m = i
					n = j
					
		return (m,n)

	def move(self):
		if (self.getfree() == 0):
			print "risolto"
			return 
		(m, n) = self.minpos()
		#print repr(m) + " " + repr(n)
		if(len(self.pos[m][n])==0):
			#print "eccezione"
			raise ValueError
		else:
			#print "lunghezza min pos" + repr(len(self.pos[m][n]))
			if(len(self.pos[m][n])==1):
				#print "pop: " + repr(self.pos[m][n].pop())
				r = self.pos[m][n].pop()
				self.pos[m][n].add(r)
				self.add(m, n, r)
				self.move()
			else:
				for d in self.pos[m][n]:
					#print repr(d)
					s = copy.deepcopy(self)
					s.add(m, n, d)
					#print "move prima if:" + repr(s)
					if(s.solve()==1):
						#print "fatto s.solve() s e :" + repr(s)
						self.setchange(s)
						return
				raise ValueError

	def solve(self):
		try:
			self.move()
			return 1
		except ValueError:
			return 0

	def __repr__(self):
		val = reduce(lambda a,b: a+b, 
			  [repr(self.boa[k])+"\n" for k in range(9)])
		posz = ""
		for i in range(0,9):
			for j in range(0,9):
				a = self.pos[i][j]
				posz += "(" + repr(j) + "," + repr(i) + ")"  + repr(self.pos[i][j]) + "\n"
		return "val:\n" + val + "possibilita:\n" + posz



#print repr(table)
print "Sudoku\n"
print "Per inserire un nuovo sudoku da console, digita: 1>"
print "Per risolvere un sudoku da default, digita:      2>"
print "Per terminare digita                             0\n>"

c=raw_input("Cosa vuoi fare?> ")
while (c!="0"):
	if c=="1":
		read="y"
		table=sudo()
		while (read!="n"):
			try:
				val = raw_input("Dimmi un numero da inserire> ")
				x = int(raw_input("Posizione X> "))
				y = int(raw_input("Posizione Y> "))
				table.add(y, x, val)
				read = raw_input("Continuare? [y/n]>")
			except ValueError:
				print "Riprova, numero gia presente o posizione occupata!"
		print repr(table)
		table.solve()
		print repr(table)
	else:
		if c=="2":
			try:
				table2=sudo()
				print repr(table2)
				table2.add(0,3,'9')
				table2.add(0,4,'8')
				table2.add(0,5,'3')
				table2.add(0,8,'7')
				table2.add(1,1,'8')
				table2.add(1,6,'4')
				table2.add(1,7,'1')
				table2.add(2,0,'5')
				table2.add(2,1,'6')
				table2.add(2,2,'7')
				table2.add(2,6,'8')
				table2.add(3,6,'9')
				table2.add(3,7,'3')
				table2.add(4,0,'7')
				table2.add(4,3,'5')
				table2.add(4,4,'2')
				table2.add(4,5,'9')
				table2.add(4,8,'1')
				table2.add(5,1,'9')
				table2.add(5,2,'4')
				table2.add(6,2,'1')
				table2.add(6,6,'2')
				table2.add(6,7,'8')
				table2.add(6,8,'6')
				table2.add(7,1,'5')
				table2.add(7,2,'9')
				table2.add(7,7,'7')
				table2.add(8,0,'8')
				table2.add(8,3,'7')
				table2.add(8,4,'4')
				table2.add(8,5,'1')
			except ValueError:
				print "ERRORE, numero gia presente o posizione occupata!"
			print repr(table2)
			table2.solve()
			print repr(table2)


	print "Per inserire un nuovo sudoku da console, digita: 1>"
	print "Per risolvere un sudoku da default, digita:      2>"
	print "Per terminare digita                             0\n>"
	c=raw_input("Cosa vuoi fare?> ")