Особенности решения концептуальной модели задачи решающего комплекса
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
тная ошибка при задании начальных условий',
: lambda q: "Переменная %s прямо вычисляется по правилу %s"%(q['vName'], q['ruleString']),
: lambda q: "Не задана переменная %s" %(q['vName']),
: lambda q: 'Какая-то из переменных правой части правил не может быть найдена в условиях и/или других правилах, ожидается %s'%(q['vName']),
: lambda q: 'Переменная правой части условий найдена в задании левой. Может вызвать ошибку',
: lambda q: 'Избыточные данные: переменная %s задана и требуется найти'%(q),
: lambda q: "Попытка использовать незаданную переменную %s в правилах" %(q['vName']),
: lambda q: 'Неизвестная ошибка при задании правил',
: lambda q: 'Ошибка прямого подiёта, строка %s, переменная %s: '%(q['ruleString'], q['varName']),
: lambda q:
"Переменная %s не найдена среди возможных (%s)" %(q['vName'], q['dVars']),
: lambda q: 'Не заданы правило: строка должна быть формата A=(B) (дано: %s'%(''.join(q['vString'])),
: lambda q: 'Ошибка обработки строки %s: %s'%(q['line'], q['str'])
}[self.solveErr](self.solveErrExtend), True)
log(self, txt, error=False, onlyError=False):error:.sErrTxt = self.sErrTxt + "\n" + txtnot onlyError:.sSolveTxt = self.sSolveTxt + "\n" + txt
graph(self, event):self.definiedVariablesself.definiedVariablesFirst.graphWindow(self.parent, globals=self.__globals, locals=self.__locals,=self.definiedVariablesFirst,=self.data,=self.fString)
Решатель судоку методом полного перебора
def solve(s)::= s.index(0)ValueError:
# No empty cell left: solution founds
= [s[j] for j in range(81)not ((i-j)%9 * (i//9^j//9) * (i//27^j//27 | (i%9//3^j%9//3)))]
v in range(1, 10):v not in c:= solve(s[:i]+[v]+s[i+1:])r is not None:r
Sudoku(list):
'''Sudokus with nicer IO'''__init__(self, content):.__init__(self, [int(i) for i in content.split()] isinstance(content, str) else content)__str__(self):'\n'.join(
' '.join([(str(j) if j != 0 else '-') j in self[i*9:(i+1)*9]]) for i in range(9))
Решатель судоку аналитическими методами
TRIPLETS = [[0,1,2],[3,4,5],[6,7,8]]
#Row/Col/3x3 iteration list, each is nine lists of nine (row,col) pairs_ITER = [[(row,col) for col in range(0,9)] for row in range(0,9)]_ITER = [[(row,col) for row in range(0,9)] for col in range(0,9)]_ITER = [[(row,col) for row in rows for col in cols] for rows in TRIPLETS for cols in TRIPLETS]
sudoku:__init__(self, start_grid=None) :
#Setup list of lists (the rows), each row is a list of 9 cells, which are each a list of integers 1-9 inclusive..squares =[ [range(1,10) for col in range(0,9)] for row in range(0,9)]
start_grid is not None:len(start_grid)==81 :row in range(0,9) :.set_row(row, start_grid[(row*9):((row+1)*9)]):len(start_grid)==9, "Bad input!"row in range(0,9) :.set_row(row, start_grid[row])
#self.check()._changed=False
solved(self) :row in range(0,9) :col in range(0,9) :len(self.squares[row][col]) > 1 :FalseTrue
copy(self) :_copy = sudoku(None)row in range(0,9) :col in range(0,9) :_copy.squares[row][col] = self.squares[row][col][:] #copy!_copy._changed=Falsesudoku_copy
set_row(self,row, x_list) :len(x_list)==9col in range(0,9) ::= int(x_list[col]):= 0
#self.set_cell(row,col,x).set_cell(row,col,x)
set_cell(self,row,col,x):self.squares[row][col] == [x] :
#Already done!x not in range(1,9+1) :
#Set to unknown:x in self.squares[row][col], \
"Told to set square (%i,%i) to an impossible entry, %i" % (row,col,x)
.squares[row][col] = [x].update_neighbours(row,col,x)._changed=True
cell_exclude(self, row,col,x) :x in range(1,9+1)x in self.squares[row][col] :
#Remove it....squares[row][col].remove(x)
#Should be one or more entries left...len(self.squares[row][col]) > 0, \
"Removed last possible entry for square (%i,%i) which was %i" \
% (row, col, x)
#Now, has this confirmed the value for this square?len(self.squares[row][col]) == 1 :
#This cell is now definate..
#Need to update its friends...
#print "After exluding %i, square (%i,%i) must be %i" \
#% (x, self.row, self.col, self[0])._changed=True.update_neighbours(row,col,self.squares[row][col][0]):
#Don't need to remove this, already done!
row_exclude(self, row, x) :x in range(1,9+1)col in range(0,9) :.cell_exclude(row,col,x)
col_exclude(self, col, x) :x in range(1,9+1)row in range(0,9) :.cell_exclude(row,col,x)
update_neighbours(self,set_row,set_col,x) :
"""Call this when the square is set to x, either directly,as a side effect of an exclude leaving only one entry"""
#print "Updating (%i,%i) to be %i..." % (self.row, self.col, x)
#Update the possibilies in this row...row in range(0,9) :row <> set_row :.cell_exclude(row,set_col,x)
#Update the possibilies in this col...col in range(0,9) :col <> set_col :.cell_exclude(set_row,col,x)
#Update the possibilies in this 3x3 square...triplet in TRIPLETS :set_row in triplet : rows = triplet[:]set_col in triplet : cols = triplet[:]
#Only need to do four of the eight possibles (well, 9 if you count the cell itself)
#as did two on the row, and two on the col.remove(set_row).remove(set_col)row in rows :col in cols :row set_col
#print "Updating (%i,%i) to be %i, excluding %i from (%i, %i)" \
#% (self.row, self.col, x, x, row, col).cell_exclude(row,col,x)
get_cell_int(self,row,col) :len(self.squares[row][col])==1 :int(self.squares[row][col][0]):0
get_cell_str(self,row,col) :len(self.squares[row][col])==1 :"(%i,%i) = %i" % (row, col, self.squares[row][col][0]):("(%i,%i) = " % (row, col)) + ",".join([str(x) for x in self.squares[row][col]])
get_cell_digit_str(self,row,col) :len(self.squares[row][col])==1 :str(self.squares[row][col][0]):"0"
as_test_81(self) :
"""Return a string of 81 digits""""".join(self.as_test_list())
simple_text(self) :"\n".join(self.as_test_list())
as_test_list(self) :[ ("".join( [self.get_cell_digit_str(row,col) for col in range(0,9)])) for row in range(0,9) ]
"""=[]row in range(0,9) :=""col in range(0,9) := line + self.get_cell_digit_str(row,col).append(line)answer
"""
__repr__(self):="[" + ",".join([ \
("[" + ",".join( [self.get_cell_digit_str(row,col) for col in range(0,9)]) + "]") \row in range(0,9) ])answer
__str__(self):= " 123 456 789\n"row in range(0,9) := answer + str(row+1) \
+ " [" + "".join([self.get_cell_digit_str(row,col).replace("0","?") for col in range(0,3)]) \
+ "] [" + "".join([self.get_cell_digit_str(row,col).replace("0","?") for col in range(3,6)]) \
+ "] [" + "".join([self.get_cell_digit_str(row,col).replace("0","?") for col in range(6,9)]) \
+ "]\n"row+1 in [3,6] : = answer + " --- --- ---\n"answer
retArr(self):= []row in range(0,9) :.append([])col in range(0, 9):[row].append(self.get_cell_digit_str(row,col))data
check(self, level=0) :._changed=Trueself._changed:
#print "checking..."._changed=False.check_for_single_occurances().check_for_last_in_row_col_3x3()level >= 1 :.overlapping_3x3_and_row_or_col() #(aka slicing and dicing)level >= 2 :.one_level_supposition()level >= 3 :.two_level_supposition()
#If nothing happened, then self.changed==False (still)
#and we break the loop
check_for_single_occurances(self):
#Want to see if x only occurs once in this row/col/3x3...check_type in [ROW_ITER, COL_ITER, TxT_ITER]:check_list in check_type :x in range(1,9+1) : #1 to 9 inclusive_in_list = [](row,col) in check_list :x in self.squares[row][col] :_in_list.append((row,col))len(x_in_list)==1 :
(row,col) = x_in_list[0]
#This position MUST be be xlen(self.squares[row][col]) > 1 :.set_cell(row,col,x)
check_for_last_in_row_col_3x3(self):
#Now, for each row/col/3x3 want to see if there is a single
#unknown entry...(type_name, check_type) in [("Row",ROW_ITER),("Col",COL_ITER),("3x3",TxT_ITER)]:check_list in check_type :_entries = []_values = range(1,9+1)