给定一个部分填充的9×9 2D数组“grid[9][9]”，目标是将数字（从1到9）分配给空单元格，以便大小为3×3的每一行、每一列和每一子网格都恰好包含1到9的数字的一个实例。
null
![图片[1]-数独|回溯-7-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_sudoku.jpg)
例子：
Input:grid = { {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} }Output: 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 9Explanation: Each row, column and 3*3 box of the output matrix contains unique numbers.Input: grid = { { 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, 0, 1, 5, 9, 8, 7 }, { 9, 7, 4, 8, 6, 0, 1, 2, 5 }, { 8, 5, 1, 7, 9, 2, 6, 4, 3 }, { 1, 3, 8, 0, 4, 7, 2, 0, 6 }, { 6, 9, 2, 3, 5, 1, 8, 7, 4 }, { 7, 4, 5, 0, 8, 6, 3, 1, 0 } };Output: 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 Explanation: Each row, column and 3*3 box of the output matrix contains unique numbers.
方法1 : 易于理解的 方法： 最简单的方法是生成从1到9的所有可能的数字配置，以填充空单元格。逐个尝试每个配置，直到找到正确的配置，即对于每个未分配的位置，用1到9的数字填充该位置。填写所有未分配位置后，检查矩阵是否安全。如果安全打印，其他情况下会再次出现。
算法：
- 创建一个函数来检查给定的矩阵是否是有效的数独。保留行、列和框的Hashmap。如果hashMap中任何数字的频率大于1，则返回false，否则返回true；
- 创建一个递归函数，该函数接受一个网格以及当前的行和列索引。
- 检查一些基本情况。如果索引位于矩阵末尾，即i=N-1和j=N，则检查网格是否安全，如果安全，则打印网格并返回true，否则返回false。另一种基本情况是，列的值为N，即j=N，然后移动到下一行，即i++和j=0。
- 如果未指定当前索引，则将元素从1填充到9，并使用下一个元素的索引（即i，j+1）重复出现所有9种情况。如果递归调用返回true，则中断循环并返回true。
- 如果分配了当前索引，则调用带有下一个元素索引的递归函数，即i，j+1
C++
#include <iostream> using namespace std; // N is the size of the 2D matrix N*N #define N 9 /* A utility function to print grid */ void print( int arr[N][N]) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) cout << arr[i][j] << " " ; cout << endl; } } // Checks whether it will be // legal to assign num to the // given row, col bool isSafe( int grid[N][N], int row, int col, int num) { // Check if we find the same num // in the similar row , we // return false for ( int x = 0; x <= 8; x++) if (grid[row][x] == num) return false ; // Check if we find the same num in // the similar column , we // return false for ( int x = 0; x <= 8; x++) if (grid[x][col] == num) return false ; // Check if we find the same num in // the particular 3*3 matrix, // we return false int startRow = row - row % 3, startCol = col - col % 3; for ( int i = 0; i < 3; i++) for ( int j = 0; j < 3; j++) if (grid[i + startRow][j + startCol] == num) return false ; return true ; } /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ bool solveSudoku( int grid[N][N], int row, int col) { // Check if we have reached the 8th // row and 9th column (0 // indexed matrix) , we are // returning true to avoid // further backtracking if (row == N - 1 && col == N) return true ; // Check if column value becomes 9 , // we move to next row and // column start from 0 if (col == N) { row++; col = 0; } // Check if the current position of // the grid already contains // value >0, we iterate for next column if (grid[row][col] > 0) return solveSudoku(grid, row, col + 1); for ( int num = 1; num <= N; num++) { // Check if it is safe to place // the num (1-9) in the // given row ,col ->we // move to next column if (isSafe(grid, row, col, num)) { /* Assigning the num in the current (row,col) position of the grid and assuming our assigned num in the position is correct */ grid[row][col] = num; // Checking for next possibility with next // column if (solveSudoku(grid, row, col + 1)) return true ; } // Removing the assigned num , // since our assumption // was wrong , and we go for // next assumption with // diff num value grid[row][col] = 0; } return false ; } // Driver Code int main() { // 0 means unassigned cells 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 } }; if (solveSudoku(grid, 0, 0)) print(grid); else cout << "no solution exists " << endl; return 0; // This is code is contributed by Pradeep Mondal P } |
C
#include <stdio.h> #include <stdlib.h> // N is the size of the 2D matrix N*N #define N 9 /* A utility function to print grid */ void print( int arr[N][N]) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) printf ( "%d " ,arr[i][j]); printf ( "" ); } } // Checks whether it will be legal // to assign num to the // given row, col int isSafe( int grid[N][N], int row, int col, int num) { // Check if we find the same num // in the similar row , we return 0 for ( int x = 0; x <= 8; x++) if (grid[row][x] == num) return 0; // Check if we find the same num in the // similar column , we return 0 for ( int x = 0; x <= 8; x++) if (grid[x][col] == num) return 0; // Check if we find the same num in the // particular 3*3 matrix, we return 0 int startRow = row - row % 3, startCol = col - col % 3; for ( int i = 0; i < 3; i++) for ( int j = 0; j < 3; j++) if (grid[i + startRow][j + startCol] == num) return 0; return 1; } /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ int solveSudoku( int grid[N][N], int row, int col) { // Check if we have reached the 8th row // and 9th column (0 // indexed matrix) , we are // returning true to avoid // further backtracking if (row == N - 1 && col == N) return 1; // Check if column value becomes 9 , // we move to next row and // column start from 0 if (col == N) { row++; col = 0; } // Check if the current position // of the grid already contains // value >0, we iterate for next column if (grid[row][col] > 0) return solveSudoku(grid, row, col + 1); for ( int num = 1; num <= N; num++) { // Check if it is safe to place // the num (1-9) in the // given row ,col ->we move to next column if (isSafe(grid, row, col, num)==1) { /* assigning the num in the current (row,col) position of the grid and assuming our assigned num in the position is correct */ grid[row][col] = num; // Checking for next possibility with next // column if (solveSudoku(grid, row, col + 1)==1) return 1; } // Removing the assigned num , // since our assumption // was wrong , and we go for next // assumption with // diff num value grid[row][col] = 0; } return 0; } int main() { // 0 means unassigned cells 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 } }; if (solveSudoku(grid, 0, 0)==1) print(grid); else printf ( "No solution exists" ); return 0; // This is code is contributed by Pradeep Mondal P } |
JAVA
// Java program for above approach public class Sudoku { // N is the size of the 2D matrix N*N static int N = 9 ; /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ static boolean solveSudoku( int grid[][], int row, int col) { /*if we have reached the 8th row and 9th column (0 indexed matrix) , we are returning true to avoid further backtracking */ if (row == N - 1 && col == N) return true ; // Check if column value becomes 9 , // we move to next row // and column start from 0 if (col == N) { row++; col = 0 ; } // Check if the current position // of the grid already // contains value >0, we iterate // for next column if (grid[row][col] != 0 ) return solveSudoku(grid, row, col + 1 ); for ( int num = 1 ; num < 10 ; num++) { // Check if it is safe to place // the num (1-9) in the // given row ,col ->we move to next column if (isSafe(grid, row, col, num)) { /* assigning the num in the current (row,col) position of the grid and assuming our assigned num in the position is correct */ grid[row][col] = num; // Checking for next // possibility with next column if (solveSudoku(grid, row, col + 1 )) return true ; } /* removing the assigned num , since our assumption was wrong , and we go for next assumption with diff num value */ grid[row][col] = 0 ; } return false ; } /* A utility function to print grid */ static void print( int [][] grid) { for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) System.out.print(grid[i][j] + " " ); System.out.println(); } } // Check whether it will be legal // to assign num to the // given row, col static boolean isSafe( int [][] grid, int row, int col, int num) { // Check if we find the same num // in the similar row , we // return false for ( int x = 0 ; x <= 8 ; x++) if (grid[row][x] == num) return false ; // Check if we find the same num // in the similar column , // we return false for ( int x = 0 ; x <= 8 ; x++) if (grid[x][col] == num) return false ; // Check if we find the same num // in the particular 3*3 // matrix, we return false int startRow = row - row % 3 , startCol = col - col % 3 ; for ( int i = 0 ; i < 3 ; i++) for ( int j = 0 ; j < 3 ; j++) if (grid[i + startRow][j + startCol] == num) return false ; return true ; } // Driver Code public static void main(String[] args) { int grid[][] = { { 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 } }; if (solveSudoku(grid, 0 , 0 )) print(grid); else System.out.println( "No Solution exists" ); } // This is code is contributed by Pradeep Mondal P } |
Python3
# N is the size of the 2D matrix N*N N = 9 # A utility function to print grid def printing(arr): for i in range (N): for j in range (N): print (arr[i][j], end = " " ) print () # Checks whether it will be # legal to assign num to the # given row, col def isSafe(grid, row, col, num): # Check if we find the same num # in the similar row , we # return false for x in range ( 9 ): if grid[row][x] = = num: return False # Check if we find the same num in # the similar column , we # return false for x in range ( 9 ): if grid[x][col] = = num: return False # Check if we find the same num in # the particular 3*3 matrix, # we return false startRow = row - row % 3 startCol = col - col % 3 for i in range ( 3 ): for j in range ( 3 ): if grid[i + startRow][j + startCol] = = num: return False return True # Takes a partially filled-in grid and attempts # to assign values to all unassigned locations in # such a way to meet the requirements for # Sudoku solution (non-duplication across rows, # columns, and boxes) */ def solveSudoku(grid, row, col): # Check if we have reached the 8th # row and 9th column (0 # indexed matrix) , we are # returning true to avoid # further backtracking if (row = = N - 1 and col = = N): return True # Check if column value becomes 9 , # we move to next row and # column start from 0 if col = = N: row + = 1 col = 0 # Check if the current position of # the grid already contains # value >0, we iterate for next column if grid[row][col] > 0 : return solveSudoku(grid, row, col + 1 ) for num in range ( 1 , N + 1 , 1 ): # Check if it is safe to place # the num (1-9) in the # given row ,col ->we # move to next column if isSafe(grid, row, col, num): # Assigning the num in # the current (row,col) # position of the grid # and assuming our assigned # num in the position # is correct grid[row][col] = num # Checking for next possibility with next # column if solveSudoku(grid, row, col + 1 ): return True # Removing the assigned num , # since our assumption # was wrong , and we go for # next assumption with # diff num value grid[row][col] = 0 return False # Driver Code # 0 means unassigned cells grid = [[ 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 ]] if (solveSudoku(grid, 0 , 0 )): printing(grid) else : print ( "no solution exists " ) # This code is contributed by sudhanshgupta2019a |
C#
// C# program for above approach using System; class GFG { // N is the size of the 2D matrix N*N static int N = 9; /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ static bool solveSudoku( int [,] grid, int row, int col) { /*if we have reached the 8th row and 9th column (0 indexed matrix) , we are returning true to avoid further backtracking */ if (row == N - 1 && col == N) return true ; // Check if column value becomes 9 , // we move to next row // and column start from 0 if (col == N) { row++; col = 0; } // Check if the current position // of the grid already // contains value >0, we iterate // for next column if (grid[row,col] != 0) return solveSudoku(grid, row, col + 1); for ( int num = 1; num < 10; num++) { // Check if it is safe to place // the num (1-9) in the // given row ,col ->we move to next column if (isSafe(grid, row, col, num)) { /* assigning the num in the current (row,col) position of the grid and assuming our assigned num in the position is correct */ grid[row,col] = num; // Checking for next // possibility with next column if (solveSudoku(grid, row, col + 1)) return true ; } /* removing the assigned num , since our assumption was wrong , and we go for next assumption with diff num value */ grid[row,col] = 0; } return false ; } /* A utility function to print grid */ static void print( int [,] grid) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) Console.Write(grid[i,j] + " " ); Console.WriteLine(); } } // Check whether it will be legal // to assign num to the // given row, col static bool isSafe( int [,] grid, int row, int col, int num) { // Check if we find the same num // in the similar row , we // return false for ( int x = 0; x <= 8; x++) if (grid[row,x] == num) return false ; // Check if we find the same num // in the similar column , // we return false for ( int x = 0; x <= 8; x++) if (grid[x,col] == num) return false ; // Check if we find the same num // in the particular 3*3 // matrix, we return false int startRow = row - row % 3, startCol = col - col % 3; for ( int i = 0; i < 3; i++) for ( int j = 0; j < 3; j++) if (grid[i + startRow,j + startCol] == num) return false ; return true ; } // Driver code static void Main() { int [,] grid = { { 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 } }; if (solveSudoku(grid, 0, 0)) print(grid); else Console.WriteLine( "No Solution exists" ); } } // This code is contributed by divyesh072019. |
Javascript
<script> // Javascript program for above approach // N is the size of the 2D matrix N*N let N = 9; /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ function solveSudoku(grid, row, col) { /* If we have reached the 8th row and 9th column (0 indexed matrix) , we are returning true to avoid further backtracking */ if (row == N - 1 && col == N) return true ; // Check if column value becomes 9 , // we move to next row // and column start from 0 if (col == N) { row++; col = 0; } // Check if the current position // of the grid already // contains value >0, we iterate // for next column if (grid[row][col] != 0) return solveSudoku(grid, row, col + 1); for (let num = 1; num < 10; num++) { // Check if it is safe to place // the num (1-9) in the given // row ,col ->we move to next column if (isSafe(grid, row, col, num)) { /* assigning the num in the current (row,col) position of the grid and assuming our assigned num in the position is correct */ grid[row][col] = num; // Checking for next // possibility with next column if (solveSudoku(grid, row, col + 1)) return true ; } /* removing the assigned num , since our assumption was wrong , and we go for next assumption with diff num value */ grid[row][col] = 0; } return false ; } /* A utility function to print grid */ function print(grid) { for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) document.write(grid[i][j] + " " ); document.write( "<br>" ); } } // Check whether it will be legal // to assign num to the // given row, col function isSafe(grid, row, col, num) { // Check if we find the same num // in the similar row , we // return false for (let x = 0; x <= 8; x++) if (grid[row][x] == num) return false ; // Check if we find the same num // in the similar column , // we return false for (let x = 0; x <= 8; x++) if (grid[x][col] == num) return false ; // Check if we find the same num // in the particular 3*3 // matrix, we return false let startRow = row - row % 3, startCol = col - col % 3; for (let i = 0; i < 3; i++) for (let j = 0; j < 3; j++) if (grid[i + startRow][j + startCol] == num) return false ; return true ; } // Driver Code let grid = [ [ 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 ] ] if (solveSudoku(grid, 0, 0)) print(grid) else document.write( "no solution exists " ) // This code is contributed by rag2127 </script> |
输出
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
复杂性分析：
- 时间复杂性： O（9^（n*n））。 对于每个未分配索引，有9个可能的选项，因此时间复杂度为O（9^（n*n））。
- 空间复杂性： O（n*n）。 为了存储输出数组，需要一个矩阵。
方法2： 回溯。 方法： 像其他人一样 回溯问题 ，数独可以通过一个接一个地给空单元格赋值来解决。在分配号码之前，请检查分配号码是否安全。检查当前行、当前列和当前3X3子网格中是否不存在相同的数字。在检查安全性后，分配号码，并递归地检查此分配是否导致解决方案。如果分配没有找到解决方案，请尝试当前空单元格的下一个数字。如果数字（1到9）中没有一个指向解决方案，则返回false并打印不存在解决方案。
算法：
- 创建一个函数，在分配当前索引后检查网格是否变得不安全。保留行、列和框的Hashmap。如果hashMap中任何数字的频率大于1，则返回false，否则返回true；hashMap可以通过使用循环来避免。
- 创建一个接受网格的递归函数。
- 检查任何未分配的位置。如果存在，则从1到9分配一个数字，检查将该数字分配到当前索引是否会导致网格不安全，如果安全，则递归调用该函数以处理从0到9的所有安全情况。如果任何递归调用返回true，则结束循环并返回true。如果没有递归调用返回true，则返回false。
- 如果没有未分配的位置，则返回true。
C++
// A Backtracking program in // C++ to solve Sudoku problem #include <bits/stdc++.h> using namespace std; // UNASSIGNED is used for empty // cells in sudoku grid #define UNASSIGNED 0 // N is used for the size of Sudoku grid. // Size will be NxN #define N 9 // This function finds an entry in grid // that is still unassigned bool FindUnassignedLocation( int grid[N][N], int & row, int & col); // Checks whether it will be legal // to assign num to the given row, col bool isSafe( int grid[N][N], int row, int col, int num); /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ bool SolveSudoku( int grid[N][N]) { int row, col; // If there is no unassigned location, // we are done if (!FindUnassignedLocation(grid, row, col)) // success! return true ; // Consider digits 1 to 9 for ( int num = 1; num <= 9; num++) { // Check if looks promising if (isSafe(grid, row, col, num)) { // Make tentative assignment grid[row][col] = num; // Return, if success if (SolveSudoku(grid)) return true ; // Failure, unmake & try again grid[row][col] = UNASSIGNED; } } // This triggers backtracking return false ; } /* Searches the grid to find an entry that is still unassigned. If found, the reference parameters row, col will be set the location that is unassigned, and true is returned. If no unassigned entries remain, false is returned. */ bool FindUnassignedLocation( int grid[N][N], int & row, int & col) { for (row = 0; row < N; row++) for (col = 0; col < N; col++) if (grid[row][col] == UNASSIGNED) return true ; return false ; } /* Returns a boolean which indicates whether an assigned entry in the specified row matches the given number. */ bool UsedInRow( int grid[N][N], int row, int num) { for ( int col = 0; col < N; col++) if (grid[row][col] == num) return true ; return false ; } /* Returns a boolean which indicates whether an assigned entry in the specified column matches the given number. */ bool UsedInCol( int grid[N][N], int col, int num) { for ( int row = 0; row < N; row++) if (grid[row][col] == num) return true ; return false ; } /* Returns a boolean which indicates whether an assigned entry within the specified 3x3 box matches the given number. */ bool UsedInBox( int grid[N][N], int boxStartRow, int boxStartCol, int num) { 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 ; } /* Returns a boolean which indicates whether it will be legal to assign num to the given row, col location. */ bool isSafe( int grid[N][N], int row, int col, int num) { /* Check if 'num' is not already placed in current row, current column and current 3x3 box */ return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num) && !UsedInBox(grid, row - row % 3, col - col % 3, num) && grid[row][col] == UNASSIGNED; } /* A utility function to print grid */ void printGrid( int grid[N][N]) { for ( int row = 0; row < N; row++) { for ( int col = 0; col < N; col++) cout << grid[row][col] << " " ; cout << endl; } } // Driver Code int main() { // 0 means unassigned cells 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 } }; if (SolveSudoku(grid) == true ) printGrid(grid); else cout << "No solution exists" ; return 0; } // This is code is contributed by rathbhupendra |
C
// A Backtracking program in C // to solve Sudoku problem #include <stdio.h> // UNASSIGNED is used for empty // cells in sudoku grid #define UNASSIGNED 0 // N is used for the size of // Sudoku grid. The size will be NxN #define N 9 // This function finds an entry // in grid that is still unassigned bool FindUnassignedLocation( int grid[N][N], int & row, int & col); // Checks whether it will be legal // to assign num to the given row, col bool isSafe( int grid[N][N], int row, int col, int num); /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ bool SolveSudoku( int grid[N][N]) { int row, col; // Check If there is no unassigned // location, we are done if (!FindUnassignedLocation(grid, row, col)) return true ; // success! //Cconsider digits 1 to 9 for ( int num = 1; num <= 9; num++) { // Check if looks promising if (isSafe(grid, row, col, num)) { // Make tentative assignment grid[row][col] = num; // Return, if success, yay! if (SolveSudoku(grid)) return true ; // Failure, unmake & try again grid[row][col] = UNASSIGNED; } } // This triggers backtracking return false ; } /* Searches the grid to find an entry that is still unassigned. If found, the reference parameters row, col will be set the location that is unassigned, and true is returned. If no unassigned entries remain, false is returned. */ bool FindUnassignedLocation( int grid[N][N], int & row, int & col) { for (row = 0; row < N; row++) for (col = 0; col < N; col++) if (grid[row][col] == UNASSIGNED) return true ; return false ; } /* Returns a boolean which indicates whether an assigned entry in the specified row matches the given number. */ bool UsedInRow( int grid[N][N], int row, int num) { for ( int col = 0; col < N; col++) if (grid[row][col] == num) return true ; return false ; } /* Returns a boolean which indicates whether an assigned entry in the specified column matches the given number. */ bool UsedInCol( int grid[N][N], int col, int num) { for ( int row = 0; row < N; row++) if (grid[row][col] == num) return true ; return false ; } /* Returns a boolean which indicates whether an assigned entry within the specified 3x3 box matches the given number. */ bool UsedInBox( int grid[N][N], int boxStartRow, int boxStartCol, int num) { 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 ; } /* Returns a boolean which indicates whether it will be legal to assign num to the given row, col location. */ bool isSafe( int grid[N][N], int row, int col, int num) { /* Check if 'num' is not already placed in current row, current column and current 3x3 box */ return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num) && !UsedInBox(grid, row - row % 3, col - col % 3, num) && grid[row][col] == UNASSIGNED; } /* A utility function to print grid */ void printGrid( int grid[N][N]) { for ( int row = 0; row < N; row++) { for ( int col = 0; col < N; col++) printf ( "%2d" , grid[row][col]); printf ( "" ); } } /* Driver Program to test above functions */ int main() { // 0 means unassigned cells 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 } }; if (SolveSudoku(grid) == true ) printGrid(grid); else printf ( "No solution exists" ); return 0; } |
JAVA
/* A Backtracking program in Java to solve Sudoku problem */ class GFG { public static boolean isSafe( int [][] board, int row, int col, int num) { // Row has the unique (row-clash) for ( int d = 0 ; d < board.length; d++) { // Check if the number we are trying to // place is already present in // that row, return false; if (board[row][d] == num) { return false ; } } // Column has the unique numbers (column-clash) for ( int r = 0 ; r < board.length; r++) { // Check if the number // we are trying to // place is already present in // that column, return false; if (board[r][col] == num) { return false ; } } // Corresponding square has // unique number (box-clash) int sqrt = ( int )Math.sqrt(board.length); int boxRowStart = row - row % sqrt; int boxColStart = col - col % sqrt; for ( int r = boxRowStart; r < boxRowStart + sqrt; r++) { for ( int d = boxColStart; d < boxColStart + sqrt; d++) { if (board[r][d] == num) { return false ; } } } // if there is no clash, it's safe return true ; } public static boolean solveSudoku( int [][] board, int n) { int row = - 1 ; int col = - 1 ; boolean isEmpty = true ; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { if (board[i][j] == 0 ) { row = i; col = j; // We still have some remaining // missing values in Sudoku isEmpty = false ; break ; } } if (!isEmpty) { break ; } } // No empty space left if (isEmpty) { return true ; } // Else for each-row backtrack for ( int num = 1 ; num <= n; num++) { if (isSafe(board, row, col, num)) { board[row][col] = num; if (solveSudoku(board, n)) { // print(board, n); return true ; } else { // replace it board[row][col] = 0 ; } } } return false ; } public static void print( int [][] board, int N) { // We got the answer, just print it for ( int r = 0 ; r < N; r++) { for ( int d = 0 ; d < N; d++) { System.out.print(board[r][d]); System.out.print( " " ); } System.out.print( "" ); if ((r + 1 ) % ( int )Math.sqrt(N) == 0 ) { System.out.print( "" ); } } } // Driver Code public static void main(String args[]) { int [][] board = new int [][] { { 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 } }; int N = board.length; if (solveSudoku(board, N)) { // print solution print(board, N); } else { System.out.println( "No solution" ); } } } // This code is contributed // by MohanDas |
python
# A Backtracking program # in Python to solve Sudoku problem # A Utility Function to print the Grid def print_grid(arr): for i in range ( 9 ): for j in range ( 9 ): print arr[i][j], print ( 'n' ) # Function to Find the entry in # the Grid that is still not used # Searches the grid to find an # entry that is still unassigned. If # found, the reference parameters # row, col will be set the location # that is unassigned, and true is # returned. If no unassigned entries # remains, false is returned. # 'l' is a list variable that has # been passed from the solve_sudoku function # to keep track of incrementation # of Rows and Columns def find_empty_location(arr, l): for row in range ( 9 ): for col in range ( 9 ): if (arr[row][col] = = 0 ): l[ 0 ] = row l[ 1 ] = col return True return False # Returns a boolean which indicates # whether any assigned entry # in the specified row matches # the given number. def used_in_row(arr, row, num): for i in range ( 9 ): if (arr[row][i] = = num): return True return False # Returns a boolean which indicates # whether any assigned entry # in the specified column matches # the given number. def used_in_col(arr, col, num): for i in range ( 9 ): if (arr[i][col] = = num): return True return False # Returns a boolean which indicates # whether any assigned entry # within the specified 3x3 box # matches the given number def used_in_box(arr, row, col, num): for i in range ( 3 ): for j in range ( 3 ): if (arr[i + row][j + col] = = num): return True return False # Checks whether it will be legal # to assign num to the given row, col # Returns a boolean which indicates # whether it will be legal to assign # num to the given row, col location. def check_location_is_safe(arr, row, col, num): # Check if 'num' is not already # placed in current row, # current column and current 3x3 box return not used_in_row(arr, row, num) and not used_in_col(arr, col, num) and not used_in_box(arr, row - row % 3 , col - col % 3 , num) # Takes a partially filled-in grid # and attempts to assign values to # all unassigned locations in such a # way to meet the requirements # for Sudoku solution (non-duplication # across rows, columns, and boxes) def solve_sudoku(arr): # 'l' is a list variable that keeps the # record of row and col in # find_empty_location Function l = [ 0 , 0 ] # If there is no unassigned # location, we are done if ( not find_empty_location(arr, l)): return True # Assigning list values to row and col # that we got from the above Function row = l[ 0 ] col = l[ 1 ] # consider digits 1 to 9 for num in range ( 1 , 10 ): # if looks promising if (check_location_is_safe(arr, row, col, num)): # make tentative assignment arr[row][col] = num # return, if success, # ya ! if (solve_sudoku(arr)): return True # failure, unmake & try again arr[row][col] = 0 # this triggers backtracking return False # Driver main function to test above functions if __name__ = = "__main__" : # creating a 2D array for the grid grid = [[ 0 for x in range ( 9 )] for y in range ( 9 )] # assigning values to the grid grid = [[ 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 ]] # if success print the grid if (solve_sudoku(grid)): print_grid(grid) else : print "No solution exists" # The above code has been contributed by Harshit Sidhwa. |
C#
/* A Backtracking program in C# to solve Sudoku problem */ using System; class GFG { public static bool isSafe( int [, ] board, int row, int col, int num) { // Row has the unique (row-clash) for ( int d = 0; d < board.GetLength(0); d++) { // Check if the number // we are trying to // place is already present in // that row, return false; if (board[row, d] == num) { return false ; } } // Column has the unique numbers (column-clash) for ( int r = 0; r < board.GetLength(0); r++) { // Check if the number // we are trying to // place is already present in // that column, return false; if (board[r, col] == num) { return false ; } } // corresponding square has // unique number (box-clash) int sqrt = ( int )Math.Sqrt(board.GetLength(0)); int boxRowStart = row - row % sqrt; int boxColStart = col - col % sqrt; for ( int r = boxRowStart; r < boxRowStart + sqrt; r++) { for ( int d = boxColStart; d < boxColStart + sqrt; d++) { if (board[r, d] == num) { return false ; } } } // if there is no clash, it's safe return true ; } public static bool solveSudoku( int [, ] board, int n) { int row = -1; int col = -1; bool isEmpty = true ; for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (board[i, j] == 0) { row = i; col = j; // We still have some remaining // missing values in Sudoku isEmpty = false ; break ; } } if (!isEmpty) { break ; } } // no empty space left if (isEmpty) { return true ; } // else for each-row backtrack for ( int num = 1; num <= n; num++) { if (isSafe(board, row, col, num)) { board[row, col] = num; if (solveSudoku(board, n)) { // Print(board, n); return true ; } else { // Replace it board[row, col] = 0; } } } return false ; } public static void print( int [, ] board, int N) { // We got the answer, just print it for ( int r = 0; r < N; r++) { for ( int d = 0; d < N; d++) { Console.Write(board[r, d]); Console.Write( " " ); } Console.Write( "" ); if ((r + 1) % ( int )Math.Sqrt(N) == 0) { Console.Write( "" ); } } } // Driver Code public static void Main(String[] args) { int [, ] board = new int [, ] { { 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 } }; int N = board.GetLength(0); if (solveSudoku(board, N)) { // print solution print(board, N); } else { Console.Write( "No solution" ); } } } // This code has been contributed by 29AjayKumar |
Javascript
<script> /* A Backtracking program in Javascript to solve Sudoku problem */ function isSafe(board, row, col, num) { // Row has the unique (row-clash) for (let d = 0; d < board.length; d++) { // Check if the number we are trying to // place is already present in // that row, return false; if (board[row][d] == num) { return false ; } } // Column has the unique numbers (column-clash) for (let r = 0; r < board.length; r++) { // Check if the number // we are trying to // place is already present in // that column, return false; if (board[r][col] == num) { return false ; } } // Corresponding square has // unique number (box-clash) let sqrt = Math.floor(Math.sqrt(board.length)); let boxRowStart = row - row % sqrt; let boxColStart = col - col % sqrt; for (let r = boxRowStart; r < boxRowStart + sqrt; r++) { for (let d = boxColStart; d < boxColStart + sqrt; d++) { if (board[r][d] == num) { return false ; } } } // If there is no clash, it's safe return true ; } function solveSudoku(board, n) { let row = -1; let col = -1; let isEmpty = true ; for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (board[i][j] == 0) { row = i; col = j; // We still have some remaining // missing values in Sudoku isEmpty = false ; break ; } } if (!isEmpty) { break ; } } // No empty space left if (isEmpty) { return true ; } // Else for each-row backtrack for (let num = 1; num <= n; num++) { if (isSafe(board, row, col, num)) { board[row][col] = num; if (solveSudoku(board, n)) { // print(board, n); return true ; } else { // Replace it board[row][col] = 0; } } } return false ; } function print(board, N) { // We got the answer, just print it for (let r = 0; r < N; r++) { for (let d = 0; d < N; d++) { document.write(board[r][d]); document.write( " " ); } document.write( "<br>" ); if ((r + 1) % Math.floor(Math.sqrt(N)) == 0) { document.write( "" ); } } } // Driver Code let board = [ [ 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 ] ]; let N = board.length; if (solveSudoku(board, N)) { // Print solution print(board, N); } else { document.write( "No solution" ); } // This code is contributed by avanitrachhadiya2155 </script> |
输出
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
复杂性分析：
- 时间复杂性： O（9^（n*n））。 对于每个未分配索引，有9个可能的选项，因此时间复杂度为O（9^（n*n））。时间复杂度保持不变，但会有一些早期修剪，因此所花费的时间将远小于原始算法，但上界时间复杂度保持不变。
- 空间复杂性： O（n*n）。 为了存储输出数组，需要一个矩阵。
方法3 : 使用比特面具。
方法： 该方法是对上述两种方法的轻微优化。为每个行/列/框创建一个位掩码，并为网格中的每个元素将相应位掩码中“value”位置的位设置为1，以进行O（1）检查。
算法：
- 创建3个大小为N的数组（一个用于行、列和框）。
- 这些框的索引范围为0到8。（为了找到元素的框索引，我们使用以下公式： 行/3*3+列/3 ).
- 首先映射网格的初始值。
- 每次我们 添加/删除 从网格到网格的元素 将位设置为1/0 到相应的位掩码。
C++
#include <bits/stdc++.h> using namespace std; #define N 9 // Bitmasks for each row/column/box int row[N], col[N], box[N]; bool seted = false ; // Utility function to find the box index // of an element at position [i][j] in the grid int getBox( int i, int j) { return i / 3 * 3 + j / 3; } // Utility function to check if a number // is present in the corresponding row/column/box bool isSafe( int i, int j, int number) { return !((row[i] >> number) & 1) && !((col[j] >> number) & 1) && !((box[getBox(i,j)] >> number) & 1); } // Utility function to set the initial values of a Sudoku board // (map the values in the bitmasks) void setInitialValues( int grid[N][N]) { for ( int i = 0; i < N;i++) for ( int j = 0; j < N; j++) row[i] |= 1 << grid[i][j], col[j] |= 1 << grid[i][j], box[getBox(i, j)] |= 1 << grid[i][j]; } /* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */ bool SolveSudoku( int grid[N][N] , int i, int j) { // Set the initial values if (!seted) seted = true , setInitialValues(grid); if (i == N - 1 && j == N) return true ; if (j == N) j = 0, i++; if (grid[i][j]) return SolveSudoku(grid, i, j + 1); for ( int nr = 1; nr <= N;nr++) { if (isSafe(i, j, nr)) { /* Assign nr in the current (i, j) position and add nr to each bitmask */ grid[i][j] = nr; row[i] |= 1 << nr; col[j] |= 1 << nr; box[getBox(i, j)] |= 1 << nr; if (SolveSudoku(grid, i,j + 1)) return true ; // Remove nr from each bitmask // and search for another possibility row[i] &= ~(1 << nr); col[j] &= ~(1 << nr); box[getBox(i, j)] &= ~(1 << nr); } grid[i][j] = 0; } return false ; } // Utility function to print the solved grid void print( int grid[N][N]) { for ( int i = 0; i < N; i++, cout << '' ) for ( int j = 0; j < N; j++) cout << grid[i][j] << ' ' ; } // Driver Code int main() { // 0 means unassigned cells 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 }}; if (SolveSudoku(grid,0 ,0)) print(grid); else cout << "No solution exists" ; return 0; } // This code is contributed // by Gatea David |
输出
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
复杂性分析：
- 时间复杂性： O（9^（n*n））。对于每个未分配索引，有9个可能的选项，因此时间复杂度为O（9^（n*n））。时间复杂度保持不变，但检查一个数字是否可以安全使用要快得多，O（1）。
- 空间复杂性： O（n*n）。为了存储输出数组，需要一个矩阵，位掩码需要3个额外的大小为n的数组。
参考资料： http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
