Автоматизируйте с помощью Python за несколько дней, когда это можно сделать за считанные минуты :)
Решатель судоку Python
Ленивый способ решить судоку с помощью Python!
Введение:
Я пишу эту статью для записи в будущем, а также для того, чтобы отметить мой путь в программировании. Я постараюсь каждую неделю писать один блог о забавных проектах по программированию. Я сосредоточусь в основном на Python и машинном обучении или искусственном интеллекте в целом. Я мог бы также сделать несколько вводных статей о блокчейне и криптографии. Посмотрим, как получится!
Вдохновение:
У меня уже давно была идея сделать Python Sudoku Solver. Пока я смотрел видео Computerphile на YouTube, я наткнулся на видео о Python Sudoku Solver. Но это было очень по делу и не очень понятно.
Итак, я решил разбить каждый шаг и объяснить на уровне новичка.
Если вы знакомы с правилами головоломки судоку, вы можете пропустить следующий абзац.
Судоку:
Изображение предоставлено: https://www.freepik.com/photos/puzzle фото-пазл, созданное freepik — www.freepik.com
Это сетка прямоугольников размером 9 X 9.
По сути, это игра с тремя основными правилами. Вы должны поместить число (или целое число в терминах программирования) во все поля. Но
Числа не должны повторяться в одном и том же
- Строка
- Столбец
- Коробка (3X3)
Примечание. У головоломки судоку может быть более 1 решения.
С этим покончено, давайте перейдем к техническим аспектам!
Основные понятия:
Я перечислил некоторые основные понятия, которые будут использоваться в этом уроке. Хотя я пытался объяснить это, но вы также можете использовать Youtube или Google, чтобы лучше понять.
- Двумерные списки (или массивы) — необязательно
- Numpy (только Matrix) — необязательно
- Рекурсия (примерно похоже на начальный фильм). Это видео может помочь(https://www.youtube.com/watch?v=Mv9NEXX1VHc&ab_channel=Computerphile)
- Обратное отслеживание (пробная версия и ошибка)
- Немного математики
Приступим:
Сначала назначьте строки как списки в один список. (Вы узнаете, почему это важно.)
Code:
import numpy as np
grid = [[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]]
print("-------Unsolved------")
print(np.matrix(grid))
Output:
-------Unsolved------
[[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]]
Process finished with exit code 0
Мы сделаем это в трех разделах.
- Проверка числа в строке
- Проверка числа в столбце
- Проверка номера в ящике
Мы определим функцию для проверки строки, а затем добавим к ней проверку столбца. Мы сделаем другую функцию для коробки (это немного сложнее)
-Проверка числа в строке:
Давайте начнем с проверки того, находится ли нужное нам число в той же строке или нет. Мы можем использовать простой цикл for, который будет проверять каждое число в строке, которую мы передаем в качестве аргумента функции.
# x for rows
# y for columns
# i for iterations. duh!!
def possible(y, x, n):
global grid
# Checking Rows
for i in range(0, 9):
if grid[x][i] == n:
return False
Эта функция вернет False, если число (n) уже находится в строке, которую мы определили.
-Проверка числа в столбце:
Теперь давайте добавим в эту функцию проверку столбцов…
def possible(y, x, n):
global grid
# Checking Rows
for i in range(0, 9):
if grid[x][i] == n:
return False
# Checking Columns
for i in range(0, 9):
if grid[i][y] == n:
return False
Эта функция возвращает False, если число (n) находится либо в том же столбце, либо в той же строке.
-Проверка числа в поле (3X3):
Чтобы установить флажок, вам нужно знать математический термин, известный как Floor Division (пожалуйста, Google или Youtube).
# Checking the Box (3X3)
x0 = x//3 * 3
y0 = y//3 * 3
for i in range(0, 3):
for j in range(0, 3):
if grid[x0+i][y0+j] == n:
return False
Первые две строки - это математика. Проще говоря, он сбрасывает сетку на определенное число для набора чисел. Мы используем это, чтобы получить начало поля для любого числа в любом поле. Например,
начало будет равно 0, если x = 0 или 1 или 2
аналогично, начало равно 3, если x = 3, 4 или 5
и 6, в то время как x = 6, или 7, или 8 .
Посмотрите, как это сбрасывает любое число в блоке на начальную точку этого блока.
Двигаясь дальше, мы используем вложенный цикл for с диапазоном 3. Чтобы проверить блоки 3x3 Box.
Кроме того, мы добавляем i и j в x0 и j0 соответственно для проверки следующего блока и следующего блока и т.д. последний блок в коробке.
С этим мы можем зациклить (i и j) и проверить все 9 блоков 1 на 1, чтобы увидеть, находится ли число (n) уже в коробке или нет.
Первый раздел завершен:
def possible(y, x, n):
global grid
# Checking Rows
for i in range(0, 9):
if grid[x][i] == n:
return False
# Checking Columns
for i in range(0, 9):
if grid[i][y] == n:
return False
# Checking the Box (3X3)
x0 = x//3 * 3
y0 = y//3 * 3
for i in range(0, 3):
for j in range(0, 3):
if grid[x0+i][y0+j] == n:
return False
return True
До сих пор мы сделали проверку, чтобы увидеть, можно ли поставить число в определенную позицию в головоломке. Но по мере программирования наша лень побуждает нас автоматизировать весь процесс. Вместо того, чтобы проверять каждое поле вручную.
Кроме того, второй раздел предназначен не только для автоматизации, но и дает еще одну важную функцию нашей программе, а именно метод проб и ошибок. Потому что возможно () только говорит нам, может ли число быть помещено в определенную позицию, но может быть много возможностей для конкретной позиции. Наш выбор сейчас может оказаться неверным позже. Вот почему нам нужен метод проб и ошибок (откат и рекурсия).
Второй раздел:
Мы прокручиваем все числа от 0 до 8 в строках и столбцах, чтобы проверить позицию с помощью Possible(). Но сначала мы проверяем, пуста ли позиция, т. е. 0. Затем с помощью возможного() и цикла проверяем, какое из чисел мы можем поместить туда в данный момент (мы можем ошибаться и не поместим то же самое число снова и снова, поэтому я использую способный поставить в настоящее время)
def solver():
global grid
for x in range(9):
for y in range(9):
if grid[x][y] == 0:
for n in range(1, 10):
if possible(y, x, n):
Теперь мы собираемся использовать самый важный и сложный метод решения этой головоломки.
Рекурсия:
Попробуйте понять рекурсию, используя этот мем:
Посмотрите, как вы получили ответ на 5-й рекурсии. Вот когда вы выходите из рекурсии. Используйте компьютерофил с этим мемом, чтобы понять его правильно!
Проще говоря, в этом методе мы продолжаем находить ответ и помещать его в пустое место до тех пор, пока не сможем найти ответ для следующей пустой позиции. В случае чего возвращаемся. Но мы вернули из рекурсивной функции не основную или самую внешнюю функцию. Пересмотрите видео рекурсии, если вы чувствуете себя потерянным.
Отслеживание:
Итак, если нам не удается найти все ответы с номером, мы просто меняем его на ноль и пробуем следующий номер. Гугл: Возврат. Чтобы понять, как мы используем метод проб и ошибок, чтобы решить эту проблему.
Этот процесс рекурсии и возврата будет продолжаться до тех пор, пока мы не найдем ответы на все пустые места, которые удовлетворяют нашим условиям в возможном ().
Это когда мы возвращаемся из нашей основной функции или самого внешнего слоя нашей функции.
Окончательно,
def solver():
global grid
# Checking Rows (Lists in the grid(main list) )
for x in range(9):
# Checking Columns (Each number in the current list)
for y in range(9):
# Checking for empty position
if grid[x][y] == 0:
# Looping through 1-9 numbers to see
# what num to we can put here currently
for n in range(1, 10):
if possible(y, x, n):
# if it's possible, lets put the
# number in that position
grid[x][y] = n
# Recall Recursion at this
# point from the video.
# This is complicated
# but you can handle it.
solver()
# If the function fails to find the
# answer for the next empty it will
# return and we will know we were wrong.
# And set the value back to zero
# and try a new number (Backtracking).
# Imp Note: One number is being checked
# for the whole puzzle in Recursion.
grid[x][y] = 0
# This return will be used in the above
# called function when we want to
# get out of the recursion(or inception)
return
print("-------Solved------")
print(np.matrix(grid))
solver()
# Don't break your keyboard because you haven't called the function XD
Если вы чувствуете себя потерянным в какой-либо момент, связанный с возвратом или рекурсией, просто погуглите или найдите учебник Computerphile на YouTube об этом.
Также посмотрите это видео для обзора этой головоломки: https://www.youtube.com/watch?v=G_UYXzGuqvM&ab_channel=Computerphile
Что ж, это была моя первая статья, и я надеюсь стать лучше в написании и своих знаниях.
Следите за дальнейшими блогами, посвященными интересным проектам Python и компьютерным наукам (особенно ML, AI, Crypto и Tech).
ДжазакАллах за чтение и ваши отзывы очень много для меня значат.
Этот блог также является закладкой для моего будущего себя, чтобы сравнить, лучше ли я сегодня, когда я писал это!
Процесс завершен с кодом выхода 0
