סודוקו פותר


רמת קושי קשה
נשאל לעתים קרובות אמזון בעברית תפוח עץ דלתא Google אינטואיט JP מורגן מיקרוסופט אורקל
חזרה לאחור בליל חבטות

בבעיית פותר הסודוקו נתנו סודוקו מלא (9 x 9) חלקי, כתוב תוכנית להשלמת הפאזל.

על סודוקו לספק את המאפיינים הבאים,

  1. כל מספר (1-9) חייב להופיע בדיוק פעם אחת בשורה ופעם בעמודה.
  2. כל מספר (1-9) חייב להופיע פעם אחת בדיוק בתיבת משנה (3 x 3) של הרשת.

0 מייצג תא ריק.

דוגמה

קלט:

סודוקו פותר

פלט:

אַלגוֹרִיתְם

הבסיס אַלגוֹרִיתְם לפתור את חידון הסודוקו (סודוקו פותר) זה לנסות את כל צירופי המספרים ולבחור את הפתרון העונה לתנאים הנ"ל.

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

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

  1. מצא תא ריק, אם אין תא ריק, הפאזל נפתר ואנחנו חוזרים.
  2. תנו לשורה ולעמודה של התא הריק להיות i ו- j בהתאמה.
  3. הקצה מספרים אחד אחד לתא הריק, אם זה בטוח להקצות מספר, חזור על רקע הצעדים לעיל באופן רקורסיבי.
  4. אם מטלה זו מובילה לפיתרון, השב נכון.
  5. אחרת נסה את המספר הבא עבור התא הריק הנוכחי.

לבדוק אם המטלה בטוחה או לא,
כדי שמספר יהיה תקף בתא, עליו לעקוב אחר המאפיינים הבסיסיים של חידת הסודוקו (שתוארו לעיל).

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

קוד פסאודו לפותר סודוקו

// פונקציה לפתרון חידון הסודוקו
לפתור (סודוקו)

// Find an empty cell
int i = 0, j = 0
for (int i = 0; i < 9; i++) {
  for (int j = 0; j < 9; j++) {
    if (sudoku[i][j] == 0)
      break
  }
}
// No empty cell found
if (i == 9 && j == 9)
  return true
// Try all the numbers one by one
for (int n = 1; n <= 9; n++) {
  // If the assignment is valid
  if (isSafe(sudoku, i, j, n)) {
    // Assign the value to this cell
    sudoku[i][j] = n
    // If recursion leads to a solution, return true
    if (solve(sudoku))
      return true
    // Back tracking
    sudoku[i][j] = 0
  }
}

// פונקציה לבדיקת תוקף מספר בתא נתון
isSafe (סודוקו, i, j, n)

// Check in current row and column
for (int x = 0; x < 9; x++)
  if (sudoku[i][x] == n || sudoku[x][j] == n)
    return false
// Calculate starting index of row and column of 3 x 3 sub box
int rs = i - (i % 3)
int cs = j - (j % 3)
// Check in 3 x 3 sub box
for (int x = 0; x < 3; x++) 
  for (int y = 0; y < 3; y++)
    if (sudoku[x + rs][y + cs] == n)
      return false
return true

קוד JAVA

public class SudokoSolver {
    public static boolean solve(int[][] sudoku) {
        int i = 0, j = 0;
        boolean found = false;
        // Find an empty cell
        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {
                if (sudoku[i][j] == 0) {
                    found = true;
                    break;
                }
            }
            if (found) {
                break;
            }
        }

        // No empty cell found, return true
        if (i == 9 && j == 9) {
            return true;
        }

        // One by one try all the values in the current cell
        for (int n = 1; n <= 9; n++) {
            // check if it is valid to assign value n to current cell
            if (isSafe(i, j, n, sudoku)) {
                sudoku[i][j] = n;
                // Recursively solve the sudoku
                if (solve(sudoku)) {
                    return true;
                }
                // back track if the recursion returns false
                sudoku[i][j] = 0;
            }
        }
        
        // Return false if no value fits
        return false;
    }

    public static boolean isSafe(int i, int j, int n, int[][] sudoku) {
        // Check in current row and column
        for (int x = 0; x < 9; x++) {
            // Row
            if (sudoku[i][x] == n) {
                return false;
            }
            // Column
            if (sudoku[x][j] == n) {
                return false;
            }
        }
        
        // Calculate the starting index of row and column of current 3x3 sub box
        int rs = i - (i % 3);
        int cs = j - (j % 3);

        // Check in the current sub box
        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++) {
                if (sudoku[x + rs][y + cs] == n) {
                    return false;
                }
            }
        }

        // Return true
        return true;
    }

    public static void main(String[] args) {
        // Partially filled sudoku puzzle
        int[][] sudoko = new int[][] {
                {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}
        };

        solve(sudoko);

        // Print the answer
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(sudoko[i][j] + " ");
            }
            System.out.println();
        }
    }
}

קוד C ++ לפותר סודוקו

#include <bits/stdc++.h>
using namespace std;

bool isSafe(vector<vector<int>> &sudoku, int i, int j, int n) {
    // Check in current row and column
    for (int x = 0; x < 9; x++) {
        // Row
        if (sudoku[i][x] == n) {
            return false;
        }
        // Column
        if (sudoku[x][j] == n) {
            return false;
        }
    }
    
    // Calculate the starting index of row and column of current 3x3 sub box
    int rs = i - (i % 3);
    int cs = j - (j % 3);

    // Check in the current sub box
    for (int x = 0; x < 3; x++) {
        for (int y = 0; y < 3; y++) {
            if (sudoku[x + rs][y + cs] == n) {
                return false;
            }
        }
    }

    // Return true
    return true;
}

bool solve(vector<vector<int>> &sudoku) {
    int i = 0, j = 0;
    bool found = false;
    // Find an empty cell
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            if (sudoku[i][j] == 0) {
                found = true;
                break;
            }
        }
        if (found)
            break;
    }
    
    // No empty cell found, return true
    if (i == 9 && j == 9) {
        return true;
    }
    
    // One by one try all the values in the current cell
    for (int n = 1; n <= 9; n++) {
        // check if it is valid to assign value n to current cell
        if (isSafe(sudoku, i, j, n)) {
            sudoku[i][j] = n;
            // Recursively solve the sudoku
            if (solve(sudoku) == true)
                return true;
            // back track if the recursion returns false
            sudoku[i][j] = 0;
        }
    }
    
    // Return false if no value fits
    return false;
}

int main() {
    // Partially filled sudoku puzzle
    vector<vector<int>> sudoku =  {
                {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}
    };
        
    solve(sudoku);

    // Print the answer
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout<<sudoku[i][j]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}
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 

ניתוח מורכבות לפותר סודוקו

מורכבות זמן

O (9 ^ (n * n)): לכל אינדקס שלא הוקצה יש 9 אפשרויות אפשריות ולכן מורכבות הזמן הגרועה ביותר של פותר סודוקו היא O (9 ^ (n * n)).

מורכבות בחלל

 O (n * n): כדי לאחסן את מערך הפלט יש צורך במטריצה.

הפניות