קוד לפתרון סודוקו בעזרת אלגוריתם backtracking גישוש נסוג

בפאזל סודוקו סטנדרטי יש טבלה של 81 תאים תוצאה של 9 שורות לגובה ו-9 עמודות לאורך 9X9 את הטבלה הזו מחלקים ל-9 טבלאות משנה של 3X3. המטרה היא למלא את הטבלה הגדולה כך שבכל שורה, עמודה וטבלת משנה בודדים יהיו כל המספרים 1-9. ומכאן, שבכל עמודה, שורה ותת טבלה אסור למספרים לחזור על עצמם.

בשביל שיהיה לי קל לפתח את הקוד השתמשתי בגרסה מפושטת של משחק סודוקו המונה 4X4 תאים. בהמשך נראה שאת העקרונות שנפתח לצורך פתרון הבעיה הקלה נוכל להרחיב בקלות לפתרון הגרסה הסטנדרטית של סודוקו.

• הטבלה מונה 4X4 תאים ו-4 תת טבלאות של 2X2.
• המספרים אותם ניתן להציב הם 1 - 4.
• תא ריק מכיל את הספרה 0.

את הפתרון נחלק ל-3 חלקים:

1. מציאת התאים שבהם יש להציב מספרים
2. ניסיון להציב מספר, אם אפשר, מה שאומר שצריך לוודא את המספר לפני הצבתו
3. אם בהמשך ההצבה שעשינו לא מובילה לפתרון אז להחזיר את המצב למה שהיה בתא קודם ולנסות אפשרות אחרת

הרעיון הוא לנסות אפשרות מסוימת, ואם בהמשך מגלים שהיא לא עובדת, לחזור למצב הקודם לפני שעשינו את הניסוי, וממצב זה לנסות אפשרות אחרת עד שמוצאים אפשרות שעובדת או עד שמנסים את כל האפשרויות. בעולם התכנות קוראים לזה אלגוריתם backtracking "גישוש נסוג". במקרה שלנו, האלגוריתם מנסה להציב, אם אפשר, מספר בתא ריק של טבלת הסודוקו. אם המספר ניתן להצבה, כי אין קונפליקטים עם ספרות זהות באותה שורה, עמודה או תת טבלה, האלגוריתם קורא לעצמו באופן רקורסיבי כדי למצוא פתרונות החל מהתא הריק הבא. אם יסתבר בהמשך שהמספר שהוצב מוביל למצב שאינו מאפשר את פתרון הפאזל, הקוד יחזור לאחור backtrack וינסה להציב מספר אחר בתא.

הדגמתי את העיקרון של backtracking "גישוש נסוג" לצורך פתרון החידה של N מלכות שם הצפי הוא ליותר מפתרון אחד, ושם גם אפשר לראות את כוחו של האלגוריתם לצורך מציאת כל הקומבינציות של הפתרון. במקרה שלנו, בשביל לפתור סודוקו, הנחתי שלכל לוח יש פתרון אחד בלבד.

נתחיל מכתיבת פונקציה לוידוא האם ניתן להציב מספר בתא ריק.

הפונקציה צריכה להחזיר תוצאה בוליאנית: True במידה וניתן להציב את המספר, False אם לא ניתן.

הפונקציה צריכה לוודא 3 דברים עבור המספר אותו מנסים להציב:

• אם נמצא מספר זהה באותה עמודה
• אם נמצא מספר זהה באותה שורה
• אם נמצא מספר זהה באותה תת טבלה

את הטבלה נגדיר באמצעות מערך דו-מימדי, לדוגמה:

# Simplified 4X4 grid
grid = [[4, 0, 1, 0],
        [0, 0, 0, 4],
        [3, 0, 4, 2],
        [2, 4, 0, 1]]

• 4 שורות מוחזקות בתוך 4 מערכים, בכל מערך 4 מספרים, ו-4 המערכים מוחזקים בתוך מערך חיצוני.
• 0 מציין תא ריק אותו צריך להחליף במספר.

פונקציה לבדיקת מספר לפני הצבתו בתא ריק

נגדיר פונקציה is_valid() שתוודא האם ניתן להציב את המספר number אותו מעבירים לה כפרמטר בתא שהקואורדינטות שלו בטבלה grid הם x ו-y:

def is_valid(grid, x, y, number):     
    pass

כדי לוודא שהמספר לא קיים כבר באותה עמודה נעבור על כל התאים בעמודה בתוך לולאה ואם באחד התאים יימצא המספר הפונקציה תחזיר False כיוון שחוקי המשחק אוסרים את הצבת המספר בתא:

# Validate that `number` is not in the same column
for n in range(0, 4):
    if grid[n][x] == number:
        return False

• הלולאה עוברת על 4 אינדקסים כיוון שזה מספר התאים בעמודה כי אנחנו פותרים סודוקו של 4X4

באופן דומה, כדי לוודא שהמספר לא קיים כבר באותה שורה נעבור על כל התאים בשורה ואם באחד התאים יימצא המספר הפונקציה תחזיר False כיוון שלא ניתן להציב את המספר:

# Validate that `number` is not in the same row
for n in range(0, 4):
    if grid[y][n] == number:
        return False

כדי לוודא האם המספר נמצא כבר באותה תת טבלה נשתמש בלוגיקה שתוחמת את החיפוש.

אם את התא שמעניין אותנו מציינות הקואורדינטות (0, 0) אז תחום החיפוש יכלול את תת הטבלה :

• 3 התאים הנותרים בתת הטבלה (1,0)(0,1)(1,1) גם הם כלולים באותו תחום חיפוש.

אם התא שמעניין אותנו נמצא בקואורדינטות (2,0) אז הוא שייך לתת הטבלה:

אפשר להסתכל על האינדקסים:

• אם אנחנו מעוניינים לבדוק עבור תא באינדקס 0 אז צריך לבדוק את כל התאים המצויים באינדקסים 0 ו-1
• עבור תא באינדקס 1 נבדוק את האינדקסים 0 ו-1
• עבור תא באינדקס 2 נבדוק את האינדקסים 2 ו-3
• עבור תא באינדקס 3 נבדוק את האינדקסים 2 ו-3

מה עוד אנחנו יודעים?

תתי טבלאות של 2X2 מרכיבים טבלה של 4X4 כמו שתתי טבלאות של 3X3 מרכיבים טבלה של 9X9.

זאת אומרת שהיחס 4 ל-2 הוא כמו היחס 9 ל-3.

זה יחס של הוצאת שורש ריבועי.

בהתאם, נחשב את ממדי תת הטבלה מתוך ממדי הטבלה באמצעות הוצאת שורש ריבועי:

root_n = int(math.sqrt(4)) # 2

הערך המחושב הוא 2, בהתאם לכך שצריך לחפש בשני תאים בכל תת טבלה.

בשביל לחשב את האינדקס ממנו צריך להתחיל לחפש נחלק בערך השורש root_n, את התוצאה נעגל כלפי מטה floor division ואז נכפול ב-root_n:

root_n = int(math.sqrt(4))
start = math.floor(x/root_n)*root_n

• אפשר לעשות floor division בפייתון על ידי שימוש בשני לוכסנים. פה בחרתי להיות יותר מפורש.

נבדוק שעובד:

x = 0
start = math.floor(x/root_n)*root_n # 0


x = 1
start = math.floor(x/root_n)*root_n # 0


x = 2
start = math.floor(x/root_n)*root_n # 1


x = 3
start = math.floor(x/root_n)*root_n # 1

• יופי! התרגיל למציאת האינדקס של תת הטבלה ממנו צריך להתחיל את החיפוש עובד.

בשביל למצוא את האינדקס בו יש לסיים את החיפוש נוסיף 2 לאינדקס ממנו מתחילים את החיפוש (במקרה של תת טבלה של 2X2). שזה אומר להוסיף את השורש root_n בשביל המקרה הכללי:

root_n = int(math.sqrt(4))
start = math.floor(x/root_n)*root_n
end = start+root_n

ניישם את ההבנה הזו עבור כל תת טבלה באמצעות לולאה מקוננת. לולאה חיצונית שתרוץ על טווח האינדקסים של העמודות (ציר y), ולולאה פנימית שתרוץ על טווח האינדקסים של השורות (ציר x):

# Validate that `number` is not in the same subgrid 
root_n = int(math.sqrt(4))
y_start = y//root_n*root_n
y_end = y_start+root_n
x_start = x//root_n*root_n
x_end = x_start+root_n
for ny in range(y_start, y_end):
    for nx in range(x_start, x_end):
        if grid[ny][nx] == number:
            return False

אם 3 הבדיקות לעיל לא מצאו מספר זהה ל-number אז הפונקציה is_valid() צריכה להחזיר True כיוון שאפשר להציב את המספר.

קלאס של פייתון לפתרון סודוקו

תיכף נכתוב את הפונקציה במלואה אבל בשלב זה נראה לי יותר נכון להשתמש בקלאס שכאשר ניצור ממנו אובייקט נעביר לו שני פרמטרים:

• N - ממדי הטבלה. זה יכול להיות 4 כמו בדוגמה שלנו, 9 שזה סודוקו סטנדרטי 16 וכיו"ב
• grid היא טבלת הסודוקו

אם הנושא של תכנות מונחה עצמים לא ברור אז מומלץ לקרוא את המדריך "פייתון מונחה עצמים 1: מחלקות, אובייקטים, תכונות ומתודות".

לקלאס נקרא SudokuSolver, ונצייד אותו במתודה __init__ שתקבל את הארגומנטים N ו-grid:

class SudokuSolver:
    def __init__(self, grid, N):
          """
          Initialize the SudokuSolver with a grid and its dimension N.

          Args:
              grid: A 2D list representing the Sudoku grid.
              N: The dimension of the grid (e.g., 9 for a standard 9x9 Sudoku).
          """
          self.grid = grid
          self.N = N

נוסיף לקלאס SudokuSolver את המתודה is_valid() לווידוא מספר לפני שמציבים ב-grid:

import math

class SudokuSolver:
    def __init__(self, grid, N):
        """
        Initialize the SudokuSolver with a grid and its dimension N.

        Args:
            grid: A 2D list representing the Sudoku grid.
            N: The dimension of the grid (e.g., 9 for a standard 9x9 Sudoku).
        """
        self.grid = grid
        self.N = N

    def is_valid(self, number, x, y):
        """
        Check if it's valid to place a number in the given cell (x, y).

        Args:
            number: The number to be placed.
            x: The x-coordinate of the cell.
            y: The y-coordinate of the cell.

        Returns:
            True if the placement is valid, False otherwise.
        """
        # Validate that `number` is not in the same column
        for n in range(0, self.N):
            if self.grid[n][x] == number:
                return False

        # Validate that `number` is not in the same row
        for n in range(0, self.N):
            if self.grid[y][n] == number:
                return False
            
        # Validate that `number` is not in the same subgrid 
        root_n = int(math.sqrt(self.N))
        y_start = y // root_n * root_n
        y_end = y_start + root_n
        x_start = x // root_n * root_n
        x_end = x_start + root_n
        for ny in range(y_start, y_end):
            for nx in range(x_start, x_end):
                if self.grid[ny][nx] == number:
                    return False

        return True

נבדוק שהקלאס שלנו והמתודה לבחינה של המספר התורן אכן עובדים:

• ננסה להציב 2 בתא שהקואורדינטות שלו (1,0)
• ננסה להציב 1 באותו תא

# Simplified 4X4 grid
grid = [[4, 0, 1, 0],
[0, 0, 0, 4],
[3, 0, 4, 2],
[2, 4, 0, 1]]


solver = SudokuSolver(grid, len(grid))

print(solver.is_valid(2, 1, 0)) # True

print(solver.is_valid(1, 1, 0)) # False

• הפונקציה המוודאת עובדת כמצופה. רצוי לבדוק ביותר מצבים. אני מקצר כדי להתרכז בעיקר.

יישום אלגוריתם backtracking גישוש נסוג לפתרון סודוקו

סוף סוף אנחנו מגיעים לעניין המרכזי שהוא שימוש באלגוריתם backtracking "גישוש נסוג" בשביל לפתור סודוקו.

הרעיון של backtracking "גישוש נסוג" הוא לנסות אפשרות מסוימת, ואם בהמשך מגלים שהיא לא עובדת, לחזור למצב הקודם לפני שעשינו את הניסוי, וממצב זה לנסות אפשרות אחרת עד שמוצאים אפשרות שעובדת או עד שמנסים את כל האפשרויות. במקרה שלנו, הקוד ינסה להציב, אם אפשר, מספר בתא ריק של טבלת הסודוקו. אם המספר ניתן להצבה, כי אין קונפליקטים עם ספרות זהות באותה שורה, עמודה או תת טבלה, האלגוריתם קורא לעצמו באופן רקורסיבי כדי למצוא פתרונות החל מהתא הריק הבא. אם מסתבר שהמספר שהוצב מביא למצב בלתי אפשרי לפתרון בהמשך, הקוד יחזור לאחור backtrack וינסה להציב מספר אחר בתא.

נוסיף מתודה לקלאס SudokuSolver ששמה יהיה solve() שתחזיר ערך בוליאני. True אם אפשר לפתור את ה-grid, אחרת False:

def solve(self):
    """
    Solve the Sudoku puzzle using backtracking.

    Returns:
        True if a solution is found, False if there is no solution.
    """
    pass

אנחנו רוצים לעבור בצורה סיסטמטית על כל התאים ב-grid כדי לאתר תא ריק שערכו 0. את זה נעשה בתוך לולאה מקוננת:

# Find candidates
for y in range(self.N):
    for x in range(self.N):
        if self.grid[y][x] == 0:
            pass

בתוך התא הריק ננסה להציב באופן סיסטמטי את כל המספרים 1-9, בתנאי שאפשר כי הם עוברים את הבדיקה של הפונקציה is_valid():

# Find candidates
for y in range(self.N):
    for x in range(self.N):
        if self.grid[y][x] == 0:
            # Check validity for each number between 1 and 9
            for number in range(1, self.N + 1):
                if self.is_valid(number, x, y):
                    pass

אם מספר עובר את הבדיקה של הפונקציה is_valid() נציב אותו ב-grid:

def solve(self):
    # Find candidates
    for y in range(self.N):
        for x in range(self.N):
            if self.grid[y][x] == 0:
                # Check validity for each number between 1 and 9
                for number in range(1, self.N + 1):
                    if self.is_valid(number, x, y):
                            
                        # Try to assign the number to the grid
                        self.grid[y][x] = number

את ה-grid עם המספר שהצבנו נעביר למתודה solve(), באופן רקורסיבי, לצורך המשך פתרון:

def solve(self):
    # Find candidates
    for y in range(self.N):
        for x in range(self.N):
            if self.grid[y][x] == 0:
                # Check validity for each number between 1 and 9
                for number in range(1, self.N + 1):
                    if self.is_valid(number, x, y):
                            
                        # Try to assign the number to the grid
                        self.grid[y][x] = number

                        # Recursive call
                        SudokuSolver(self.grid, self.N).solve()

אם המתודה solve, לה קראנו ברקורסיה, תחזיר True כי הצבת המספר בתא מאפשרת פתרון, המתודה הקוראת תחזיר גם היא True אחרת נחזיר את המצב הקודם backtrack ע"י הצבת 0 בתא, ומכיוון שהמספר שניסינו לא עובד נעבור למספרים האפשריים הבאים לצורך מציאת פתרון:

def solve(self):
    # Find candidates
    for y in range(self.N):
        for x in range(self.N):
            if self.grid[y][x] == 0:
                # Check validity for each number between 1 and 9
                for number in range(1, self.N + 1):
                    if self.is_valid(number, x, y):
                            
                        # Try to assign the number to the grid
                        self.grid[y][x] = number

                        # Recursive call
                        SudokuSolver(self.grid, self.N).solve()

                        # If the recursive call does not lead to a solution, backtrack
                        self.grid[y][x] = 0

אם ניסינו את כל המספרים ואף אחד מהם לא התחבר ל-grid שניתן לפתור, לא ניתן לפתור את הפאזל, ולפיכך צריך לקטוע את התהליך על ידי החזרת False:

def solve(self):
        # Find candidates
        for y in range(self.N):
            for x in range(self.N):
                if self.grid[y][x] == 0:
                    # Check validity for each number between 1 and 9
                    for number in range(1, self.N + 1):
                        if self.is_valid(number, x, y):
                            
                            # Try to assign the number to the grid
                            self.grid[y][x] = number
                            
                            # Recursive call
                            if SudokuSolver(self.grid, self.N).solve():
                                # If the recursive call finds a solution, return True
                                return True

                            # If the recursive call does not lead to a solution, backtrack
                            self.grid[y][x] = 0

                    # If no valid number can be placed, return False to backtrack further
                    return False

לבסוף, אם עברנו על כל התאים והצלחנו להציב בכולם מספרים, נחזיר True כיוון שהצלחנו לפתור:

def solve(self):
        """
        Solve the Sudoku puzzle using backtracking.

        Returns:
            True if a solution is found, False if there is no solution.
        """
        # Find candidates
        for y in range(self.N):
            for x in range(self.N):
                if self.grid[y][x] == 0:
                    # Check validity for each number between 1 and 9
                    for number in range(1, self.N + 1):
                        if self.is_valid(number, x, y):
                            
                            # Try to assign the number to the grid
                            self.grid[y][x] = number
                            
                            # Recursive call
                            if SudokuSolver(self.grid, self.N).solve():
                                # If the recursive call finds a solution, return True
                                return True

                            # If the recursive call does not lead to a solution, backtrack
                            self.grid[y][x] = 0

                    # If no valid number can be placed, return False to backtrack further
                    return False

        # If all cells are filled, a solution is found
        return True

להלן הקלאס SudokuSolver המלא לפתרון פאזל סודוקו תוך הסתמכות על אלגוריתם backtracking:

import math
import numpy as np

class SudokuSolver:
    def __init__(self, grid, N):
        """
        Initialize the SudokuSolver with a grid and its dimension N.

        Args:
            grid: A 2D list representing the Sudoku grid.
            N: The dimension of the grid (e.g., 9 for a standard 9x9 Sudoku).
        """
        self.grid = grid
        self.N = N

    def is_valid(self, number, x, y):
        """
        Check if it's valid to place a number in the given cell (x, y).

        Args:
            number: The number to be placed.
            x: The x-coordinate of the cell.
            y: The y-coordinate of the cell.

        Returns:
            True if the placement is valid, False otherwise.
        """
        # Validate that `number` is not in the same column
        for n in range(0, self.N):
            if self.grid[n][x] == number:
                return False

        # Validate that `number` is not in the same row
        for n in range(0, self.N):
            if self.grid[y][n] == number:
                return False
            
        # Validate that `number` is not in the same subgrid 
        root_n = int(math.sqrt(self.N))
        y_start = y // root_n * root_n
        y_end = y_start + root_n
        x_start = x // root_n * root_n
        x_end = x_start + root_n
        for ny in range(y_start, y_end):
            for nx in range(x_start, x_end):
                if self.grid[ny][nx] == number:
                    return False

        return True

    def solve(self):
        """
        Solve the Sudoku puzzle using backtracking.

        Returns:
            True if a solution is found, False if there is no solution.
        """
        # Find candidates
        for y in range(self.N):
            for x in range(self.N):
                if self.grid[y][x] == 0:
                    # Check validity for each number between 1 and 9
                    for number in range(1, self.N + 1):
                        if self.is_valid(number, x, y):
                            
                            # Try to assign the number to the grid
                            self.grid[y][x] = number
                            
                            # Recursive call
                            if SudokuSolver(self.grid, self.N).solve():
                                # If the recursive call finds a solution, return True
                                return True

                            # If the recursive call does not lead to a solution, backtrack
                            self.grid[y][x] = 0

                    # If no valid number can be placed, return False to backtrack further
                    return False

        # If all cells are filled, a solution is found
        return True

ננסה את הקלאס עבור גרסה פשוטה של 4X4:

# Test cases
# Simplified 4X4 grid
grid = [[4, 0, 1, 0],
        [0, 0, 0, 4],
        [3, 0, 4, 2],
        [2, 4, 0, 1]]


solver = SudokuSolver(grid, len(grid))
res = solver.solve()
if not res:
    print("No solution found.")
else:
    print(np.matrix(solver.grid))

התוצאה:

[[4 2 1 3]
 [1 3 2 4]
 [3 1 4 2]
 [2 4 3 1]]

• בשביל להדפיס את grid התוצאה השתמשתי במתודה matrix() של חבילת numpy.

ננסה פאזל שאי אפשר לפתור:

# Unsolvable grid
grid = [[4, 0, 1, 0],
        [0, 0, 0, 4],
        [3, 3, 4, 2],
        [2, 4, 0, 1]]

התוצאה:

No solution found.

ננסה עבור רמות קושי שונות של סודוקו סטנדרטי 9X9:

# Test cases

# Easy
grid0 = [[5, 8, 2, 4, 0, 1, 0, 9, 0],
        [6, 9, 0, 5, 8, 0, 7, 0, 4],
        [0, 0, 4, 0, 9, 3, 8, 2, 5],
        [0, 3, 6, 8, 2, 5, 1, 0, 0],
        [0, 2, 0, 0, 1, 4, 9, 3, 6],
        [1, 0, 7, 0, 3, 0, 2, 5, 8],
        [2, 0, 8, 0, 0, 7, 3, 6, 9],
        [0, 7, 1, 3, 6, 9, 0, 8, 0],
        [3, 6, 9, 0, 0, 8, 0, 7, 1]]

# Medium
grid1 = [[0, 0, 0, 3, 1, 4, 0, 0, 0],
        [0, 0, 0, 0, 2, 0, 0, 6, 0],
        [0, 1, 3, 0, 5, 0, 0, 2, 0],
        [0, 9, 1, 0, 0, 0, 2, 0, 6],
        [0, 0, 7, 0, 0, 0, 5, 0, 0],
        [3, 0, 5, 0, 0, 0, 7, 1, 0],
        [0, 6, 0, 0, 8, 0, 9, 7, 0],
        [0, 5, 0, 0, 3, 0, 0, 0, 0],
        [0, 0, 0, 7, 4, 2, 0, 0, 0]]

# Hard
grid2 = [[6, 0, 5, 0, 3, 9, 0, 0, 2],
        [9, 1, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 8, 0, 4, 0, 0, 0, 6],
        [0, 0, 0, 0, 1, 0, 7, 0, 3],
        [1, 0, 2, 0, 9, 3, 6, 0, 5],
        [0, 0, 0, 0, 5, 0, 2, 0, 8],
        [0, 0, 1, 0, 2, 0, 0, 0, 7],
        [2, 6, 0, 0, 0, 0, 0, 0, 0],
        [8, 0, 4, 0, 6, 1, 0, 0, 9]]

# Very hard
grid3 = [[0, 0, 0, 0, 0, 0, 6, 9, 0],
        [5, 0, 0, 6, 9, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 4, 8, 0, 5],
        [7, 0, 0, 0, 0, 5, 9, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 4, 0],
        [0, 0, 3, 0, 4, 0, 2, 0, 0],
        [1, 0, 4, 0, 0, 0, 0, 6, 0],
        [0, 8, 5, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 7, 0, 0, 8, 2]]

grids = [grid0, grid1, grid2, grid3]

for grid in grids:
    solver = SudokuSolver(grid, len(grid))
    res = solver.solve()
    if not res:
        print("No solution found.")
    else:
        print(np.matrix(solver.grid))

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

שימוש באלגוריתם backtracking גישוש נסוג לפתרון האתגר של N מלכות

רקורסיה בפייתון - כל מה שרצית לדעת ועוד כמה דברים חשובים

תכנות דינמי מלמטה למעלה ובחזרה - מדריך לתכנות דינאמי שמתחיל מהבסיס

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים