shayelkin · May 21, 2019 18:18 · May 21, 2019 · May 21, 2019 · May 21, 2019
diff --git a/soduko.py b/soduko.py
@@ -33,16 +33,15 @@ def popcount(i):
 assert 1 == popcount(1)
 assert 2 == popcount(3)
 
-def print_puzzle(bp):    
-    space_per_cell = max(popcount(c) for c in bp)
-
+def pprint_puzzle(bp):    
+    space_per_cell = max(popcount(c) for c in bp)    
     for row in xrange(9):        
         print " ".join("".join(str_cell(bp[row*9+col])).center(space_per_cell) for col in xrange(9))
 
 def neighbour_indices(i):    
     row, col = i / 9, i % 9
-    return set([(row*9 + c) for c in xrange(9) if c != col] +\
-               [(r*9 + col) for r in xrange(9) if r != row] +\
+    return set([(row*9 + c) for c in xrange(9)] +\
+               [(r*9 + col) for r in xrange(9)] +\
                [(r+3*(row/3))*9 + (c+3*(col/3)) for r in xrange(3) for c in xrange(3)]) - set([row*9+col])
 
 neighbours = [neighbour_indices(i) for i in xrange(81)]
@@ -60,7 +59,7 @@ def validate_cell(bp, i):
     return True
 
 def validate_puzzle(bp):  
-    "Validate that the matrix does not invalidate the Soduko property"
+    "Validate that the whole matrix does not invalidate the Soduko property"
     # Not as optimal as it could be, but only used for asserting the result    
     return all(validate_cell(bp, i) for i in xrange(81))
 

diff --git a/soduko.py2 → soduko.py b/soduko.py2 → soduko.py
@@ -1,6 +1,6 @@
 #!/usr/bin/env python2
 """
-Soduko solver. Everybody writes one at one time or other.
+Soduko solver. Everybody writes one.
 """   
 
 sample = "003020600900305001001806400008102900700000008006708200002609500800203009005010300"

diff --git a/soduko.py2 b/soduko.py2
@@ -0,0 +1,101 @@
+#!/usr/bin/env python2
+"""
+Soduko solver. Everybody writes one at one time or other.
+"""   
+
+sample = "003020600900305001001806400008102900700000008006708200002609500800203009005010300"
+
+all_bits = int('1'*9,2)
+
+def load_puzzle(s):
+    return [all_bits if c in '0.' else 1 << (int(c)-1) for c in s]    
+
+sample_puzzle = load_puzzle(sample)
+assert 81 == len(sample_puzzle)
+
+def itr_digits(b):
+    return (d for d in xrange(9) if b & (1 << d))
+
+def itr_bits(b):
+    return (1 << d for d in xrange(9) if b & (1 << d))
+
+def str_cell(b):
+    return "".join([str(d+1) for d in itr_digits(b)])
+
+def popcount(i):
+    count = 0
+    while i:
+        i &= (i - 1) # clear the least signficiant bit set
+        count += 1
+    return count 
+
+assert 0 == popcount(0)
+assert 1 == popcount(1)
+assert 2 == popcount(3)
+
+def print_puzzle(bp):    
+    space_per_cell = max(popcount(c) for c in bp)
+
+    for row in xrange(9):        
+        print " ".join("".join(str_cell(bp[row*9+col])).center(space_per_cell) for col in xrange(9))
+
+def neighbour_indices(i):    
+    row, col = i / 9, i % 9
+    return set([(row*9 + c) for c in xrange(9) if c != col] +\
+               [(r*9 + col) for r in xrange(9) if r != row] +\
+               [(r+3*(row/3))*9 + (c+3*(col/3)) for r in xrange(3) for c in xrange(3)]) - set([row*9+col])
+
+neighbours = [neighbour_indices(i) for i in xrange(81)]
+
+assert all((i not in neighbours[i]) for i in xrange(81))
+
+def validate_cell(bp, i):
+    "Validate that the value(s) in cell i don't invalidate the Soduko property"
+    if 0 == popcount(bp[i]):
+        return False
+    if 1 == popcount(bp[i]):
+        for j in neighbours[i]:
+            if 1 == popcount(bp[j]) and bp[i] & bp[j]:
+                return False
+    return True
+
+def validate_puzzle(bp):  
+    "Validate that the matrix does not invalidate the Soduko property"
+    # Not as optimal as it could be, but only used for asserting the result    
+    return all(validate_cell(bp, i) for i in xrange(81))
+
+assert validate_puzzle(sample_puzzle)
+
+def is_solved(bp):
+    return bp and all((1 == popcount(x)) for x in bp) and validate_puzzle(bp)
+
+assert (not is_solved(sample_puzzle))
+
+def set_value_and_prune(bp, i, bit_v):
+    if 1 != popcount(bit_v):
+        raise ValueError("Only set a single value at a time")
+
+    bp[i] = bit_v
+    mask = (~bp[i] & all_bits)
+    for j in neighbours[i]:   
+        bp[j] = bp[j] & mask
+        if 0 == popcount(bp[j]):
+            return False             
+    return bp
+
+def solve(bp):
+    try:
+        c_i, c_val, _ = min(((i, x, popcount(x)) for (i, x) in enumerate(bp) if 1 < popcount(x)), key=lambda t: t[2])
+    except ValueError:
+        return bp if validate_puzzle(bp) else False
+
+    for bit in itr_bits(c_val):                
+        maybe_solution = set_value_and_prune(bp[:], c_i, bit)
+        if maybe_solution:
+            maybe_solution = solve(maybe_solution) 
+            if maybe_solution:
+                return maybe_solution
+
+    return False
+
+assert is_solved(solve(sample_puzzle))
No results found