부분적으로 채워진 스도쿠 그리드가 있고 이것을 해결해야 한다고 가정합니다. 우리는 스도쿠가 9 × 9 숫자 그리드라는 것을 알고 있으며 전체 그리드도 3 × 3 상자로 나뉩니다. 스도쿠를 푸는 몇 가지 규칙이 있습니다.
-
이 문제를 해결하려면 1에서 9까지의 숫자를 사용해야 합니다.
-
하나의 행, 하나의 열 또는 하나의 3 × 3 상자에서 하나의 숫자를 반복할 수 없습니다.
역추적 알고리즘을 사용하여 스도쿠 문제를 해결하려고 합니다. 일부 셀이 숫자로 채워지면 유효한지 여부를 확인합니다. 유효하지 않은 경우 다른 번호를 확인합니다. 모든 숫자가 1-9부터 확인되고 유효한 숫자가 없으면 이전 옵션으로 되돌아갑니다.
따라서 입력이 다음과 같으면 -
출력은 -
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
isPresentInCol()이라는 메서드를 정의합니다. 이 메서드는 호출과 num
을 받습니다. -
그리드의 각 행 r에 대해
-
grid[r, col] =num이면 true를 반환합니다.
-
-
그렇지 않으면 false를 반환
-
isPresentInRow()라는 메서드를 정의하면 행과 숫자가 필요합니다.
-
그리드의 각 열 c에 대해
-
grid[row, c] =num이면 true를 반환합니다.
-
-
그렇지 않으면 false를 반환
-
isPresentInBox()라는 메서드를 정의하면 boxStartRow, boxStartCol, num
이 사용됩니다. -
boxStartRow의 각 행 r에 대해 다음 3행까지
-
다음 3개의 열에 대한 boxStartCol의 각 열에 대해 수행
-
grid[r, c] =num이면 true를 반환합니다.
-
-
-
그렇지 않으면 false를 반환
-
findEmptyPlace()라는 메서드를 정의하면 행과 열이 필요합니다.
-
그리드의 각 행 r에 대해
-
그리드의 각 열 c에 대해
-
grid[r, c] =0이면 true를 반환합니다.
-
-
-
거짓을 반환
-
isValidPlace()라는 메서드를 정의하면 행, 열, 번호
가 사용됩니다. -
isPresentInRow(row, num) 및 isPresentInCol(col, num) 및 isPresntInBox(row - row mod 3, col - col mod 3, num)가 모두 거짓이면 true를 반환합니다.
-
solveSudoku()라는 메서드를 정의하면 그리드가 필요합니다.
-
그리드에 빈 자리가 없으면 true를 반환합니다.
-
숫자 1에서 9에 대해 수행
-
isValidPlace(행, 열, 숫자)인 경우
-
그리드[행, 열] :=숫자
-
solveSudoku =true이면 true를 반환합니다.
-
그리드[행, 열] :=0
-
-
-
거짓을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <iostream>
#define N 9
using namespace std;
int grid[N][N] = { {3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}};
bool isPresentInCol(int col, int num){
//check whether num is present
in col or not
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
bool isPresentInRow(int row, int num){
//check whether num is present
in row or not
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
bool isPresentInBox(int boxStartRow, int boxStartCol, int num){
//check whether num is present in 3x3 box or not
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
void sudokuGrid(){
//print the sudoku grid after solve
for (int row = 0; row < N; row++){
for (int col = 0; col < N; col++){
if(col == 3 || col == 6)
cout << " | ";
cout << grid[row][col] <<" ";
}
if(row == 2 || row == 5){
cout << endl;
for(int i = 0; i<N; i++)
cout << "---";
}
cout << endl;
}
}
bool findEmptyPlace(int &row, int &col){
//get empty location and
update row and column
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == 0) //marked with 0 is empty
return true;
return false;
}
bool isValidPlace(int row, int col, int num){
//when item not found in col, row and current 3x3 box
return !isPresentInRow(row, num) && !isPresentInCol(col, num) &&
for (int row = 0; row < N; row++){
for (int col = 0; col < N; col++){
if(col == 3 || col == 6)
cout << " | ";
cout << grid[row][col] <<" ";
}
if(row == 2 || row == 5){
cout << endl;
for(int i = 0; i<N; i++)
cout << "−−−";
}
cout << endl;
}
}
bool findEmptyPlace(int &row, int &col){
//get empty location and
update row and column
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == 0) //marked with 0 is empty
return true;
return false;
}
bool isValidPlace(int row, int col, int num){
//when item not found in col, row and current 3x3 box
return !isPresentInRow(row, num) && !isPresentInCol(col, num) &&
cout << "No solution exists";
} 입력
{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0} 출력
3 1 6 | 5 7 8 | 4 9 2 5 2 9 | 1 3 4 | 7 6 8 4 8 7 | 6 2 9 | 5 3 1 --------------------------- 2 6 3 | 4 1 5 | 9 8 7 9 7 4 | 8 6 3 | 1 2 5 8 5 1 | 7 9 2 | 6 4 3 --------------------------- 1 3 8 | 9 4 7 | 2 5 6 6 9 2 | 3 5 1 | 8 7 4 7 4 5 | 2 8 6 | 3 1 9