Skip to content

Instantly share code, notes, and snippets.

@JokerQyou
Created June 13, 2014 07:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • 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
#coding=utf-8
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):
try:
self.known.add(gidx)
self.grids[gidx] = set([value])
for uidx in uindexs[gidx]:
self.units[uidx].remove(value)
self.changes.add(uidx)
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:
return
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]
gset.intersection_update(uset)
length = len(gset)
if length == 0:
self.conflict = True
return
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:
map[value].append(gidx)
for value, gidxs in map.iteritems():
length = len(gidxs)
if length == 1:
self.set(gidxs[0], value)
elif length == 0:
self.conflict = True
return
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:
break
gset = self.grids[gindex]
for i in list(gset):
sudoku = self.clone()
sudoku.set(gindex, gset.pop())
yield sudoku
def solove(self):
self.detect()
if len(self.known) == 81:
return self
if self.conflict:
return
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()
sudoku.load(fen)
return sudoku.solove()
if __name__ == '__main__':
import time
t = time.time()
for i in xrange(1000):
main()
print time.time() - t
@JokerQyou
Copy link
Author

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