de Ali Spittel
Cum am revenit la o veche problemă și în cele din urmă am scris un algoritm de rezolvare Sudoku
Acest articol va fi parte tehnică, parte poveste personală și parte critică culturală. Dacă sunteți aici doar pentru cod și explicație, treceți la Abordarea inițială antet!
Această poveste începe acum câțiva ani într-o sală de clasă de informatică a colegiului. Am avut o cale netradițională de a scrie codul – m-am înscris aleatoriu la o clasă de informatică în timpul celui de-al doilea an de facultate, pentru că aveam o oră de credit suplimentară și eram curios despre ce este vorba. Am crezut că vom învăța cum să folosim Microsoft Word și Excel – cu adevărat nu aveam idee ce cod este.
Liceul meu cu siguranță nu avea clase de codare, abia aveau computere funcționale! Nu am jucat jocuri video și nici nu m-am implicat în activități care, în mod tradițional, îi determină pe copii să învețe cum să codeze. Deci, codificarea a fost complet nouă pentru mine când am luat acea clasă Python la facultate.
De îndată ce am intrat în clasă, ne-au pus să introducem codul Python în Idle, un editor de text care vine cu limbajul Python. Au tipărit codul și ne-au pus doar să-l introducem și să-l rulăm – am fost imediat prins. Pe parcursul acelei clase, am construit un script Tic Tac Toe cu un GUI pentru a introduce piese și o clonă Flappy Bird. Sincer, mi-a venit destul de ușor și m-am distrat foarte mult. Am decis repede să mă specializez în informatică și am vrut doar să scriu mai multe coduri.
Semestrul următor m-am înscris la un curs de structuri de date și algoritmi, care a urmat în secvența de informatică. Clasa a fost predată în C ++, care, fără să știu, ar fi trebuit să fie învățată în vara dinaintea orei. A devenit rapid evident că profesorii au încercat să folosească clasa pentru a filtra studenții – aproximativ 50% din cei înscriși în prima zi au reușit să treacă prin semestru. Am schimbat chiar sălile de clasă dintr-o sală de curs într-o sală de odihnă. Mândria mea a fost singurul lucru care m-a ținut în clasă. M-am simțit complet pierdut în aproape fiecare lecție. Mi-am petrecut multe nopți lucrând la proiecte și studiind examenele.
O problemă în special m-a prins cu adevărat – trebuia să construim un program în C ++ care să rezolve orice problemă Sudoku. Din nou, am petrecut nenumărate ore pe sarcină încercând să pun codul în funcțiune. Până la data la care proiectul a trebuit, soluția mea a funcționat pentru unele dintre cazurile de testare, dar nu pentru toate. Am ajuns să primesc un C + la misiunea mea – una dintre cele mai proaste note din toată facultatea.
După semestrul respectiv, mi-am abandonat ideea de minorat în informatică, am renunțat complet la codificare și m-am lipit de ceea ce credeam că mă pricep la scriere și politică.
Desigur, se întâmplă lucruri amuzante în viață și, evident, am început să codez din nou, dar mi-a luat mult timp să simt că sunt un programator competent.
Acestea fiind spuse, câțiva ani mai târziu în călătoria mea de programare, am decis să încerc din nou să implementez algoritmul de rezolvare Sudoku pentru a-mi demonstra că aș putea să-l implementez acum. Codul nu este perfect, dar va rezolva aproape orice puzzle Sudoku. Să parcurgem algoritmul și apoi implementarea.
Puzzle-uri Sudoku
În cazul în care nu ați mai jucat puzzle-uri Sudoku, acestea sunt puzzle-uri numerice în care fiecare rând, coloană și pătrat de 3×3 din puzzle trebuie să aibă numerele 1-9 reprezentate exact o dată. Există o mulțime de abordări pentru rezolvarea acestor puzzle-uri, dintre care multe pot fi reproduse de un computer în loc de o persoană. De obicei, atunci când le rezolvăm folosind un computer, vom folosi tablouri imbricate pentru a reprezenta placa Sudoku astfel:
puzzle = [[5, 3, 0, 0, 7, 0, 0, 0, 0], [6, 0, 0, 1, 9, 5, 0, 0, 0], [0, 9, 8, 0, 0, 0, 0, 6, 0], [8, 0, 0, 0, 6, 0, 0, 0, 3], [4, 0, 0, 8, 0, 3, 0, 0, 1], [7, 0, 0, 0, 2, 0, 0, 0, 6], [0, 6, 0, 0, 0, 0, 2, 8, 0], [0, 0, 0, 4, 1, 9, 0, 0, 5], [0, 0, 0, 0, 8, 0, 0, 7, 9]]Când sunt rezolvate, zerourile vor fi completate cu numere reale:
solution = [[5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8], [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 4, 5, 2, 8, 6, 1, 7, 9]]Abordarea inițială
Deoarece nu aveam chef să scriu o suită completă de teste cu diferite puzzle-uri, am folosit provocările CodeWars să mă testez. Prima problemă pe care am încercat-o a fost acest – unde toate puzzle-urile erau Sudokus „ușor”, care puteau fi rezolvate fără un algoritm mai complex.
Am decis să încerc să rezolv Sudokus-urile așa cum fac personal – unde aș găsi numerele posibile pentru un spațiu, le voi urmări și, dacă există un singur număr posibil, conectați-l la acel loc. Deoarece acestea erau Sudokus mai ușoare, această abordare a funcționat bine pentru acest Kata și am trecut.
Iată codul meu (necurățat)!
class SudokuSolver: def __init__(self, puzzle): self.puzzle = puzzle self.box_size = 3 def find_possibilities(self, row_number, column_number): possibilities = set(range(1, 10)) row = self.get_row(row_number) column = self.get_column(column_number) box = self.get_box(row_number, column_number) for item in row + column + box: if not isinstance(item, list)and item in possibilities: possibilities.remove(item) return possibilities def get_row(self, row_number): return self.puzzle[row_number] def get_column(self, column_number): return [row[column_number] for row in self.puzzle] def get_box(self, row_number, column_number): start_y = column_number // 3 * 3 start_x = row_number // 3 * 3 if start_x < 0: start_x = 0 if start_y < 0: start_y = 0 box = [] for i in range(start_x, self.box_size + start_x): box.extend(self.puzzle[i][start_y:start_y+self.box_size]) return box def find_spot(self): unsolved = True while unsolved: unsolved = False for row_number, row in enumerate(self.puzzle): for column_number, item in enumerate(row): if item == 0: unsolved = True possibilities = self.find_possibilities( row_number, column_number) if len(possibilities) == 1: self.puzzle[row_number][column_number] = list(possibilities)[ 0] return self.puzzledef sudoku(puzzle): sudoku = SudokuSolver(puzzle) return sudoku.find_spot()Desigur, am vrut să rezolv și puzzle-uri Sudoku mai dificile, așa că am decis să implementez un algoritm mai complex pentru a rezolva acele puzzle-uri.
Algoritmul
Un algoritm pentru rezolvarea puzzle-urilor Sudoku este algoritmul de backtracking. În esență, continuați să încercați numerele în locuri goale până când nu sunt posibile, apoi înapoi și încercați numere diferite în sloturile anterioare.
Primul lucru pe care l-am făcut a fost să continui abordarea „ușor” a solverului Sudoku de a găsi valorile posibile pentru fiecare pătrat pe baza cărora valorile erau deja în rândul, coloana și caseta respectivului pătrat. Am stocat toate aceste valori într-o listă, astfel încât să mă pot referi rapid la ele în timp ce mergeam înapoi sau găseam ce valoare să folosim în acel pătrat.
Apoi, trebuia să implementez mișcarea și retrogradarea înainte de a pune obiecte în fiecare spațiu. Am pus markere pe fiecare spațiu ne-dat (deci cele care erau zerouri la începutul jocului), astfel încât acele spații să fie incluse în backtracking și locurile date să nu fie. Apoi am parcurs acele locuri nerezolvate. Aș pune primul articol din lista de valori posibile în acel loc și apoi m-aș deplasa la următorul loc nerezolvat. Aș pune apoi prima valoare posibilă a acelui loc la locul său. Dacă ar intra în conflict cu valoarea slotului anterior, aș trece apoi la al doilea element din lista de valori posibile și apoi m-aș deplasa la următorul slot.
Acest proces va continua până când nu va exista nicio mișcare posibilă pentru un anumit loc – adică s-a ajuns la sfârșitul listei de valori posibile și niciuna dintre valorile nu a funcționat în acel rând, coloană sau casetă. Apoi, algoritmul de backtracking a început.
În cadrul implementării backtracking, codul s-ar muta înapoi la ultimul loc care a fost completat și s-ar muta la următoarea valoare posibilă și apoi va începe să avanseze din nou. Dacă ultima valoare posibilă a fost atinsă și în acel punct, algoritmul de urmărire inversă ar continua să se deplaseze înapoi până când va exista un punct care ar putea fi incrementat.
Odată ajuns la sfârșitul puzzle-ului cu valori corecte în fiecare pătrat, puzzle-ul a fost rezolvat!
Abordarea mea
Îmi plac abordările orientate pe obiecte, așa că am două clase diferite în soluția mea: una pentru celulă și una pentru placa Sudoku. Codul meu foarte imperfect arată astfel:
class Cell: """One individual cell on the Sudoku board""" def __init__(self, column_number, row_number, number, game): # Whether or not to include the cell in the backtracking self.solved = True if number > 0 else False self.number = number # the current value of the cell # Which numbers the cell could potentially be self.possibilities = set(range(1, 10)) if not self.solved else [] self.row = row_number # the index of the row the cell is in self.column = column_number # the index of the column the cell is in self.current_index = 0 # the index of the current possibility self.game = game # the sudoku game the cell belongs to if not self.solved: # runs the possibility checker self.find_possibilities() def check_area(self, area): """Checks to see if the cell's current value is a valid sudoku move""" values = [item for item in area if item != 0] return len(values) == len(set(values)) def set_number(self): """changes the number attribute and also changes the cell's value in the larger puzzle""" if not self.solved: self.number = self.possibilities[self.current_index] self.game.puzzle[self.row][self.column] = self.possibilities[self.current_index] def handle_one_possibility(self): """If the cell only has one possibility, set the cell to that value and mark it as solved""" if len(self.possibilities) == 1: self.solved = True self.set_number() def find_possibilities(self): """filter the possible values for the cell""" for item in self.game.get_row(self.row) + self.game.get_column(self.column) + self.game.get_box(self.row, self.column): if not isinstance(item, list) and item in self.possibilities: self.possibilities.remove(item) self.possibilities = list(self.possibilities) self.handle_one_possibility() def is_valid(self): """checks to see if the current number is valid in its row, column, and box""" for unit in [self.game.get_row(self.row), self.game.get_column(self.column), self.game.get_box(self.row, self.column)]: if not self.check_area(unit): return False return True def increment_value(self): """move number to the next possibility while the current number is invalid and there are possibilities left""" while not self.is_valid() and self.current_index < len(self.possibilities) - 1: self.current_index += 1 self.set_number()class SudokuSolver: """contains logic for solving a sudoku puzzle -- even very difficult ones using a backtracking algorithm""" def __init__(self, puzzle): self.puzzle = puzzle # the 2d list of spots on the board self.solve_puzzle = [] # 1d list of the Cell objects # the size of the boxes within the puzzle -- 3 for a typical puzzle self.box_size = int(len(self.puzzle) ** .5) self.backtrack_coord = 0 # what index the backtracking is currently at def get_row(self, row_number): """Get the full row from the puzzle based on the row index""" return self.puzzle[row_number] def get_column(self, column_number): """Get the full column""" return [row[column_number] for row in self.puzzle] def find_box_start(self, coordinate): """Get the start coordinate for the small sudoku box""" return coordinate // self.box_size * self.box_size def get_box_coordinates(self, row_number, column_number): """Get the numbers of the small sudoku box""" return self.find_box_start(column_number), self.find_box_start(row_number) def get_box(self, row_number, column_number): """Get the small sudoku box for an x and y coordinate""" start_y, start_x = self.get_box_coordinates(row_number, column_number) box = [] for i in range(start_x, self.box_size + start_x): box.extend(self.puzzle[i][start_y:start_y+self.box_size]) return box def initialize_board(self): """create the Cells for each item in the puzzle and get its possibilities""" for row_number, row in enumerate(self.puzzle): for column_number, item in enumerate(row): self.solve_puzzle.append( Cell(column_number, row_number, item, self)) def move_forward(self): """Move forwards to the next cell""" while self.backtrack_coord < len(self.solve_puzzle) - 1 and self.solve_puzzle[self.backtrack_coord].solved: self.backtrack_coord += 1 def backtrack(self): """Move forwards to the next cell""" self.backtrack_coord -= 1 while self.solve_puzzle[self.backtrack_coord].solved: self.backtrack_coord -= 1 def set_cell(self): """Set the current cell to work on""" cell = self.solve_puzzle[self.backtrack_coord] cell.set_number() return cell def reset_cell(self, cell): """set a cell back to zero""" cell.current_index = 0 cell.number = 0 self.puzzle[cell.row][cell.column] = 0 def decrement_cell(self, cell): """runs the backtracking algorithm""" while cell.current_index == len(cell.possibilities) - 1: self.reset_cell(cell) self.backtrack() cell = self.solve_puzzle[self.backtrack_coord] cell.current_index += 1 def change_cells(self, cell): """move forwards or backwards based on the validity of a cell""" if cell.is_valid(): self.backtrack_coord += 1 else: self.decrement_cell(cell) def solve(self): """run the other functions necessary for solving the sudoku puzzle""" self.move_forward() cell = self.set_cell() cell.increment_value() self.change_cells(cell) def run_solve(self): """runs the solver until we are at the end of the puzzle""" while self.backtrack_coord <= len(self.solve_puzzle) - 1: self.solve()def solve(puzzle): solver = SudokuSolver(puzzle) solver.initialize_board() solver.run_solve() return solver.puzzleTakeaways-urile mele
Uneori este nevoie doar de timp și de practică. Rezolvatorul Sudoku pe care am petrecut nenumărate ore de facultate m-a luat mai puțin de o oră câțiva ani mai târziu.
Voi spune că programele de informatică nu tind să înceapă într-un mod care să permită persoanelor care nu au scris cod mai devreme în viață să participe. În câțiva ani, politicile de educație în informatică se pot schimba. Dar, deocamdată, acest lucru elimină oamenii care au crescut în orașele mici, care nu erau interesați de codificarea crescândă sau care mergeau la licee mai slabe.
În parte, acest lucru contribuie cu siguranță la succesul codării bootcamp-urilor care încep cu elementele fundamentale și învață abilitățile de dezvoltare web mai puțin conceptuale decât algoritmi grei.
Acum pot scrie algoritmul de rezolvare Sudoku, dar nu cred că este o abilitate necesară pentru dezvoltatori – am devenit în continuare un inginer software de succes la scurt timp după aceea, când nu am putut implementa soluția Sudoku.
Cred că unele elemente fundamentale din domeniul informaticii pot fi foarte utile, chiar și pentru noii dezvoltatori. De exemplu, conceptele din spatele notării Big-O pot fi cu adevărat utile pentru a decide între abordări. Acestea fiind spuse, majoritatea structurilor de date și algoritmilor nu sunt folosiți în fiecare zi, așa că de ce sunt baza interviurilor și orelor de informatică în loc de lucrurile mai importante utilizate în fiecare zi?
Mă bucur să văd propria mea creștere personală în codificare; cu toate acestea, abia aștept o zi în care dezvoltatorii nu sar prin cercuri imaginare pentru a se dovedi și când mediile de învățare sunt mult mai constructive.
Dacă ți-a plăcut acest articol, te rog Abonati-va la newsletterul meu săptămânal unde veți primi linkurile mele preferate din săptămână și cele mai recente articole.
