Skip to content

Instantly share code, notes, and snippets.

Created June 13, 2014 07:03
Show Gist options
  • Save JokerQyou/5e986e822425f91eff1b to your computer and use it in GitHub Desktop.
Save JokerQyou/5e986e822425f91eff1b to your computer and use it in GitHub Desktop.
A Sudoku solver in Python2, can't find the original author
#!/usr/bin/env python
units = ([[j for j in range(81) if j%9 == i] for i in range(9)] +
[[j for j in range(81) if j/9 == i] for i in range(9)] +
[[j for j in range(81) if (j%9)/3+(j/27)*3 == i] for i in range(9)])
uindexs = [[j for j, u in enumerate(units) if i in u] for i in range(81)]
class Sudoku(object):
conflict = False
def set(self, gidx, value):
self.grids[gidx] = set([value])
for uidx in uindexs[gidx]:
except KeyError:
self.conflict = True
def load(self, s):
self.grids = [set(range(1, 10)) for i in range(81)]
self.units = [set(range(1, 10)) for i in range(27)]
self.known = set()
self.changes = set()
for gidx, c in enumerate(s):
if c in '123456789':
self.set(gidx, int(c))
def detect(self):
if self.conflict:
while self.changes:
while self.changes:
uidx = self.changes.pop()
uset = self.units[uidx]
for gidx in units[uidx]:
if gidx not in self.known:
gset = self.grids[gidx]
length = len(gset)
if length == 0:
self.conflict = True
elif length == 1:
self.set(gidx, gset.pop())
for uidx, uset in enumerate(self.units):
map = dict((value, []) for value in uset)
for gidx in units[uidx]:
for value in self.grids[gidx]:
if value in map:
for value, gidxs in map.iteritems():
length = len(gidxs)
if length == 1:
self.set(gidxs[0], value)
elif length == 0:
self.conflict = True
def guess(self):
count = 10
gindex = -1
for gidx, gset in enumerate(self.grids):
if gidx not in self.known:
if len(gset) < count:
gindex = gidx
count = len(gset)
if count == 2:
gset = self.grids[gindex]
for i in list(gset):
sudoku = self.clone()
sudoku.set(gindex, gset.pop())
yield sudoku
def solove(self):
if len(self.known) == 81:
return self
if self.conflict:
for sudoku in self.guess():
sudoku = sudoku.solove()
if sudoku is not None:
return sudoku
def clone(self):
sudoku = Sudoku()
sudoku.grids = [set(i) for i in self.grids]
sudoku.units = [set(unit) for unit in self.units]
sudoku.known = set(self.known)
sudoku.changes = set()
return sudoku
def __str__(self):
seq = ''.join(str(i)[5] for i in self.grids)
return '\n'.join(seq[i:i+9] for i in range(0, 81, 9))
__repr__ = __str__
def main():
fen = '..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9'
sudoku = Sudoku()
return sudoku.solove()
if __name__ == '__main__':
import time
t = time.time()
for i in xrange(1000):
print time.time() - t
Copy link

Could somebody make some explanations in the code? I'm quite confused about it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment