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。