Kaip grįžau prie senos problemos ir pagaliau parašiau Sudoku sprendimo algoritmą

Šis straipsnis bus techninis, asmeninės istorijos ir kultūrinės kritikos dalis. Jei tik čia ieškote kodo ir paaiškinimo, pereikite prie antraštės „Pradinis požiūris“ !

Ši istorija prasidėjo prieš kelerius metus kolegijos informatikos kabinete. Turėjau netradicinį kelią į kodo rašymą - per antrus studijų metus atsitiktinai užsirašiau į informatikos būrelį, nes turėjau papildomą kredito valandą ir man buvo įdomu, apie ką tai. Maniau, kad mes išmoksime naudotis „Microsoft Word“ ir „Excel“ - aš tikrai nežinojau, kas yra kodas.

Mano vidurinėje mokykloje tikrai nebuvo jokių kodavimo klasių, jos beveik neturėjo veikiančių kompiuterių! Aš taip pat nežaidžiau vaizdo žaidimų ir nedalyvavau veikloje, dėl kurios vaikai tradiciškai išmoko koduoti. Taigi kodavimas man buvo visiškai naujas, kai lankiau tą „Python“ klasę kolegijoje.

Kai tik įėjau į klasę, jie privertė mus įvesti „Python“ kodą į „Idle“, teksto redaktorių, pateiktą kartu su „Python“ kalba. Jie atspausdino kodą ir tiesiog liepė mums jį įvesti ir paleisti - aš iškart buvau užsikabinęs. Per tą klasę sukūriau „Tic Tac Toe“ scenarijų su GUI, kad įvestumėte kūrinius ir „Flappy Bird“ kloną. Tai nuoširdžiai man atėjo gana lengvai, ir aš labai smagiai praleidau laiką. Greitai nusprendžiau pereiti į informatikos specialybę ir tiesiog norėjau parašyti daugiau kodo.

Kitą semestrą įstojau į duomenų struktūrų ir algoritmų kursą, kuris buvo kitas informatikos sekoje. Klasė buvo dėstoma C ++ kalba, kuri, man nežinant, turėjo būti išmokta vasarą prieš pamoką. Greitai tapo akivaizdu, kad profesoriai bandė naudoti klasę norėdami išfiltruoti studentus - maždaug 50% pirmąją dieną besimokančiųjų per semestrą. Mes netgi pakeitėme klases iš paskaitų salės į „break out“ kabinetą. Mano pasididžiavimas buvo vienintelis dalykas, laikantis mane klasėje. Kiekvienoje pamokoje jaučiausi visiškai pasimetusi. Aš praleidau daug naktų dirbdamas projektus ir mokydamasis egzaminų.

Viena problema mane tikrai privertė - turėjome sukurti programą C ++, kuri išspręstų visas „Sudoku“ problemas. Aš vėl praleidau daugybę valandų užduotyje, bandydamas suveikti kodą. Tuo metu, kai turėjo būti įvykdytas projektas, mano sprendimas buvo tinkamas kai kuriems bandomiesiems atvejams, bet ne visiems. Aš galų gale gavau savo užduoties C + - vieną blogiausių mano pažymių visoje kolegijoje.

Po to semestro atsisakiau minties apie kompiuterių specialybę, visiškai metiau kodavimą ir laikiausi to, kas, manau, man sekasi - rašymo ir politikos.

Žinoma, gyvenime nutinka juokingų dalykų, ir aš, aišku, vėl pradėjau koduoti, tačiau man prireikė daug laiko, kol pasijutau esąs kompetentingas programuotojas.

Visa tai pasakius, praėjus keleriems metams po savo programavimo kelionės nusprendžiau dar kartą įdiegti „Sudoku“ sprendimo algoritmą, kad galėčiau įrodyti sau, jog galiu jį įgyvendinti dabar. Kodas nėra tobulas, bet jis išspręs beveik bet kokį „Sudoku“ galvosūkį. Pereikime per algoritmą ir paskui įgyvendinimą.

Sudoku galvosūkiai

Jei dar nesate žaidę „Sudoku“ dėlionių, tai yra galvosūkiai, kurių kiekvienoje eilutėje, stulpelyje ir 3x3 kvadratėlyje turi būti tiksliai nurodytas skaičius 1–9. Šiems galvosūkiams spręsti yra daugybė būdų, iš kurių daugelį gali atkartoti kompiuteris, o ne žmogus. Paprastai spręsdami juos naudodami kompiuterį, naudosime įdėtus masyvus, kad vaizduotume „Sudoku“ lentą taip:

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]]

Kai bus išspręsta, nuliai bus užpildyti tikraisiais skaičiais:

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]]

Pradinis požiūris

Kadangi nenorėjau rašyti viso testų rinkinio su skirtingais galvosūkiais, išbandžiau „CodeWars“ iššūkius. Pirmoji problema, kurią bandžiau, buvo tokia - kai visi galvosūkiai buvo „lengvi“ Sudokus, kuriuos buvo galima išspręsti be sudėtingesnio algoritmo.

Nusprendžiau išbandyti „Sudokus“ taip, kaip aš asmeniškai darau - kur rasčiau galimus erdvės numerius, juos stebėsiu, o jei yra tik vienas galimas skaičius, prijunkite jį prie tos vietos. Kadangi tai buvo lengviau „Sudokus“, šis požiūris šiai Katai pasiteisino, ir aš praėjau.

Štai mano (neišvalytas) kodas!

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.puzzle
def sudoku(puzzle): sudoku = SudokuSolver(puzzle) return sudoku.find_spot()

Žinoma, norėjau išspręsti ir sunkesnius „Sudoku“ galvosūkius, todėl nusprendžiau įgyvendinti sudėtingesnį algoritmą, kad galėčiau išspręsti tuos galvosūkius.

Algoritmas

Vienas iš „Sudoku“ galvosūkių sprendimo algoritmų yra „backtracking“ algoritmas. Iš esmės jūs bandote skaičius tuščiose vietose, kol jų nėra, tada grįžtate atgal ir bandote skirtingus skaičius ankstesniuose lizduose.

Pirmas dalykas, kurį aš padariau, buvo tęsti savo „lengvą“ „Sudoku Solver“ metodą - surasti galimas kiekvieno kvadrato reikšmes pagal tai, kurios vertės jau buvo to kvadrato eilutėje, stulpelyje ir laukelyje. Aš visas šias reikšmes išsaugojau sąraše, kad galėčiau greitai jas nurodyti, kai grįžtama atgal arba randu, kurią vertę tame kvadrate naudoti.

Tada man reikėjo įgyvendinti elementų įdėjimo į kiekvieną erdvę judėjimą pirmyn ir atgal. Ant kiekvienos neduotos vietos uždėjau žymeklius (taigi tuos, kurie buvo nuliai, kai prasidėjo žaidimas), kad tos vietos būtų įtrauktos į atgalinį kelią, o jų nebūtų. Tada kartojau per tas neišspręstas vietas. Į tą vietą įdėčiau pirmą galimo vertės sąrašo elementą ir tada pereinčiau į kitą neišspręstą vietą. Tada į vietą įdėčiau pirmąją įmanomą tos vietos vertę. Jei tai prieštarautų ankstesnio lizdo vertei, tada pereisiu prie antrojo elemento galimų verčių sąraše ir tada pereisiu prie kito lizdo.

Tas procesas tęsis tol, kol tam tikroje vietoje nebuvo galimo judėjimo - tai yra, buvo pasiektas galimo reikšmių sąrašo pabaiga ir nė viena iš verčių neveikė toje eilutėje, stulpelyje ar laukelyje. Tada įsijungė grįžimo algoritmas.

Vykdant „backtracking“ kodą, jis grįžta į paskutinę užpildytą vietą ir pereina prie kitos galimos vertės, tada vėl pradeda judėti pirmyn. Jei paskutinė iš galimų verčių būtų pasiekta ir toje vietoje, grįžimo atgal algoritmas judėtų atgal, kol atsiras taškas, kurį būtų galima padidinti.

Pasiekus galvosūkio pabaigą su teisingomis vertėmis kiekviename kvadrate, galvosūkis buvo išspręstas!

Mano požiūris

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.puzzle

Hard 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?

Džiaugiuosi matydamas savo asmeninį kodavimo augimą; tačiau negaliu sulaukti dienos, kai kūrėjai nešoks per įsivaizduojamus ratus, kad įrodytų save, ir kai mokymosi aplinka kur kas konstruktyvesnė.

Jei jums patiko šis straipsnis, užsiprenumeruokite mano savaitinį naujienlaiškį, kuriame gausite mano mėgstamiausias savaitės nuorodas ir naujausius straipsnius.