Ovaj će članak biti dio tehničke, dijelom osobne priče, a dijelom kulturne kritike. Ako ste ovdje samo radi koda i objašnjenja, prijeđite na zaglavlje Inicijalni pristup !
Ova priča započinje prije nekoliko godina u učionici informatike na fakultetu. Imao sam neobičan put pisanja koda - nasumično sam se upisao na čas informatike tijekom druge godine faksa, jer sam imao dodatni kreditni sat i bio sam znatiželjan o čemu se radi. Mislio sam da ćemo naučiti koristiti Microsoft Word i Excel - iskreno nisam imao pojma što je to kod.
Moja srednja škola definitivno nije imala satove kodiranja, jedva su imala ispravna računala! Ni ja nisam igrao video igrice niti se bavio aktivnostima koje tradicionalno dovode do toga da djeca uče kako kodirati. Dakle, kodiranje mi je bilo potpuno novo kad sam pohađao taj tečaj Pythona na fakultetu.
Čim sam ušao u učionicu, natjerali su nas da upišemo Python kôd u Idle, uređivač teksta koji dolazi s jezikom Python. Ispisali su kod i samo su nas natjerali da ga upišemo i pokrenemo - odmah sam bio spojen. Tijekom te nastave izradio sam skriptu Tic Tac Toe s GUI-jem za unos dijelova i klopom Flappy Bird. Iskreno mi je to prilično lako došlo i jako sam se dobro zabavljao. Brzo sam se odlučio za malo računarskih znanosti i samo sam htio napisati još koda.
Sljedeći semestar upisao sam kolegij Strukture podataka i algoritmi koji je bio sljedeći u slijedu informatike. Predavanje se izvodilo na jeziku C ++, koji je, bez mog znanja, trebao biti naučen tijekom ljeta prije nastave. Brzo je postalo očito da profesori pokušavaju koristiti nastavu za filtriranje učenika - oko 50% upisanih prvoga je dana prošlo semestar. Čak smo i učionice iz predavaonice promijenili u sobu za odmor. Jedino me ponos držao u razredu. Osjećao sam se potpuno izgubljeno u gotovo svakoj lekciji. Mnogo sam noći proveo radeći na projektima i učeći za ispite.
Zapravo me doveo jedan problem - trebali smo izgraditi program na C ++-u koji će riješiti bilo koji Sudoku problem. Ponovno sam proveo bezbroj sati na zadatku pokušavajući postići da kod funkcionira. U trenutku kad je projekt trebao nastupiti, moje je rješenje uspjelo za neke test slučajeve, ali ne za sve. Na kraju sam dobio C + na zadatku - jedan od mojih najgorih ocjena na svim fakultetima.
Nakon tog semestra napustio sam svoju ideju manjinskog obrazovanja iz računalnih znanosti, potpuno napustio kodiranje i držao se onoga što sam smatrao dobrim - pisanja i politike.
Naravno, u životu se događaju smiješne stvari i očito sam opet počeo kodirati, ali trebalo mi je puno vremena da se osjećam kao da sam kompetentan programer.
Sve to, nekoliko godina kasnije na svom programskom putovanju, odlučio sam ponovno pokušati implementirati algoritam rješavanja Sudokua kako bih sebi dokazao da ga mogu implementirati sada. Kôd nije savršen, ali riješit će gotovo svaku zagonetku Sudokua. Prođimo kroz algoritam, a zatim i implementaciju.
Sudoku zagonetke
U slučaju da dosad niste igrali Sudoku zagonetke, to su zagonetke s brojevima u kojima svaki redak, stupac i kvadrat od 3x3 u slagalici moraju imati brojeve 1–9 predstavljene točno jednom. Postoji mnogo pristupa rješavanju ovih zagonetki, od kojih mnoge može reproducirati računalo umjesto osoba. Obično, kada ih riješimo pomoću računala, upotrijebit ćemo ugniježđene nizove za predstavljanje Sudoku ploče na sljedeći način:
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]]Kada se riješe, nule će se popuniti stvarnim brojevima:
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]]Početni pristup
Budući da mi se nije dalo pisati cjelovit testni paket s različitim zagonetkama, iskoristio sam izazove na CodeWarsu da bih se testirao. Prvi problem koji sam pokušao bio je ovaj - gdje su sve zagonetke bile "lagan" Sudokus koji se mogao riješiti bez složenijeg algoritma.
Odlučio sam pokušati riješiti Sudokus na način koji osobno radim - gdje bih pronašao moguće brojeve za prostor, pratio ih i ako postoji samo jedan mogući broj, priključio bih ga na to mjesto. Budući da je ovo bio lakši Sudokus, ovaj je pristup dobro funkcionirao za ovu Katu i prošao sam.
Evo mog (neočišćenog) koda!
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()Naravno, želio sam riješiti i teže Sudoku zagonetke, pa sam odlučio implementirati složeniji algoritam kako bih riješio te zagonetke.
Algoritam
Jedan algoritam za rješavanje Sudoku zagonetki je algoritam za vraćanje unazad. U osnovi, nastavljate pokušavati s brojevima na praznim mjestima sve dok ih nema, a zatim se vratite i isprobavate različite brojeve u prethodnim mjestima.
Prvo što sam učinio je da nastavim sa svojim "laganim" pristupom Sudoku rješavača pronalaženja mogućih vrijednosti za svaki kvadrat na temelju kojih su vrijednosti već bile u retku, stupcu i okviru tog kvadrata. Sve te vrijednosti pohranio sam na popis kako bih se mogao brzo pozvati na njih dok sam se vraćao unatrag ili pronalazio koju vrijednost upotrijebiti u tom kvadratu.
Dalje, trebao sam provesti pomicanje i vraćanje naprijed stavljanja predmeta u svaki prostor. Stavio sam markere na svaki nedani prostor (dakle one koji su bili nula kad je igra započela) kako bi ti razmaci bili uključeni u povratne tragove, a zadana mjesta neće biti. Zatim sam prošao kroz ta neriješena mjesta. Stavio bih prvu stavku mogućeg popisa vrijednosti na to mjesto, a zatim bih prešao na sljedeće neriješeno mjesto. Tada bih na njegovo mjesto stavio prvu moguću vrijednost tog mjesta. Ako je u sukobu s vrijednošću prethodnog mjesta, prešao bih na drugu stavku na popisu mogućih vrijednosti, a zatim bih prešao na sljedeći utor.
Taj bi se postupak nastavio sve dok nije bilo mogućeg pomicanja za određeno mjesto - odnosno, došao je kraj mogućeg popisa vrijednosti i nijedna od vrijednosti nije radila u tom retku, stupcu ili okviru. Zatim se uključio algoritam za vraćanje unazad.
Unutar implementacije vraćanja unazad, kôd bi se vratio na posljednje mjesto koje je bilo popunjeno i pomaknuo se na sljedeću moguću vrijednost, a zatim bi se opet počeo kretati naprijed. Kad bi se i na tom mjestu postigla posljednja od mogućih vrijednosti, algoritam za vraćanje unatrag nastavio bi se kretati unatrag dok ne bi došlo do mjesta koje se može povećati.
Nakon što je kraj zagonetke dosegnut s točnim vrijednostima na svakom kvadratu, zagonetka je riješena!
Moj pristup
I like object oriented approaches, so I have two different classes in my solution: one for the cell and one for the Sudoku board. My very imperfect code looks like this:
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.puzzleHard Sudoku Solver
My Takeaways
Sometimes it just takes time and practice. The Sudoku solver I spent countless college hours on took me less than an hour a few years later.
I will say that computer science programs don’t tend to start in a way that allows people who didn’t write code earlier in life to participate. In a few years, computer science education policies may change. But for now, this eliminates people who grew up in small towns, who weren’t interested in coding growing up, or who went to weaker high schools.
In part, this definitely contributes to the success of coding bootcamps which start with the fundamentals and teach the less conceptual web development skills rather than heavy algorithms.
I can now write the Sudoku solving algorithm, but I don’t think it’s a necessary skill for developers to have — I still became a successful software engineer shortly after that time when I couldn’t implement the Sudoku solver.
I do think that some computer science fundamentals can be very helpful, even for new developers. For example, the concepts behind Big-O notation can be really helpful for deciding between approaches. That being said, most data structures and algorithms aren’t used on a day to day basis, so why are they the basis for interviews and computer science classes instead of the more important things used every day?
I’m happy to see my own personal growth in coding; however, I can’t wait for a day when developers aren’t jumping through imaginary hoops to prove themselves, and when learning environments are much more constructive.
If you liked this article, please subscribe to my weekly newsletter where you’ll receive my favorite links from the week and my latest articles.