Hvordan jeg kom tilbage til et gammelt problem og til sidst skrev en Sudoku-løsningsalgoritme

Denne artikel vil være del teknisk, del personlig historie og del kulturel kritik. Hvis du bare er her for koden og forklaringen, skal du hoppe til overskriften The Initial Approach !

Denne historie starter for et par år siden i et college i datalogi. Jeg havde en utraditionel vej til at skrive kode - Jeg tilmeldte mig tilfældigt et datalogikundervisning i mit andet år på college, fordi jeg havde en ekstra kredit time, og jeg var nysgerrig efter, hvad det handlede om. Jeg troede, vi ville lære at bruge Microsoft Word og Excel - jeg havde virkelig ingen idé om, hvad kode var.

Min gymnasium havde bestemt ingen kodningskurser, de havde knap fungerende computere! Jeg spillede heller ikke videospil eller deltog i aktiviteter, der traditionelt førte til, at børn lærte at kode. Så kodning var helt ny for mig, da jeg tog den Python-klasse på college.

Så snart jeg gik ind i klasseværelset, fik de os til at skrive Python-kode i Idle, en teksteditor, der følger med Python-sproget. De havde udskrevet koden og bare fik os til at skrive den ind og køre den - jeg blev straks hooked. I løbet af denne klasse byggede jeg et Tic Tac Toe-script med en GUI til inputstykker og en Flappy Bird-klon. Det kom ærligt talt ganske let til mig, og jeg havde masser af sjov. Jeg besluttede hurtigt at undervise i datalogi, og jeg ville bare skrive mere kode.

Det næste semester tilmeldte jeg mig et kursus i datastrukturer og algoritmer, som var næste i datalogisk rækkefølge. Klassen blev undervist i C ++, som, uden at jeg vidste det, skulle læres i løbet af sommeren før klassen. Det blev hurtigt tydeligt, at professorerne forsøgte at bruge klassen til at filtrere eleverne ud - omkring 50% af tilmeldte på dag 1 kom igennem semesteret. Vi skiftede endda klasseværelser fra en forelæsningssal til et brydningsrum. Min stolthed var det eneste, der holdt mig i klassen. Jeg følte mig helt fortabt i stort set hver lektion. Jeg brugte mange all-nighters til at arbejde på projekter og studere til eksamen.

Især et problem fik mig virkelig - vi skulle bygge et program i C ++, der ville løse ethvert Sudoku-problem. Igen brugte jeg utallige timer på opgaven med at prøve at få koden til at fungere. Da projektet skulle udløbe, fungerede min løsning i nogle af testsagerne, men ikke alle. Jeg endte med at få en C + på min opgave - en af ​​mine værste karakterer på hele college.

Efter dette semester opgav jeg min idé om undervisning inden for datalogi, holdt op med at kode og holdt fast ved det, jeg troede, jeg var god til - skrivning og politik.

Selvfølgelig sker der sjove ting i livet, og jeg begyndte naturligvis at kode igen, men det tog mig lang tid at føle, at jeg var en kompetent programmør.

Alt dette sagt besluttede jeg et par år senere i min programmeringsrejse at prøve at implementere Sudoku-løsningsalgoritmen for at bevise for mig selv, at jeg kunne implementere den nu. Koden er ikke perfekt, men den løser stort set ethvert Sudoku-puslespil. Lad os gennemgå algoritmen og derefter implementeringen.

Sudoku puslespil

Hvis du ikke har spillet Sudoku-puslespil før, er det nummerpuslespil, hvor hver række, kolonne og 3x3 firkant i puslespillet skal have tallene 1–9 repræsenteret nøjagtigt en gang. Der er mange tilgange til løsning af disse gåder, hvoraf mange kan replikeres af en computer i stedet for en person. Når vi løser dem ved hjælp af en computer, bruger vi normalt indlejrede arrays til at repræsentere Sudoku-kortet sådan:

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

Når det er løst, udfyldes nuller med aktuelle tal:

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

Den første tilgang

Fordi jeg ikke havde lyst til at skrive en komplet testpakke med forskellige gåder, brugte jeg udfordringerne på CodeWars til at teste mig selv. Det første problem, jeg prøvede, var dette - hvor alle gåderne var “lette” Sudokus, der kunne løses uden en mere kompleks algoritme.

Jeg besluttede at prøve at løse Sudokus på den måde, jeg personligt gør - hvor jeg ville finde de mulige tal til et mellemrum, holde styr på dem, og hvis der kun er et muligt nummer, skal du tilslutte det til det sted. Da disse var lettere Sudokus, fungerede denne tilgang fint for denne Kata, og jeg bestod.

Her er min (urensede) kode!

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

Selvfølgelig ville jeg også løse sværere Sudoku-gåder, så jeg besluttede at implementere en mere kompleks algoritme for at løse disse gåder.

Algoritmen

En algoritme til løsning af Sudoku-gåder er backtracking-algoritmen. I det væsentlige fortsætter du med at prøve numre i tomme pletter, indtil der ikke er nogen, der er mulige, så trækker du tilbage og prøver forskellige numre i de foregående slots.

Den første ting, jeg gjorde, var at fortsætte min “lette” Sudoku-opløsers tilgang til at finde de mulige værdier for hver firkant baseret på hvilke værdier der allerede var i kvadratets række, kolonne og boks. Jeg lagrede alle disse værdier på en liste, så jeg hurtigt kunne henvise til dem, mens jeg backtrackede eller fandt, hvilken værdi jeg skulle bruge i den firkant.

Dernæst havde jeg brug for at implementere fremadgående bevægelse og backtracking af at sætte genstande i hvert rum. Jeg satte markører på hvert ikke-givne mellemrum (så dem der var nuller, da spillet startede), så disse mellemrum ville blive inkluderet i backtracking og givne pletter ikke ville være. Derefter gentog jeg mig gennem disse uløste pletter. Jeg ville placere det første element på den mulige værdiliste på stedet og derefter flytte til det næste uløste sted. Jeg vil derefter sætte den første mulige værdi af stedet på stedet. Hvis det var i modstrid med værdien af ​​det forrige slot, flyttede jeg derefter til det andet punkt på listen over mulige værdier og flyttede derefter til det næste slot.

Denne proces ville fortsætte, indtil der ikke var nogen mulig bevægelse for et givet sted - det vil sige, slutningen af ​​den mulige værdiliste blev nået, og ingen af ​​værdierne arbejdede i den række, kolonne eller boks. Derefter startede backtracking-algoritmen.

Inden for backtracking-implementeringen flyttede koden tilbage til det sidste sted, der blev udfyldt, og flyttede til den næste mulige værdi og begyndte derefter at bevæge sig frem igen. Hvis den sidste af de mulige værdier også blev nået på det sted, ville backtracking-algoritmen fortsætte med at bevæge sig bagud, indtil der var et sted, der kunne øges.

Når slutningen af ​​puslespillet var nået med korrekte værdier i hver firkant, blev puslespillet løst!

Min tilgang

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?

Jeg er glad for at se min egen personlige vækst i kodning; dog kan jeg ikke vente på en dag, hvor udviklere ikke hopper gennem imaginære bøjler for at bevise sig selv, og når læringsmiljøer er meget mere konstruktive.

Hvis du kunne lide denne artikel, skal du abonnere på mit ugentlige nyhedsbrev, hvor du modtager mine yndlingslinks fra ugen og mine seneste artikler.