"""Sudoku.py
PADS-based command-line application for generating and solving Sudoku puzzles.
These puzzles are given as a 9x9 grid of cells, some of which are filled with
digits in the range 1-9. The task is to fill the remaining cells in such a
way that each row of the grid, each column of the grid, and each of nine 3x3
squares into which the grid is partitioned, all have one copy of each of the
nine digits.
A proper Sudoku puzzle must have a unique solution, and it should be possible
to reach that solution by a sequence of logical deductions without trial and
error. To the extent possible, we strive to keep the same ethic in our
automated solver, by mimicking human rule-based reasoning, rather than
resorting to brute force backtracking search.
D. Eppstein, July 2005.
"""
import random
import sys
from optparse import OptionParser
from BipartiteMatching import imperfections
from StrongConnectivity import StronglyConnectedComponents
from Repetitivity import NonrepetitiveGraph
from Wrap import wrap
from Not import Not
from TwoSatisfiability import Forced
from SVG import SVG
class BadSudoku(Exception): pass
# raised when we discover that a puzzle has no solutions
# ======================================================================
# Bitmaps and patterns
# ======================================================================
digits = range(1,10)
class group:
def __init__(self, i, j, x, y, name):
mask = 0
h,k = [q for q in range(4) if q != i and q != j]
for w in range(3):
for z in range(3):
mask |= 1 << (x*3**i + y*3**j + w*3**h + z*3**k)
self.mask = mask
self.pos = [None]*9
self.name = "%s %d" % (name,x+3*y+1)
cols = [group(0,1,x,y,"column") for x in range(3) for y in range(3)]
rows = [group(2,3,x,y,"row") for x in range(3) for y in range(3)]
sqrs = [group(1,3,x,y,"square") for x in range(3) for y in range(3)]
groups = sqrs+rows+cols
neighbors = [0]*81
for i in range(81):
b = 1<* min(census):
continue # block already filled, can't use this row now
FullPlacementGraph[node][node|b] = 1<<(9*i+sum(census)) # found edge
census[i//3] += 1
searchPlacements(node|b,census) # recurse
census[i//3] -= 1
searchPlacements(0,[0,0,0])
# ======================================================================
# Human-readable names for puzzle cells
# ======================================================================
cellnames = [None]*81
for row in range(9):
for col in range(9):
cellnames[row*9+col] = ''.join(['R',str(row+1),'C',str(col+1)])
def andlist(list,conjunction="and"):
"""Turn list of strings into English text."""
if len(list) == 0:
return "(empty list!)"
if len(list) == 1:
return list[0]
elif len(list) == 2:
return (' '+conjunction+' ').join(list)
else:
return ', '.join(list[:-1]+[conjunction+' '+list[-1]])
def namecells(mask,conjunction="and"):
"""English string describing a sequence of cells."""
names = []
while mask:
bit = mask &~ (mask - 1)
names.append(cellnames[unmask[bit]])
mask &=~ bit
return andlist(names,conjunction)
def pathname(cells):
return '-'.join([cellnames[c] for c in cells])
def plural(howmany,objectname):
if howmany == 1:
return objectname
else:
return "%d %ss" % (howmany,objectname)
# ======================================================================
# State for puzzle solver
# ======================================================================
class Sudoku:
"""
Data structure for storing and manipulating Sudoku puzzles.
The actual rules for solving the puzzles are implemented
separately from this class.
"""
def __init__(self,initial_placements = None):
"""
Initialize a new Sudoku grid.
If an argument is given, it should either be a sequence of 81
digits 0-9 (0 meaning a not-yet-filled cell), or a sequence
of (digit,cell) pairs.
The main state we use for the solver is an array contents[]
of 81 cells containing digits 0-9 (0 for an unfilled cell)
and an array locations[] indexed by the digits 1-9, containing
bitmasks of the cells still available to each digit.
We also store additional fields:
- progress is a boolean, set whenever one of our methods
changes the state of the puzzle, and used by step() to tell
whether one of its rules fired.
- rules_used is a set of the rule names that have made progress.
- pairs is a dictionary mapping bitmasks of pairs of cells to
lists of digits that must be located in that pair, as set up
by the pair rule and used by other later rules.
- bilocation is a NonrepetitiveGraph representing paths and
cycles among bilocated digits, as constructed by the bilocal
rule and used by the repeat and conflict rules.
- bivalues is a NonrepetitiveGraph representing paths and
cycles among bivalued cells, as constructed by the bivalue
rule and used by the repeat and conflict rules.
- otherbv maps pairs (cell,digit) in the bivalue graph to the
other digit available at the same cell
- logstream is a stream on which to log verbose descriptions
of the steps made by the solver (typically sys.stderr), or
None if verbose descriptions are not to be logged.
- steps is used to count how many solver passes we've made so far.
- original_cells is a bitmask of cells that were originally nonempty.
- assume_unique should be set true to enable solution rules
based on the assumption that there exists a unique solution
- twosat should be set true to enable a 2SAT-based solution rule
"""
self.contents = [0]*81
self.locations = [None]+[(1<<81)-1]*9
self.rules_used = set()
self.progress = False
self.pairs = None
self.bilocation = None
self.logstream = False
self.steps = 0
self.original_cells = 0
self.assume_unique = False
self.twosat = False
if initial_placements:
cell = 0
for item in initial_placements:
try:
digit = int(item)
except TypeError:
digit,cell = item
if digit:
self.place(digit,cell)
self.original_cells |= 1 << cell
cell += 1
def __iter__(self):
"""
If we are asked to loop over the items in a grid
(for instance, if we pass one Sudoku instance as the argument
to the initialization of another one) we simply list the
known cell contents of the grid.
"""
return iter(self.contents)
def mark_progress(self):
"""Set progress True and clear fields that depended on old state."""
self.progress = True
self.pairs = None
def log(self,items,explanation=None):
"""
Send a message for verbose output.
Items should be a string or list of strings in the message.
If explanation is not None, it is called as a function and
the results appended to items.
"""
if not self.logstream:
return
if isinstance(items,str):
items = [items]
if explanation:
if isinstance(explanation,str) or isinstance(explanation,list):
x = explanation
else:
x = explanation()
if isinstance(x,str):
x = [x]
else:
x = []
text = ' '.join([str(i) for i in items+x])
for line in wrap(text):
self.logstream.write(line+'\n')
self.logstream.write('\n')
self.logstream.flush()
def place(self,digit,cell,explanation=None):
"""Change the puzzle by filling the given cell with the given digit."""
if digit != int(digit) or not 1 <= digit <= 9:
raise ValueError("place(%d,%d): digit out of range" % (digit,cell))
if self.contents[cell] == digit:
return
if self.contents[cell]:
self.log(["Unable to place",digit,"in",cellnames[cell],
"as it already contains",str(self.contents[cell])+"."])
raise BadSudoku("place(%d,%d): cell already contains %d" %
(digit,cell,self.contents[cell]))
if (1<* 1:
that = "would leave too few remaining cells" \
" to place those digits."
if expls:
expls[-1] += ','
if force == forces[-1]:
expls[-1] += ' and'
forcedigs = [str(x) for x in force]
forcedigs.sort()
forcemask = 0
for dig in force:
for cell in force[dig]:
forcemask |= 1< 2;
# in this case multiple cycles go through the same edge
# and cell must be filled with the digit labeling that edge.
# But for simplicity's sake we ignore that possibility;
# it doesn't happen very often and when it does the repetitive
# cycle rule will find it instead.
mask = 1< 1:
for d in grid.choices(cell):
T[(cell,d)] = [Not((cell,e))
for e in grid.choices(cell)
if d != e]
T[Not((cell,d))] = []
# If a cell has value d, its neighbors can't have the same value
for cell in range(81):
if len(grid.choices(cell)) > 1:
for neighbor in range(81):
if cell != neighbor and (1<")
for a in range(3):
print("")
for b in range(3):
print("")
for c in range(3):
print("")
for d in range(3):
row = 3*a+c
col = 3*b+d
cell = 9*row+col
if grid.contents[cell]:
print('' % grid.contents[cell])
else:
print('')
print("")
print("")
print("")
print("")
return False
def svg_format(grid):
svg = SVG(274+274j,sys.stdout)
svg.group(style={"fill":"none", "stroke":"black", "stroke-width":"1.5"})
svg.rectangle(2+2j,272+272j)
for i in [3,6]:
pos = 30*i+2
svg.segment(2+pos*1j,272+pos*1j)
svg.segment(pos+2j,pos+272j)
svg.ungroup()
svg.group(style={"fill":"none", "stroke":"black", "stroke-width":"0.5"})
for i in [1,2,4,5,7,8]:
pos = 30*i+2
svg.segment(2+pos*1j,272+pos*1j)
svg.segment(pos+2j,pos+272j)
svg.ungroup()
svg.group(style={"font-family":"Times", "font-size":"24", "fill":"black",
"text-anchor":"middle"})
for row in range(9):
for col in range(9):
cell = row*9+col
if grid.contents[cell]:
svg.text(str(grid.contents[cell]),30*col+17+30j*row+25j)
svg.ungroup()
svg.close()
return False
output_formats = {
"text": text_format,
"txt": text_format,
"t": text_format,
"numeric": numeric_format,
"num": numeric_format,
"n": numeric_format,
"html": html_format,
"h": html_format,
"svg": svg_format,
"s": svg_format,
}
# ======================================================================
# Backtracking search for all solutions
# ======================================================================
def all_solutions(grid, fastrules = True):
"""Generate sequence of completed Sudoku grids from initial puzzle."""
while True:
# first try the usual non-backtracking rules
try:
while step(grid,fastrules): pass
except BadSudoku:
grid.log("A contradiction was found,"
" so this branch has no solutions.")
return # no solutions
# if they finished off the puzzle, there's only one solution
if grid.complete():
grid.log("A solution to the puzzle has been found.")
yield grid
return
# find a cell with few remaining possibilities
def choices(c):
ch = grid.choices(c)
if len(ch) < 2: return (10,0,0)
return (len(ch),c,ch[0])
L,c,d = min([choices(c) for c in range(81)])
# try it both ways
branch = Sudoku(grid)
grid.log("Failed to progress, "
"creating a new backtracking search branch.")
branch.logstream = grid.logstream
branch.steps = grid.steps
branch.original_cells = grid.original_cells
branch.place(d,c,"The backtracking search will try this placement"
" first. Then, after returning from this branch,"
" it will try preventing this placement.")
for sol in all_solutions(branch,fastrules):
yield sol
grid.log(["Returned from backtracking branch; undoing placement of",
d,"in",cellnames[c],"and all subsequent decisions."])
grid.rules_used.update(branch.rules_used)
grid.rules_used.add("backtrack")
grid.steps = branch.steps
grid.unplace(d,1< 1 and c or []
while True:
try:
while not grid.complete():
d,c = random.choice([(d,c) for c in range(81)
for d in choices(c)])
grid.place(d,c)
while step(grid,True): pass
puzzle.append((d,c))
if generate_symmetric:
c = 80-c
ch = grid.choices(c)
if not ch: # avoid IndexError from random.choice
raise BadSudoku("Placement invalidated symmetric cell")
d = random.choice(ch)
grid.place(d,c)
while step(grid,True): pass
puzzle.append((d,c))
except BadSudoku:
puzzle = []
grid = Sudoku()
continue
break
# find redundant information in initial state
q = 0
while q < len(puzzle):
grid = Sudoku(puzzle[:q] + puzzle[q+1+generate_symmetric:])
if not unisolvent(grid):
q += 1+generate_symmetric
else:
del puzzle[q]
if generate_symmetric:
del puzzle[q]
return Sudoku(puzzle)
def read_puzzle(empty = ".0"):
"""Read and return a Sudoku instance from standard input."""
def digits():
for digit in sys.stdin.read():
if digit in empty:
yield 0
elif '1' <= digit <= '9':
yield int(digit)
return Sudoku(digits())
if __name__ == '__main__':
if options.generate:
puzzle = random_puzzle(not options.asymmetric)
print_puzzle = True
print_solution = options.output_both
else:
puzzle = read_puzzle(options.emptychars)
print_puzzle = options.output_both or options.translate
print_solution = options.output_both or not options.translate
if options.permute:
puzzle = permute(puzzle, not options.asymmetric)
if options.verbose:
puzzle.logstream = sys.stderr
if options.assume_unique:
puzzle.assume_unique = True
if options.twosat:
puzzle.twosat = True
# ======================================================================
# Main program: print and solve puzzle
# ======================================================================
if __name__ == '__main__':
print_level = True
if print_puzzle:
print_level = outputter(puzzle)
if options.output_both and print_level:
print
if options.backtrack:
solns = all_solutions(puzzle,False)
else:
while step(puzzle): pass
solns = [puzzle]
nsolns = 0
for soln in solns:
if print_solution:
print_level = outputter(soln)
nsolns += 1
difficulty = 0
used_names = []
for name,rule,level in rules:
if name in puzzle.rules_used:
used_names.append(name)
difficulty += (1< | | |