Kuinka palasin takaisin vanhaan ongelmaan ja kirjoitin lopulta Sudoku-ratkaisualgoritmin

Tämä artikkeli on osittain tekninen, osittain henkilökohtainen tarina ja osa kulttuurikriittistä. Jos olet täällä vain saadaksesi koodin ja selityksen, siirry Alkuperäinen lähestymistapa -otsikkoon!

Tämä tarina alkaa muutama vuosi sitten yliopiston tietojenkäsittelytieteen luokkahuoneessa. Minulla oli epätavallinen polku koodin kirjoittamiseen - ilmoittautuin satunnaisesti tietojenkäsittelytieteen luokalle toisen korkeakoulun opiskeluvuoden aikana, koska minulla oli ylimääräinen luottotunti ja olin utelias, mistä siinä oli kyse. Ajattelin, että opimme käyttämään Microsoft Wordia ja Exceliä - minulla ei aidosti ollut aavistustakaan mikä koodi oli.

Lukioissani ei todellakaan ollut koodausluokkia, heillä oli tuskin toimivia tietokoneita! En myöskään pelannut videopelejä tai osallistunut aktiviteetteihin, jotka perinteisesti johtavat siihen, että lapset oppivat koodaamaan. Joten koodaus oli minulle aivan uutta, kun otin kyseisen Python-luokan yliopistossa.

Heti kun kävelin luokkahuoneessa, he pyysivät meitä kirjoittamaan Python-koodin Idle-tekstieditoriin, joka tulee Python-kielen mukana. He olivat painaneet koodin ja vain pyytäneet meitä kirjoittamaan sen ja suorittamaan sen - olin heti koukussa. Tämän luokan aikana rakensin Tic Tac Toe -komentosarjan, jossa oli graafinen käyttöliittymä kappaleiden syöttämiseen ja Flappy Bird -klooni. Se tuli rehellisesti minulle melko helposti, ja minulla oli hauskaa. Päätin nopeasti opiskella tietojenkäsittelytieteessä ja halusin kirjoittaa lisää koodia.

Seuraavan lukukauden aikana ilmoittautuin tietorakenteiden ja algoritmien kurssille, joka oli seuraavaksi tietojenkäsittelyjärjestyksessä. Luokkaa opetettiin C ++ -kurssilla, joka minun oli tietämättä opittu kesän aikana ennen luokkaa. Nopeasti kävi selväksi, että professorit yrittivät käyttää luokkaa opiskelijoiden suodattamiseksi - noin 50% ensimmäisenä päivänä ilmoittautuneista pääsi läpi lukukauden. Vaihdoimme jopa luokkahuoneet luentosalista break out -huoneeksi. Ylpeyteni oli ainoa asia, joka piti minut luokassa. Tunsin olevani täysin hukassa melkein jokaisessa oppitunnissa. Vietin monia koko yön töitä projekteissa ja opiskelin tenttejä varten.

Yksi ongelma sai minut todella saamaan - meidän piti rakentaa C ++ --ohjelma, joka ratkaisee kaikki Sudoku-ongelmat. Jälleen vietin lukemattomia tunteja tehtävässä yrittäen saada koodi toimimaan. Projektin eräpäivään mennessä ratkaisuni toimi joissakin testitapauksissa, mutta ei kaikissa. Päädyin saamaan C + -tehtävän - yksi pahimmista arvosanojeni koko yliopistossa.

Tämän lukukauden jälkeen luopuin ajatuksestani tietojenkäsittelytieteen sivuaineesta, lopetin koodaamisen kokonaan ja pidin kiinni siitä, mitä luulin olevani hyvä - kirjoittaminen ja politiikka.

Tietysti elämässä tapahtuu hauskoja asioita ja aloin tietysti koodata uudelleen, mutta kesti kauan tuntea olevani pätevä ohjelmoija.

Muutama vuosi myöhemmin ohjelmointimatkallani päätin yrittää uudelleen käyttää Sudokun ratkaisualgoritmia todistaakseni itselleni, että voisin toteuttaa sen nyt. Koodi ei ole täydellinen, mutta se ratkaisee melkein kaikki Sudoku-palapelit. Käydään läpi algoritmi ja sitten toteutus.

Sudoku-palapelit

Jos et ole pelannut Sudoku-pulmia aikaisemmin, ne ovat numeropulmia, joissa jokaisessa palapelin rivissä, sarakkeessa ja 3x3-neliössä numeroiden 1–9 on oltava täsmälleen kerran. Näiden pulmien ratkaisemiseen on paljon tapoja, joista monet voidaan toistaa tietokoneella henkilön sijaan. Yleensä, kun ratkaisemme ne tietokoneella, käytämme sisäkkäisiä taulukoita edustamaan Sudoku-levyä nä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]]

Kun ratkaisu on tehty, nollat ​​täytetään todellisilla numeroilla:

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

Alkuperäinen lähestymistapa

Koska en halunnut kirjoittaa täyttä testipakettia erilaisilla pulmilla, käytin CodeWarsin haasteita testatakseni itseni. Ensimmäinen ongelma, jonka kokeilin, oli tämä - missä kaikki pulmat olivat "helppoja" Sudokuksia, jotka voitiin ratkaista ilman monimutkaisempaa algoritmia.

Päätin kokeilla ja ratkaista Sudokus tavallani - mistä löydän mahdolliset numerot tilalle, pidän kirjaa niistä, ja jos on vain yksi mahdollinen numero, kytke se siihen pisteeseen. Koska nämä olivat helpompia Sudokuksia, tämä lähestymistapa toimi hyvin tälle Katalle, ja ohitin.

Tässä on (puhdistamaton) koodini!

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()

Halusin tietysti ratkaista myös vaikeampia Sudoku-pulmia, joten päätin toteuttaa monimutkaisemman algoritmin näiden pulmien ratkaisemiseksi.

Algoritmi

Yksi algoritmi Sudoku-pulmien ratkaisemiseksi on taaksepäin palaamisen algoritmi. Pohjimmiltaan yrität numeroita tyhjissä paikoissa, kunnes mahdollisia ei ole, sitten palaat takaisin ja kokeilet eri numeroita edellisissä paikoissa.

Ensimmäinen asia, jonka tein, oli jatkaa "helppoa" Sudoku-ratkaisijani lähestymistapaa löytääksesi mahdolliset arvot jokaiselle neliölle sen perusteella, mitkä arvot olivat jo kyseisen neliön rivillä, sarakkeessa ja laatikossa. Tallensin kaikki nämä arvot luetteloon, jotta voisin viitata niihin nopeasti, kun palasin takaisin tai etsin, mitä arvoa siinä neliössä käytetään.

Seuraavaksi minun täytyi toteuttaa esineiden sijoittaminen eteenpäin ja takaisin. Laitoin merkinnät jokaiselle antamattomalle tilalle (eli ne, jotka olivat nollia pelin alkaessa), jotta nämä tilat sisältyisivät takaisinvetoon ja annetut paikat eivät. Sitten iteroin näiden ratkaisemattomien paikkojen läpi. Laitoin ensimmäisen mahdollisen arvolistan kohteen kyseiseen kohtaan ja siirryin sitten seuraavaan ratkaisemattomaan kohtaan. Laittaisin sitten paikalle ensimmäisen mahdollisen arvon. Jos se on ristiriidassa edellisen aikavälin arvon kanssa, siirryn sitten mahdollisten arvojen luettelon toiseen kohtaan ja sitten seuraavaan paikkaan.

Tämä prosessi jatkuisi, kunnes tietylle paikalle ei ollut mahdollista siirtyä - toisin sanoen mahdollisen arvolistan loppu oli saavutettu eikä yksikään arvoista toiminut kyseisellä rivillä, sarakkeessa tai ruudussa. Sitten takaisinpalautusalgoritmi potkaisi.

Takaisinkytkennän sisällä koodi siirtyi takaisin viimeiseen täytettyyn kohtaan ja siirtyi seuraavaan mahdolliseen arvoon ja alkoi sitten siirtyä eteenpäin. Jos viimeinen mahdollinen arvo saavutettaisiin myös siinä paikassa, paluureittialgoritmi liikkuisi taaksepäin, kunnes oli piste, jota voitiin lisätä.

Kun palapelin loppu oli saavutettu oikeilla arvoilla jokaisessa neliössä, palapeli ratkaistiin!

Minun lähestymistapani

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?

Olen iloinen nähdessäni oman henkilökohtaisen kasvuni koodauksessa; En kuitenkaan voi odottaa päivää, jolloin kehittäjät eivät hyppää kuvitteellisten vanteiden läpi todistaakseen itsensä ja kun oppimisympäristöt ovat paljon rakentavampia.

Jos pidit tästä artikkelista, tilaa viikoittainen uutiskirjeeni, josta saat viikon suosikkilinkkini ja viimeisimmät artikkelini.