이 섹션에서는 스도쿠라는 유명한 숫자 미로 문제를 해결하려고 합니다. 스도쿠는 9 x 9 숫자 그리드이며 전체 그리드도 3 x 3 상자로 나뉩니다. 스도쿠를 푸는 몇 가지 규칙이 있습니다.
이 문제를 해결하려면 1에서 9까지의 숫자를 사용해야 합니다.
하나의 행, 하나의 열 또는 하나의 3 x 3 상자에서 하나의 숫자를 반복할 수 없습니다.
역추적 알고리즘을 사용하여 스도쿠 문제를 해결하려고 합니다. 일부 셀이 숫자로 채워지면 유효한지 여부를 확인합니다. 유효하지 않은 경우 다른 번호를 확인합니다. 1-9 사이의 모든 숫자를 확인하고 유효한 숫자를 찾지 못하면 이전 옵션으로 되돌아갑니다.
입력 및 출력
Input: This will take a 9 x 9 matrix as Sudoku grid. Some values are placed in the grid. The blank spaces are denoted by 0. Output: The final matrix (Sudoku grid) filled with numbers. If the solution does not exist, it will return false. 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
알고리즘
isPresentInCol(열, 숫자)
입력: 열 및 대상 번호입니다.
출력 - 주어진 열에 숫자가 있으면 참입니다.
Begin for each row r in the grid, do if grid[r, col] = num, then return true done return false otherwise End
isPresentInRow(행, 숫자)
입력 - 행 및 대상 번호입니다.
출력 - 주어진 열에 숫자가 있으면 참입니다.
Begin for each column c in the grid, do if grid[row, c] = num, then return true done return false otherwise End
isPresentInBox(boxStartRow, boxStartCol, num)
입력 - 3 x 3 상자의 시작 행과 열, 그리고 대상 번호입니다.
출력 - 숫자가 상자에 있으면 참입니다.
Begin for each row r in boxStartRow to next 3 rows, do for each col r in boxStartCol to next 3 columns, do if grid[r, c] = num, then return true done done return false otherwise End
findEmptyPlace(행, 열)
입력: 그리드의 행과 열.
출력 - grid[row, col]가 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
Begin for each row r in the grid, do for each column c in the grid, do if grid[r, c] = 0, then return true done done return false End
isValidPlace(행, 열, 숫자)
입력: 그리드의 행, 열, 확인할 숫자입니다.
출력: 참, 그리드[row, col] 위치에 숫자를 배치할 때 유효합니다.
Begin if isPresentInRow(row, num) and isPresentInCol(col, num) and isPresntInBox(row – row mod 3, col – col mod 3, num) all are false, then return true End
solveSudoku(스도쿠 그리드)
입력: 스도쿠의 미해결 그리드.
출력: 해결 후 그리드.
Begin if no place in the grid is empty, then return true for number 1 to 9, do if isValidPlace(row, col, number), then grid[row, col] := number if solveSudoku = true, then return true grid[row, col] := 0 done return false End
예시
#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) && !isPresentInBox(row - row%3 , col - col%3, num); } bool solveSudoku() { int row, col; if (!findEmptyPlace(row, col)) return true; //when all places are filled for (int num = 1; num <= 9; num++) { //valid numbers are 1 - 9 if (isValidPlace(row, col, num)) { //check validation, if yes, put the number in the grid grid[row][col] = num; if (solveSudoku()) //recursively go for other rooms in the grid return true; grid[row][col] = 0; //turn to unassigned space when conditions are not satisfied } } return false; } int main() { if (solveSudoku() == true) sudokuGrid(); else cout << "No solution exists"; }
출력
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