# -*- coding: utf-8 -*- import cProfile import sys import time import copy sudoku01=[ [0,0,3,0,2,0,6,0,0], [9,0,0,3,0,5,0,0,1], [0,0,1,8,0,6,4,0,0], [0,0,8,1,0,2,9,0,0], [7,0,0,0,0,0,0,0,8], [0,0,6,7,0,8,2,0,0], [0,0,2,6,0,9,5,0,0], [8,0,0,2,0,3,0,0,9], [0,0,5,0,1,0,3,0,0] ] sudoku25=[ [3,6,0,0,2,0,0,8,9], [0,0,0,3,6,1,0,0,0], [0,0,0,0,0,0,0,0,0], [8,0,3,0,0,0,6,0,2], [4,0,0,6,0,3,0,0,7], [6,0,7,0,0,0,1,0,8], [0,0,0,0,0,0,0,0,0], [0,0,0,4,1,8,0,0,0], [9,7,0,0,3,0,0,1,4] ] sudoku50=[ [3,0,0,2,0,0,0,0,0], [0,0,0,1,0,7,0,0,0], [7,0,6,0,3,0,5,0,0], [0,7,0,0,0,9,0,8,0], [9,0,0,0,2,0,0,0,4], [0,1,0,8,0,0,0,5,0], [0,0,9,0,4,0,3,0,1], [0,0,0,7,0,2,0,0,0], [0,0,0,0,0,8,0,0,6] ] sudoku_hardest=[ [1,0,0,0,0,7,0,9,0], [0,3,0,0,2,0,0,0,8], [0,0,9,6,0,0,5,0,0], [0,0,5,3,0,0,9,0,0], [0,1,0,0,8,0,0,0,2], [6,0,0,0,0,4,0,0,0], [3,0,0,0,0,0,0,1,0], [0,4,0,0,0,0,0,0,7], [0,0,7,0,0,0,3,0,0], ] sudoku_hardest2=[ [0,0,5,3,0,0,0,0,0], [8,0,0,0,0,0,0,2,0], [0,7,0,0,1,0,5,0,0], [4,0,0,0,0,5,3,0,0], [0,1,0,0,7,0,0,0,6], [0,0,3,2,0,0,0,8,0], [0,6,0,5,0,0,0,0,9], [0,0,4,0,0,0,0,3,0], [0,0,0,0,0,9,7,0,0], ] sudoku_hardest3=[ [8,5,0,0,0,2,4,0,0], [7,2,0,0,0,0,0,0,9], [0,0,4,0,0,0,0,0,0], [0,0,0,1,0,7,0,0,2], [3,0,5,0,0,0,9,0,0], [0,4,0,0,0,0,0,0,0], [0,0,0,0,8,0,0,7,0], [0,1,7,0,0,0,0,0,0], [0,0,0,0,3,6,0,4,0], ] norvig_sudoku=[ [0,0,0,0,0,5,0,8,0], [0,0,0,6,0,1,0,4,3], [0,0,0,0,0,0,0,0,0], [0,1,0,5,0,0,0,0,0], [0,0,0,1,0,6,0,0,0], [3,0,0,0,0,0,0,0,5], [5,4,0,0,0,0,0,6,1], [0,0,0,0,0,0,0,0,4], [0,0,0,0,0,0,0,0,0] ] def is_line_filled (line): return all (c!=0 for i in line) def is_line_solved (i): return len(list(set(i)))==9 def check_box_solved (box, i, j): return is_line_solved ([box[i][j], box[i][j+1], box[i][j+2], box[i+1][j], box[i+1][j+1], box[i+1][j+2], box[i+2][j], box[i+2][j+1], box[i+2][j+2]]) def dump_sudoku(i): for l in i: print (l) def check_boxes_solved(tbl): return all ([check_box_solved(tbl,0,0), check_box_solved(tbl,0,3), check_box_solved(tbl,0,6), check_box_solved(tbl,3,0), check_box_solved(tbl,3,3), check_box_solved(tbl,3,6), check_box_solved(tbl,6,0), check_box_solved(tbl,6,3), check_box_solved(tbl,6,6)]) def check_horiz_lines_solved (tbl): return all(is_line_solved (l) for l in tbl) def check_ver_lines_solved (tbl): for idx1 in range(9): r=[] for idx2 in range(9): r.append(tbl[idx2][idx1]) if is_line_solved(r)==False: return False return True def check_as_solved (tbl): return all ([check_horiz_lines_solved (tbl), check_ver_lines_solved (tbl), check_boxes_solved(tbl)]) def find_unfilled_pos (i): # find zero in tbl for X in range (9): for Y in range (9): if i[X][Y]==0: return X,Y return None def is_dups_in_line_except_zero (line): # 1..9 found=[False, False, False, False, False, False, False, False, False] for i in line: if i>0: if found[i-1]: return True else: found[i-1]=True return False def is_dups_in_row_except_zero (tbl, row): """ r=[] for idx2 in range(9): r.append(tbl[idx2][row]) if is_dups_in_line_except_zero(r): return True return False """ # 1..9 found=[False, False, False, False, False, False, False, False, False] for i in tbl: if i[row]>0: if found[i[row]-1]: return True else: found[i[row]-1]=True return False def is_dups_in_box_except_zero (box, i, j): return is_dups_in_line_except_zero ([box[i][j], box[i][j+1], box[i][j+2], box[i+1][j], box[i+1][j+1], box[i+1][j+2], box[i+2][j], box[i+2][j+1], box[i+2][j+2]]) def check_it (i, last_modified_posX=None, last_modified_posY=None): global count if False and count>0 and (count % 100000)==0: print ("* count="+str(count)) dump_sudoku(i) count=count+1 # check for dups # check all horiz if last_modified_posX==None: if any([is_dups_in_line_except_zero (l) for l in i]): return None else: if is_dups_in_line_except_zero(i[last_modified_posX]): return None # check all vertical if last_modified_posY==None: if any([is_dups_in_row_except_zero (i, idx) for idx in range(9)]): return None else: if is_dups_in_row_except_zero (i, last_modified_posY): return None if (any([is_dups_in_box_except_zero(i,6,6), is_dups_in_box_except_zero(i,6,3), is_dups_in_box_except_zero(i,6,0), is_dups_in_box_except_zero(i,3,6), is_dups_in_box_except_zero(i,3,3), is_dups_in_box_except_zero(i,3,0), is_dups_in_box_except_zero(i,0,6), is_dups_in_box_except_zero(i,0,3), is_dups_in_box_except_zero(i,0,0)])): return None r=find_unfilled_pos(i) if r==None: # all elements in table are filled if check_as_solved (i)==True: return i return None posX,posY=r saved=i[posX][posY] for new_cell in range (1,10): # она не должна быть из числа тех что в той же линии, итд... i[posX][posY]=new_cell t=check_it(i, posX, posY) if t!=None: return t i[posX][posY]=saved return None def tst(): solved=[ [4,8,3,9,2,1,6,5,7], [9,6,7,3,4,5,8,2,1], [2,5,1,8,7,6,4,9,3], [5,4,8,1,3,2,9,7,6], [7,2,9,5,6,4,1,3,8], [1,3,6,7,9,8,2,4,5], [3,7,2,6,8,9,5,1,4], [8,1,4,2,5,3,7,6,9], [6,9,5,4,1,7,3,8,2] ] if check_it (sudoku01)==solved: print ("tst passed") else: print ("tst not passed!") def str_to_list_of_number(s): rt=[] for c in s: rt.append (ord(c)-0x30) return rt def main(): tst() f=open ('sudoku.txt', 'r') sum=0 for s in range (50): #for s in range (4): name=f.readline().rstrip("\n") print (name) sudoku=[] for i in range (9): sudoku.append (str_to_list_of_number (f.readline().rstrip("\n"))) r=check_it(sudoku) if r!=None: print ("solved:") dump_sudoku (r) n=r[0][0]*100 + r[0][1]*10 + r[0][2] sum=sum+n print ("number is %d" % n) else: print ("not solved!") sys.exit(0) print ("sum=%d" % sum) count=0 #cProfile.run('main()') main() #cProfile.run('tst()') #tst() #print check_it (norvig_sudoku)