|
| 1 | +importrandom |
| 2 | +importmath |
| 3 | +importcopy |
| 4 | + |
| 5 | +classSudoku: |
| 6 | +def__init__(self,N,E): |
| 7 | +self.N=N |
| 8 | +self.E=E |
| 9 | + |
| 10 | +# compute square root of N |
| 11 | +self.SRN=int(math.sqrt(N)) |
| 12 | +self.table= [[0forxinrange(N)]foryinrange(N)] |
| 13 | +self.answerable_table=None |
| 14 | + |
| 15 | +self._generate_table() |
| 16 | + |
| 17 | +def_generate_table(self): |
| 18 | +# fill the subgroups diagonally table/matrices |
| 19 | +self.fill_diagonal() |
| 20 | + |
| 21 | +# fill remaining empty subgroups |
| 22 | +self.fill_remaining(0,self.SRN) |
| 23 | + |
| 24 | +# Remove random Key digits to make game |
| 25 | +self.remove_digits() |
| 26 | + |
| 27 | +deffill_diagonal(self): |
| 28 | +forxinrange(0,self.N,self.SRN): |
| 29 | +self.fill_cell(x,x) |
| 30 | + |
| 31 | +defnot_in_subgroup(self,rowstart,colstart,num): |
| 32 | +forxinrange(self.SRN): |
| 33 | +foryinrange(self.SRN): |
| 34 | +ifself.table[rowstart+x][colstart+y]==num: |
| 35 | +returnFalse |
| 36 | +returnTrue |
| 37 | + |
| 38 | +deffill_cell(self,row,col): |
| 39 | +num=0 |
| 40 | +forxinrange(self.SRN): |
| 41 | +foryinrange(self.SRN): |
| 42 | +whileTrue: |
| 43 | +num=self.random_generator(self.N) |
| 44 | +ifself.not_in_subgroup(row,col,num): |
| 45 | +break |
| 46 | +self.table[row+x][col+y]=num |
| 47 | + |
| 48 | +defrandom_generator(self,num): |
| 49 | +returnmath.floor(random.random()*num+1) |
| 50 | + |
| 51 | +defsafe_position(self,row,col,num): |
| 52 | +return (self.not_in_row(row,num)andself.not_in_col(col,num)andself.not_in_subgroup(row-row%self.SRN,col-col%self.SRN,num)) |
| 53 | + |
| 54 | +defnot_in_row(self,row,num): |
| 55 | +forcolinrange(self.N): |
| 56 | +ifself.table[row][col]==num: |
| 57 | +returnFalse |
| 58 | +returnTrue |
| 59 | + |
| 60 | +defnot_in_col(self,col,num): |
| 61 | +forrowinrange(self.N): |
| 62 | +ifself.table[row][col]==num: |
| 63 | +returnFalse |
| 64 | +returnTrue |
| 65 | + |
| 66 | + |
| 67 | +deffill_remaining(self,row,col): |
| 68 | +# check if we have reached the end of the matrix |
| 69 | +ifrow==self.N-1andcol==self.N: |
| 70 | +returnTrue |
| 71 | + |
| 72 | +# move to the next row if we have reached the end of the current row |
| 73 | +ifcol==self.N: |
| 74 | +row+=1 |
| 75 | +col=0 |
| 76 | + |
| 77 | +# skip cells that are already filled |
| 78 | +ifself.table[row][col]!=0: |
| 79 | +returnself.fill_remaining(row,col+1) |
| 80 | + |
| 81 | +# try filling the current cell with a valid value |
| 82 | +fornuminrange(1,self.N+1): |
| 83 | +ifself.safe_position(row,col,num): |
| 84 | +self.table[row][col]=num |
| 85 | +ifself.fill_remaining(row,col+1): |
| 86 | +returnTrue |
| 87 | +self.table[row][col]=0 |
| 88 | + |
| 89 | +# no valid value was found, so backtrack |
| 90 | +returnFalse |
| 91 | + |
| 92 | +defremove_digits(self): |
| 93 | +count=self.E |
| 94 | + |
| 95 | +# replicates the table so we can have a filled and pre-filled copy |
| 96 | +self.answerable_table=copy.deepcopy(self.table) |
| 97 | + |
| 98 | +# removing random numbers to create the puzzle sheet |
| 99 | +while (count!=0): |
| 100 | +row=self.random_generator(self.N)-1 |
| 101 | +col=self.random_generator(self.N)-1 |
| 102 | +if (self.answerable_table[row][col]!=0): |
| 103 | +count-=1 |
| 104 | +self.answerable_table[row][col]=0 |
| 105 | + |
| 106 | + |
| 107 | +defpuzzle_table(self): |
| 108 | +returnself.answerable_table |
| 109 | + |
| 110 | +defpuzzle_answers(self): |
| 111 | +returnself.table |
| 112 | + |
| 113 | + |
| 114 | +defprintSudoku(self): |
| 115 | +forrowinrange(self.N): |
| 116 | +forcolinrange(self.N): |
| 117 | +print(self.table[row][col],end=" ") |
| 118 | +print() |
| 119 | + |
| 120 | +print("") |
| 121 | + |
| 122 | +forrowinrange(self.N): |
| 123 | +forcolinrange(self.N): |
| 124 | +print(self.answerable_table[row][col],end=" ") |
| 125 | +print() |
| 126 | + |
| 127 | + |
| 128 | +if__name__=="__main__": |
| 129 | +N=9 |
| 130 | +E= (N*N)//2 |
| 131 | +sudoku=Sudoku(N,E) |
| 132 | +sudoku.printSudoku() |