스도쿠 솔버 문제에서 우리는 부분적으로 채워진 (9 x 9) 스도쿠를 제공했습니다. 퍼즐을 완성하는 프로그램을 작성하십시오.
스도쿠는 다음 속성을 충족해야합니다.
- 모든 숫자 (1-9)는 행에 한 번, 열에 한 번만 표시되어야합니다.
- 모든 숫자 (1-9)는 그리드의 (3 x 3) 하위 상자에 정확히 한 번 나타나야합니다.
0은 빈 셀을 나타냅니다.
차례
예
입력:
출력:
암호알고리즘
기본 연산 스도쿠 퍼즐 (sudoku solver)을 풀기 위해서는 모든 숫자의 조합을 시도하고 위의 조건을 만족하는 솔루션을 선택합니다.
이 프로세스의 시간 복잡성은 매우 높기 때문에 현재 경로가 솔루션으로 이어지지 않는다는 것을 발견하자마자 역 추적을 사용하여 재귀를 줄입니다.
이것은 퍼즐을 푸는 데 걸리는 시간을 줄이는 경향이 있지만 시간 복잡성의 전체 상한은 동일하게 유지됩니다.
- 빈 셀을 찾으십시오. 빈 셀이 없으면 퍼즐이 풀리고 반환됩니다.
- 빈 셀의 행과 열을 각각 i와 j로 둡니다.
- 빈 셀에 하나씩 숫자를 할당하십시오. 숫자를 할당하는 것이 안전하다면 위의 단계를 반복적으로 반복하십시오.
- 이 할당이 솔루션으로 연결되면 true를 반환합니다.
- 그렇지 않으면 현재 빈 셀에 대해 다음 번호를 시도하십시오.
과제가 안전한지 확인하고,
셀에서 숫자가 유효하려면 위에서 설명한 스도쿠 퍼즐의 기본 속성을 따라야합니다.
- 할당 된 번호가 현재 행 또는 현재 열에 있으면 false를 반환합니다.
- 빈 셀이있는 3x3 서브 박스의 행과 열의 시작 인덱스를 계산합니다.
- 현재 3x3 서브 박스에 할당 된 번호가 있으면 false를 반환합니다.
- 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) : 출력 배열을 저장하려면 행렬이 필요합니다.
