把數獨寫成如下形式，保存成s.txt，放在同目錄下
010000087
005074000
000006040
009063050
000400200
640050300
030005071
000900400
507100003
以下是代碼部分
---------------------------------------------------------------------------------------------------------------------------------
# sudoku auto solver by RomanGoliard
import copy
#---------------------------------------------------------------------------------------------------------------------------------
full_set = set([1,2,3,4,5,6,7,8,9])
threshold = 3
SUCCESS = 1
REDUCED = 2
NOT_REDUCED = 3
ERROR = 4
#---------------------------------------------------------------------------------------------------------------------------------
# Read sudoku from the file
def get( L ):
f = open("s.txt", 'r')
s = f.read(1)
while s != '':
L.append( int(s) )
s = f.read(1)
if s == '\n':
s = f.read(1)
# get the brick's row from the num of brick
def get_row ( num ):
return num / 9
# get the brick's col from the num of brick
def get_col ( num ):
return num % 9
# get the brick's block from the num of brick
# blocks are defined as follow:
# 0 1 2
# 3 4 5
# 6 7 8
def get_block ( num ):
return get_row(num) / 3 * 3 + get_col(num) / 3
#---------------------------------------------------------------------------------------------------------------------------------
# print the sudoku
def output_sudoku( L ):
for i in range(0, 9):
for j in range(0, 9):
print L[i*9 + j],
print
print
def print_set( col, row, block, sudoku, brick ):
for i in range(9):
if len( col[i] ) < threshold and len( col[i] ) > 0:
print "col:", i, col[i]
if len( row[i] ) < threshold and len( row[i] ) > 0:
print "row:", i, row[i]
if len( block[i] ) < threshold and len( block[i] ) > 0:
print "block:", i, block[i]
for i in range(81):
if sudoku[i] == 0:
if len( brick[i]) < threshold:
print i, brick[i]
#---------------------------------------------------------------------------------------------------------------------------------
def clean_list( col, row, block ):
if len( col ) != 0:
del col[0 : len(col)]
if len( row ) != 0:
del row[0 : len(row)]
if len( block ) != 0:
del block[0 : len(block)]
def reset_all( col, row, block ):
clean_list( col, row, block )
for i in range(9):
col.append( set([]) )
row.append( set([]) )
block.append( set([]) )
# search and inverse the set
def inverse_set( col, row, block, sudoku ):
for i in range(81):
if sudoku[i] != 0:
col[ get_col(i) ].add( sudoku[i] )
row[ get_row(i) ].add( sudoku[i] )
block[ get_block(i) ].add( sudoku[i] )
for i in range(9):
col[i] = full_set - col[i]
row[i] = full_set - row[i]
block[i] = full_set - block[i]
# search the bricks and find those who has only one element
def uni( col, row, block, sudoku ):
for i in range(81):
if sudoku[i] == 0:
temp = col[ get_col(i) ] & row[ get_row(i) ] & block[ get_block(i) ]
if len( temp ) == 1:
sudoku[i] = temp.pop()
col[ get_col(i) ].remove(sudoku[i])
row[ get_row(i) ].remove(sudoku[i])
block[ get_block(i) ].remove(sudoku[i])
# print i, sudoku[i]
# run and solve the sudoko
def search_sudoku( col, row, block, sudoku, brick ):
reset_all( col, row, block )
inverse_set( col, row, block, sudoku )
uni( col, row, block, sudoku )
#---------------------------------------------------------------------------------------------------------------------------------
def check_set( col, row, block, sudoku, brick ):
flag = SUCCESS
for i in range(81):
if sudoku[i] == 0:
flag = NOT_REDUCED
if flag == SUCCESS:
return flag
for i in range(81):
if sudoku[i] == 0:
temp = col[get_col(i)] & row[get_row(i)] & block[get_block(i)]
if len( brick[i] ) > len( temp ):
brick[i] = temp
flag = REDUCED
if len( brick[i] ) == 0:
return ERROR
return flag
def loop_search( col, row, block, sudoku, brick ):
search_sudoku( col, row, block, sudoku, brick )
value = check_set( col, row, block, sudoku, brick )
while value == REDUCED:
search_sudoku( col, row, block, sudoku, brick )
value = check_set( col, row, block, sudoku, brick )
return value
#---------------------------------------------------------------------------------------------------------------------------------
# sandbox test
def sandbox( col, row, block, sudoku, brick ):
for i in range( 81 ):
for j in range( 81 ):
if sudoku[i] == 0 and sudoku[j] == 0:
if len( brick[i] ) > 0 and len( brick[j] ) > 0:
remain_i, remain_j = set([]), set([])
for e in brick[i]:
for f in brick[j]:
sudoku[i], sudoku[j] = e, f
value = loop_search( copy.deepcopy( col ), copy.deepcopy( row ), copy.deepcopy( block ), copy.deepcopy( sudoku ), copy.deepcopy( brick ) )
sudoku[i], sudoku[j] = 0, 0
if value != ERROR:
remain_i.add( e )
remain_j.add( f )
if len ( remain_i ) < len( brick[i] ) and len( remain_i ) > 0:
brick[i] = remain_i
if len ( remain_j ) < len( brick[j] ) and len( remain_j ) > 0:
brick[j] = remain_j
if len( brick[i] ) == 1:
for e in brick[i]:
sudoku[i] = e
loop_search( col, row, block, sudoku, brick )
if len( brick[j] ) == 1:
for e in brick[j]:
sudoku[j] = e
loop_search( col, row, block, sudoku, brick )
# main -------------------------------------------------------------------------------------------
cols = []
rows = []
blocks = []
bricks = []
sudokus = []
get(sudokus)
for i in range(81):
bricks.append(full_set)
if loop_search( cols, rows, blocks, sudokus, bricks ) == SUCCESS:
print "Found solution!"
else:
sandbox( cols, rows, blocks, sudokus, bricks )
output_sudoku( sudokus )
# write back to file
# ......
# write back to file