Sudoku həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon alma Qapılar google Intuit JP Morgan microsoft Kahin
Geri qayıtma Sükut HashingBaxılıb 134

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Sudoku həll edici məsələdə qismən doldurulmuş (9 x 9) sudoku verdik, tapmacanı tamamlamaq üçün bir proqram yazın.

Sudoku aşağıdakı xüsusiyyətləri təmin etməlidir,

  1. Hər bir rəqəm (1-9) ardıcıl olaraq bir dəfə və sütunda bir dəfə görünməlidir.
  2. Hər bir rəqəm (1-9), ızgaranın (3 x 3) alt qutusunda tam bir dəfə görünməlidir.

0 boş bir hüceyrəni təmsil edir.

misal

Input:

Sudoku həlliPin

Çıxış:

Pin

Alqoritm

Əsasdır alqoritm sudoku tapmacasını (sudoku həll edən) həll etmək, rəqəmlərin bütün birləşmələrini sınamaq və yuxarıdakı şərtlərə cavab verən həll yolu seçməkdir.

Bu prosesin zaman mürəkkəbliyi çox yüksəkdir, buna görə də mövcud yolun bir həll yolu tapmayacağını tapan kimi rekursiyanı azaltmaq üçün geri çəkilmədən istifadə edirik.

Bu, tapmacanı həll etmək üçün çəkilən vaxtı azaltmağa meyllidir, lakin zamanın mürəkkəbliyinə dair yuxarı sərhəd eyni qalır.

  1. Boş bir hüceyrə tapın, boş bir hüceyrə yoxdursa, tapmaca həll olundu və geri qayıtdıq.
  2. Boş xananın sətri və sütunu müvafiq olaraq i və j olsun.
  3. Boş hüceyrəyə nömrələri bir-bir təyin edin, əgər nömrə təyin etmək təhlükəsizdirsə, yuxarıdakı addımları təkrarən təkrarlayın.
  4. Bu tapşırıq bir həll yolunu taparsa, doğru qayıdın.
  5. Başqa birində cari boş xana üçün növbəti nömrəni sınayın.

Tapşırığın təhlükəsiz olub-olmadığını yoxlamaq,
Ədədin bir hüceyrədə etibarlı olması üçün sudoku tapmacasının əsas xüsusiyyətlərinə əməl etməlidir (yuxarıda təsvir edilmişdir).

  1. Təyin edilmiş nömrə cari sətirdə və ya cari sütunda varsa, false olaraq qaytarın.
  2. Boş xananın olduğu 3 × 3 alt qutusunun sətir və sütunun başlanğıc indeksini hesablayın.
  3. Təyin edilmiş nömrə cari 3 × 3 alt qutusundadırsa, false olaraq qayıdın.
  4. Doğru qayıdın.

Sudoku Solver üçün Pseudo Code

// Sudoku tapmacasını həll etmək funksiyası
həll etmək (sudoku)

// 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
  }
}

// Verilən xanadakı bir ədədin etibarlılığını yoxlamaq funksiyası
isSafe (sudoku, 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 Kodu

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

Sudoku Solver üçün C ++ kodu

#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 

Sudoku Solver üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (9 ^ (n * n)): Hər təyin olunmamış indeks üçün 9 mümkün seçim mövcuddur, buna görə sudoku həll edicinin ən pis zaman mürəkkəbliyi O (9 ^ (n * n)).

Kosmik Mürəkkəblik

 O (n * n): Çıxış massivini saxlamaq üçün bir matris lazımdır.

References

Crack Sistemi Dizayn Müsahibələri
Translate »