Как я вернулся к старой проблеме и наконец написал алгоритм решения судоку

1656590419 kak ya vernulsya k staroj probleme i nakonecz napisal algoritm

автор Али Шпиттель

euiCV5aBysXWtj-7plytDtE1tQZDzlowm8gw
Фото Майка Уилсона на Unsplash

Эта статья будет отчасти технической, отчасти личной историей и отчасти культурной критикой. Если вы только для кода и объяснений, перейдите к Начальный подход заголовок!

Эта история начинается несколько лет назад в кабинете информатики колледжа. У меня был нетрадиционный путь к написанию кода — я случайно записался на урок информатики на втором курсе колледжа, потому что у меня был дополнительный кредитный час, и мне было интересно, о чем идет речь. Я думал, что мы научимся использовать Microsoft Word и Excel — я не знал, что такое код.

В моей средней школе точно не было никаких кодировочных классов, у них почти не было функционирующих компьютеров! Я также не играл в видеоигры и не занимался мероприятиями, традиционно ведущими к тому, чтобы дети учились кодированию. Поэтому кодировка была новой для меня, когда я проходил курс Python в колледже.

Как только я вошел в класс, они попросили нас ввести код Python в Idle, текстовый редактор, поставляемый с языком Python. Они распечатали код и просто попросили нас ввести его и запустить – я сразу зацепился. В течение этого занятия я создал сценарий Tic Tac Toe с графическим интерфейсом для ввода фрагментов и клоном Flappy Bird. Честно говоря, мне это далось достаточно легко, и я получил массу удовольствия. Я быстро решил заняться компьютерными науками, и я просто хотел написать больше кода.

В следующем семестре я записался на курс «Структур данных и алгоритмов», следующий в последовательности информатики. Урок преподавался на C++, который, я не знаю, должен был учить за лето перед уроком. Быстро стало очевидно, что преподаватели пытались использовать класс, чтобы отфильтровать студентов — около 50% зачисленных в первый день прошли семестр. Мы даже сменили классные комнаты с лекционной комнаты для отдыха. Моя гордость была единственным, что держало меня в классе. Практически на каждом уроке я чувствовал себя совершенно растерянным. Я провел много ночей, работая над проектами и готовясь к экзаменам.

Одна проблема меня особенно увлекла — мы должны были создать программу на C++, которая решила бы любую проблему судоку. Снова я потратил бесчисленное количество часов на выполнение задания, пытаясь заставить код работать. К тому времени, когда проект был завершен, мое решение работало для некоторых тестовых случаев, но не для всех. В итоге я получил C+ за свою задачу — одну из моих самых плохих оценок во всем колледже.

После этого семестра я отказался от своей идеи заниматься компьютерными науками, полностью бросил программирование и занялся тем, в чем я считал, что умею хорошо писательской деятельностью и политикой.

Конечно, в жизни случаются забавные вещи, и я, очевидно, снова начал кодировать, но мне понадобилось много времени, чтобы почувствовать себя компетентным программистом.

Все это было сказано, через несколько лет, когда я начал программировать, я решил еще раз попытаться реализовать алгоритм решения судоку, чтобы доказать себе, что могу реализовать его сейчас. Код не идеален, но он решит почти любую головоломку судоку. Давайте пройдемся по алгоритму, а затем по реализации.

Пазлы судоку

NGyo6kOiNfPdOzeV5RfN8K4SUw0Jxw0LOraz

Если вы раньше не играли в головоломки Судоку, это числовые головоломки, в которых каждая строка, столбец и квадрат 3×3 в головоломке должны иметь числа 1–9, представленные ровно один раз. Есть много подходов к решению этих головоломок, многие из которых можно воспроизвести компьютером, а не человеком. Обычно, когда мы решаем их с помощью компьютера, мы используем вложенные массивы для представления судоковой доски следующим образом:

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

После решения нули будут заполнены реальными числами:

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

Начальный подход

Поскольку мне не хотелось писать полный набор тестов с разными головоломками, я использовал задачи на CodeWars, чтобы проверить себя. Первая проблема, которую я попробовал, заключалась в этой – где все головоломки были «легкими» судоку, которые можно было решить без более сложного алгоритма.

Я решил попытаться разгадать судокус так, как это делаю я лично – где я нахожу возможные числа для пробела, отслеживаю их, и если есть только одно возможное число, подключаю его к этому месту. Поскольку это были легче судоку, этот подход хорошо сработал для этого палача, и я прошел.

Вот мой (неочищенный) код!

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

Конечно, я также хотел решить более сложные головоломки судоку, поэтому решил реализовать более сложный алгоритм, чтобы разгадать эти головоломки.

Алгоритм

Одним из алгоритмов решения головоломок судоку является алгоритм возвращения назад. По сути вы продолжаете пробовать числа на пустых местах, пока не станет возможных, а затем возвращаетесь назад и пробуете другие числа в предыдущих слотах.

XHVFcJhCX-mRMxvSBvuWMQuEw1eipOCxKWBS
Спасибо Википедии за отличную визуализацию!

Первое, что я сделал, — это продолжил свой «легкий» подход судоку: находил возможные значения для каждого квадрата на основе того, какие значения уже были в строке, столбце и поле этого квадрата. Я сохранил все эти значения в списке, чтобы я мог быстро обратиться к ним, возвращаясь назад или находя, какое значение использовать в этом квадрате.

Далее мне нужно было реализовать движение вперед и назад для размещения элементов в каждом пространстве. Я поставил маркеры на каждый непредоставленный пробел (поэтому те, которые были нулями к моменту начала игры), чтобы эти пробелы были включены в обратное отслеживание, а заданные места не были. Потом я перебирал эти нерешенные места. Я поместил бы первый элемент из списка возможных значений в это место, а затем перешел бы к следующему нерешенному месту. Тогда я поставил бы первое возможное значение этого места на его место. Если это противоречит значениям предыдущего слота, я перешел бы ко второму пункту в списке возможных значений, а затем перешел бы к следующему слоту.

Этот процесс будет продолжаться до тех пор, пока не будет возможного перемещения для данного места, то есть до конца списка возможных значений, и ни одно из значений не работает в этой строке, столбце или поле. Затем заработал алгоритм возврата.

В рамках реализации обратной отслеживания код возвращался к последнему заполненному месту и переходил к следующему возможному значению, а затем снова начинал двигаться вперед. Если в этом месте также будет достигнуто последнее из возможных значений, алгоритм обратного движения продолжал двигаться назад, пока не будет увеличить место.

Как только конец головоломки был достигнут с правильными значениями в каждом квадрате, головоломка была разгадана!

Мой подход

Мне нравятся объектно-ориентированные подходы, поэтому в моем решении есть два разных класса: один для ячейки, а второй для доски судоку. Мой очень несовершенный код выглядит так:

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

Сложный решатель судоку

Мои блюда на вынос

Иногда просто нужно время и практика. Решитель судоку, на который я потратил бесчисленное количество часов в колледже, занял у меня меньше часа через несколько лет.

Я скажу, что программы по информатике не имеют тенденции начинаться так, чтобы участвовать люди, ранее не писавшие код. Через несколько лет политика образования по информатике может измениться. Но сейчас это исключает людей, выросших в небольших городах, которые в детстве не интересовались программированием или учились в более слабых школах.

Частично это, безусловно, способствует успеху курсов программирования, которые начинаются с основ и обучают менее концептуальным навыкам веб-разработки, а не тяжелым алгоритмам.

Теперь я могу писать алгоритм решения судоку, но я не считаю, что это необходимый навык для разработчиков — я все еще стал успешным инженером программного обеспечения вскоре после того, как не мог реализовать судоку.

Я думаю, что некоторые основы информатики могут быть очень полезны даже для новичков. К примеру, концепции обозначения Big-O могут быть действительно полезны для выбора между подходами. Учитывая это, большинство структур данных и алгоритмов не используются ежедневно, почему же они являются основой для интервью и уроков информатики, а не для более важных вещей, которые используются ежедневно?

Я рад видеть свой личный рост в программировании; однако я не могу дождаться дня, когда разработчики не будут прыгать через воображаемые обручи, чтобы доказать себя, и когда учебная среда станет намного конструктивнее.

Если вам понравилась эта статья, подпишитесь на мой еженедельный информационный бюллетень, где вы будете получать мои любимые ссылки за неделю и мои последние статьи.

Добавить комментарий

Ваш адрес email не будет опубликован.