Skip to content

Instantly share code, notes, and snippets.

@vuryleo
Last active December 15, 2015 07:29
Show Gist options
  • Save vuryleo/5223413 to your computer and use it in GitHub Desktop.
Save vuryleo/5223413 to your computer and use it in GitHub Desktop.
a stupid sudoku utility
#!/usr/bin/python3.3
import sys
import argparse
import random
import copy
parser = argparse.ArgumentParser(description='Sudoku Utility.')
parser.add_argument('inStream', metavar='inStream', type=str, nargs='?', help='input stream.')
parser.add_argument('outStream', metavar='outStream', type=str, nargs='?', help='output stream.')
parser.add_argument('-g', '--generate', action='store_true', help='generate a sudoku other than solve')
parser.add_argument('-v', '--verbose', action='store_true', help='show debug information')
parser.add_argument('-q', '--quiet', action='store_true', help='show none information')
parser.add_argument('-n', '--number', metavar='number', type=int, default=30, help='Number of hole')
class Logger:
logLevel = 0;
def debug(self, *arg):
if self.logLevel < 0:
sys.stderr.write("[debug] "+str(arg)+"\n")
def info(self, *arg):
if self.logLevel < 1:
sys.stderr.write("[info] "+str(arg)+"\n")
def error(self, *arg):
if self.logLevel < 2:
sys.stderr.write("[error] "+str(arg)+"\n")
logger = Logger()
class Sudoku:
puzzle = []
def load(self, infile):
content = infile.read().split('\n')
if not len(content) in range(9, 11):
raise Exception("File line length is not right")
self.puzzle = list(list(map(int, line)) for line in content)
def __init__(self):
self.puzzle = [
[1, 2, 3, 4, 5, 6, 7, 8, 9],
[4, 5, 6, 7, 8, 9, 1, 2, 3],
[7, 8, 9, 1, 2, 3, 4, 5, 6],
[2, 3, 4, 5, 6, 7, 8, 9, 1],
[5, 6, 7, 8, 9, 1, 2, 3, 4],
[8, 9, 1, 2, 3, 4, 5, 6, 7],
[3, 4, 5, 6, 7, 8, 9, 1, 2],
[6, 7, 8, 9, 1, 2, 3, 4, 5],
[9, 1, 2, 3, 4, 5, 6, 7, 8]
]
def __str__(self):
return '\n'.join([''.join(list(map(str, row))) for row in self.puzzle])
def check(self, count):
row, col = count // 9, count % 9
if self.puzzle[row][col] == 0:
return True
for i in range(9):
if self.puzzle[row][i] == self.puzzle[row][col] and i != col:
return False
if self.puzzle[i][col] == self.puzzle[row][col] and i != row:
return False
blockRow, blockCol = row // 3 * 3, col // 3 * 3
for i in range(blockRow, blockRow + 3):
for j in range(blockCol, blockCol + 3):
if self.puzzle[i][j] == self.puzzle[row][col] and (i != row or j != col):
return False
return True
def swap(self, numA, numB):
logger.debug("Try to swap", numA, numB)
self.puzzle = [[numB if i == numA else numA if i==numB else i for i in x] for x in self.puzzle]
def randSwap(self):
numA = random.randint(1,8)
numB = random.randint(numA+1,9)
self.swap(numA, numB)
def swapLine(self, linA, linB):
logger.debug("Try to swap Line", linA, linB)
self.puzzle[linA], self.puzzle[linB] = self.puzzle[linB], self.puzzle[linA]
def randSwapLine(self):
block = random.randint(0,2) * 3
numA = random.randint(0,1)
numB = random.randint(numA+1,2)
self.swapLine(block + numA, block + numB)
def roll(self):
logger.debug("Rolling")
self.puzzle = [[x[i] for x in reversed(self.puzzle)] for i in range(9)]
def swapBlock(self, blockA, blockB):
logger.debug("Try to swap block", blockA, blockB)
blockA, blockB = blockA * 3, blockB * 3
for i in range(3):
self.puzzle[blockA + i], self.puzzle[blockB + i] = self.puzzle[blockB + i], self.puzzle[blockA + i]
def randSwapBlock(self):
blockA = random.randint(0,1)
blockB = random.randint(blockA+1,2)
self.swapBlock(blockA, blockB)
def shuffle(self, time = 100):
for i in range(time):
random.choice([self.randSwap, self.roll, self.randSwapLine, self.randSwapBlock])()
def generate(self, s_hole = 30, stime =100):
hole = 0
self.shuffle(stime)
for i in range(len(self.puzzle)):
if hole == s_hole:
break
for j in range(9):
if self.dig(i * 9 + j):
hole = hole + 1
logger.info("Digged: ", hole, '/', s_hole)
if hole == s_hole:
break
self.shuffle(stime)
def dig(self, count):
row, col = count // 9, count % 9
origin = self.puzzle[row][col]
if origin != 0:
canDig = True
for i in range(1,10):
if i != origin:
self.puzzle[row][col] = i
newSudoku = copy.deepcopy(self)
if newSudoku.search():
self.puzzle[row][col] = origin
canDig = False
break
if canDig:
logger.debug("Can dig", row, col)
self.puzzle[row][col] = 0
return True
return False
def search(self, count = 80):
if count == -1:
return True
row, col = count // 9, count % 9
if self.puzzle[row][col] == 0:
for i in range(1, 10):
self.puzzle[row][col] = i
if self.check(count):
if self.search(count - 1):
return True
self.puzzle[row][col] = 0
else:
if self.check(count) and self.search(count - 1):
return True
return False
if __name__=='__main__':
try:
args = parser.parse_args()
if args.verbose:
logger.logLevel = -1
if args.quiet:
logger.logLevel = 100
try:
infile = open(args.inStream, 'r')
except:
infile = sys.stdin
try:
outfile = open(args.outStream, 'w')
except:
outfile = sys.stdout
if args.generate:
sudoku = Sudoku()
sudoku.generate(args.number, 100)
outfile.write(str(sudoku))
else:
sudoku = Sudoku()
sudoku.load(infile)
if sudoku.search():
outfile.write(str(sudoku))
else:
outfile.write("No Answer")
except Exception:
raise
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment