Last active
December 15, 2015 07:29
-
-
Save vuryleo/5223413 to your computer and use it in GitHub Desktop.
a stupid sudoku utility
This file contains 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/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