Sudoku Generator 程序 · GeeksForGeeks 中文系列教程

# Sudoku Generator 程序 > 原文： [https://www.geeksforgeeks.org/program-sudoku-generator/](https://www.geeksforgeeks.org/program-sudoku-generator/) <center>**Background:**</center> Following are the rules of Suduku for a player. 1. 在所有 9 个 3×3 子矩阵中，元素应为 1-9，不可重复。 2. 在所有行中，应该有 1-9 之间的元素，不能重复。 3. 在所有列中，元素应在 1-9 之间，且不得重复。任务是生成有效的 9 x 9 Suduku 网格，即玩家可以按照上述规则填充网格。可以使用**简单的初始解决方案**。 1. 随机取 1-9 的任何数字。 2. 检查放入电池是否安全（行，列和框） 3. 如果安全，请将其放到下一个位置，然后转到步骤 1。 4. 如果不安全，请不执行步骤 1。 5. 矩阵完全填充后，删除 k no。元素随机完成游戏。 **改进的解决方案**：如果我们了解此游戏中的模式，则可以改进解决方案。我们可以观察到，对角存在的所有 3 x 3 矩阵最初与其他 3 x 3 相邻矩阵无关，因为其他矩阵为空。 ``` 3 8 5 0 0 0 0 0 0 9 2 1 0 0 0 0 0 0 6 4 7 0 0 0 0 0 0 0 0 0 1 2 3 0 0 0 0 0 0 7 8 4 0 0 0 0 0 0 6 9 5 0 0 0 0 0 0 0 0 0 8 7 3 0 0 0 0 0 0 9 6 2 0 0 0 0 0 0 1 4 5 ``` （我们可以观察到，在上面的矩阵中，对角矩阵最初独立于其他空矩阵）。因此，如果我们先填充它们，则只需要进行复选框检查即可，因此不需要进行列/行检查。其次，当我们填充其余非对角元素时，我们将不必使用随机生成器，但是可以通过检查 1 到 9 来递归填充。 ``` Following is the improved logic for the problem. 1\. Fill all the diagonal 3x3 matrices. 2\. Fill recursively rest of the non-diagonal matrices. For every cell to be filled, we try all numbers until we find a safe number to be placed. 3\. Once matrix is fully filled, remove K elements randomly to complete game. ``` ``` /* Java program for Sudoku generator */ import java.lang.*; public class Sudoku { int[] mat[]; int N; // number of columns/rows. int SRN; // square root of N int K; // No. Of missing digits // Constructor Sudoku(int N, int K) { this.N = N; this.K = K; // Compute square root of N Double SRNd = Math.sqrt(N); SRN = SRNd.intValue(); mat = new int[N][N]; } // Sudoku Generator public void fillValues() { // Fill the diagonal of SRN x SRN matrices fillDiagonal(); // Fill remaining blocks fillRemaining(0, SRN); // Remove Randomly K digits to make game removeKDigits(); } // Fill the diagonal SRN number of SRN x SRN matrices void fillDiagonal() { for (int i = 0; i<N; i=i+SRN) // for diagonal box, start coordinates->i==j fillBox(i, i); } // Returns false if given 3 x 3 block contains num. boolean unUsedInBox(int rowStart, int colStart, int num) { for (int i = 0; i<SRN; i++) for (int j = 0; j<SRN; j++) if (mat[rowStart+i][colStart+j]==num) return false; return true; } // Fill a 3 x 3 matrix. void fillBox(int row,int col) { int num; for (int i=0; i<SRN; i++) { for (int j=0; j<SRN; j++) { do { num = randomGenerator(N); } while (!unUsedInBox(row, col, num)); mat[row+i][col+j] = num; } } } // Random generator int randomGenerator(int num) { return (int) Math.floor((Math.random()*num+1)); } // Check if safe to put in cell boolean CheckIfSafe(int i,int j,int num) { return (unUsedInRow(i, num) && unUsedInCol(j, num) && unUsedInBox(i-i%SRN, j-j%SRN, num)); } // check in the row for existence boolean unUsedInRow(int i,int num) { for (int j = 0; j<N; j++) if (mat[i][j] == num) return false; return true; } // check in the row for existence boolean unUsedInCol(int j,int num) { for (int i = 0; i<N; i++) if (mat[i][j] == num) return false; return true; } // A recursive function to fill remaining // matrix boolean fillRemaining(int i, int j) { // System.out.println(i+" "+j); if (j>=N && i<N-1) { i = i + 1; j = 0; } if (i>=N && j>=N) return true; if (i < SRN) { if (j < SRN) j = SRN; } else if (i < N-SRN) { if (j==(int)(i/SRN)*SRN) j = j + SRN; } else { if (j == N-SRN) { i = i + 1; j = 0; if (i>=N) return true; } } for (int num = 1; num<=N; num++) { if (CheckIfSafe(i, j, num)) { mat[i][j] = num; if (fillRemaining(i, j+1)) return true; mat[i][j] = 0; } } return false; } // Remove the K no. of digits to // complete game public void removeKDigits() { int count = K; while (count != 0) { int cellId = randomGenerator(N*N); // System.out.println(cellId); // extract coordinates i and j int i = (cellId/N); int j = cellId%9; if (j != 0) j = j - 1; // System.out.println(i+" "+j); if (mat[i][j] != 0) { count--; mat[i][j] = 0; } } } // Print sudoku public void printSudoku() { for (int i = 0; i<N; i++) { for (int j = 0; j<N; j++) System.out.print(mat[i][j] + " "); System.out.println(); } System.out.println(); } // Driver code public static void main(String[] args) { int N = 9, K = 20; Sudoku sudoku = new Sudoku(N, K); sudoku.fillValues(); sudoku.printSudoku(); } } ``` 输出：[ **0** 表示未填充] ``` 2 3 0 4 1 5 0 6 8 0 8 0 2 3 6 5 1 9 1 6 0 9 8 7 2 3 4 3 1 7 0 9 4 0 2 5 4 5 8 1 2 0 6 9 7 9 2 6 0 5 8 3 0 1 0 0 0 5 0 0 1 0 2 0 0 0 8 4 2 9 0 3 5 9 2 3 7 1 4 8 6 ``` 本文由 **Ankur Trisal（ankur.trisal@gmail.com）**提供。如果您喜欢 GeeksforGeeks 并希望做出贡献，则也可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。