Created
June 13, 2014 07:03
-
-
Save JokerQyou/5e986e822425f91eff1b to your computer and use it in GitHub Desktop.
A Sudoku solver in Python2, can't find the original author
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Could somebody make some explanations in the code? I'm quite confused about it.