스도쿠 해결사

난이도 하드
자주 묻는 질문 아마존 Apple 문틀 구글 인튜이트 JP 모건 Microsoft 신탁
역 추적 해시 해싱조회수 73

스도쿠 솔버 문제에서 우리는 부분적으로 채워진 (9 x 9) 스도쿠를 제공했습니다. 퍼즐을 완성하는 프로그램을 작성하십시오.

스도쿠는 다음 속성을 충족해야합니다.

  1. 모든 숫자 (1-9)는 행에 한 번, 열에 한 번만 표시되어야합니다.
  2. 모든 숫자 (1-9)는 그리드의 (3 x 3) 하위 상자에 정확히 한 번 나타나야합니다.

0은 빈 셀을 나타냅니다.

입력:

스도쿠 해결사

출력:

암호알고리즘

기본 연산 스도쿠 퍼즐 (sudoku solver)을 풀기 위해서는 모든 숫자의 조합을 시도하고 위의 조건을 만족하는 솔루션을 선택합니다.

이 프로세스의 시간 복잡성은 매우 높기 때문에 현재 경로가 솔루션으로 이어지지 않는다는 것을 발견하자마자 역 추적을 사용하여 재귀를 줄입니다.

이것은 퍼즐을 푸는 데 걸리는 시간을 줄이는 경향이 있지만 시간 복잡성의 전체 상한은 동일하게 유지됩니다.

  1. 빈 셀을 찾으십시오. 빈 셀이 없으면 퍼즐이 풀리고 반환됩니다.
  2. 빈 셀의 행과 열을 각각 i와 j로 둡니다.
  3. 빈 셀에 하나씩 숫자를 할당하십시오. 숫자를 할당하는 것이 안전하다면 위의 단계를 반복적으로 반복하십시오.
  4. 이 할당이 솔루션으로 연결되면 true를 반환합니다.
  5. 그렇지 않으면 현재 빈 셀에 대해 다음 번호를 시도하십시오.

과제가 안전한지 확인하고,
셀에서 숫자가 유효하려면 위에서 설명한 스도쿠 퍼즐의 기본 속성을 따라야합니다.

  1. 할당 된 번호가 현재 행 또는 현재 열에 있으면 false를 반환합니다.
  2. 빈 셀이있는 3x3 서브 박스의 행과 열의 시작 인덱스를 계산합니다.
  3. 현재 3x3 서브 박스에 할당 된 번호가 있으면 false를 반환합니다.
  4. true를 반환합니다.

스도쿠 솔버에 대한 의사 코드

// 스도쿠 퍼즐을 푸는 기능
해결 (스도쿠)

// 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 (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 코드

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) : 출력 배열을 저장하려면 행렬이 필요합니다.

참조

Translate »