Java 中的数独

17 Mar 2025 | 6 分钟阅读

数独是一种基于逻辑的数字排列谜题。在经典的数独谜题中，任务是在一个9x9的网格中填入数字，使得每一行、每一列以及每一个3x3的子网格都包含数字1到9（包含1和9）。图示如下：

在代码中，我们将上述9x9的网格输入如下：

grid = {  {7, 0, 0, 0, 0, 0, 2, 0, 0}, 
          {4, 0, 2, 0, 0, 0, 0, 0, 3}, 
          {0, 0, 0, 2, 0, 1, 0, 0, 0}, 
          {3, 0, 0, 1, 8, 0, 0, 9, 7}, 
          {0, 0, 9, 0, 7, 0, 6, 0, 0}, 
          {6, 5, 0, 0, 3, 2, 0, 0, 1}, 
          {0, 0, 0, 4, 0, 9, 0, 0, 0}, 
          {5, 0, 0, 0, 0, 0, 1, 0, 6}, 
          {0, 0, 6, 0, 0, 0, 0, 0, 8} 
       }

网格中有许多0。它表示网格中包含0的单元格是空的，需要被填充。为了填充这些空单元格中的数字，我们将使用回溯法来解决谜题。

使用回溯法

在这种方法中，我们逐个为空单元格分配数字。在分配任何数字之前，我们会检查该数字是否已存在于当前列、当前行或当前3x3子网格中。如果该数字已存在，则我们尝试另一个数字并检查其安全性。

如果相同的数字不存在，则该数字被分配，然后我们递归地检查此分配是否会导致解决方案。如果分配不导致解决方案，则我们尝试另一个数字并重复该过程。如果1到9之间的任何数字都无法导致解决方案，则返回false，并显示消息“不存在解决方案”。

算法

步骤1：创建一个函数，其作用是检查在当前索引处为数字分配时网格是否安全。对于盒子、列和行，创建一个HashMap来存储数字的频率。

如果HashMap显示任何数字的频率大于1，则返回false，否则返回true。除了HashMap，也可以使用循环。

步骤2：编写一个接受网格作为输入的递归函数。

步骤3：查找网格中未分配的位置。如果存在未分配的位置，则分配一个1到9之间的数字，检查分配给当前索引的数字是否使网格安全。

如果网格安全，则递归调用该方法处理1到9之间所有安全的情况。如果任何递归调用返回true，则通过返回true来终止循环。如果没有递归调用返回true，则返回false。

步骤4：如果网格中未分配位置的总数为零，则返回true。

实施

让我们根据上述算法看看实现。

文件名： SudokuPuzzle.java

public class SudokuPuzzle
{
public boolean isSafe(int[][] b, int r, int c, int n)
{
// the loop takes care of the clash in the row of the grid
for (int d = 0; d < b.length; d++)
{

// if the number that we have inserted is already 
// present in that row then return false
if (b[r][d] == n) 
{
return false;
}
}

// the loop takes care of the clash in the column of the grid
for (int r1 = 0; r1 < b.length; r1++)
{

// if the number that we have inserted is already 
// present in that column then return false
if (b[r1][c] == n)
{
return false;
}
}

// the loop takes care of the clash in the sub-grid that is present in the grid
int sqt = (int)Math.sqrt(b.length);
int boxRowSt = r - r % sqt;
int boxColSt = c - c % sqt;

for (int r1 = boxRowSt; r1 < boxRowSt + sqt; r1++)
{
for (int d = boxColSt; d < boxColSt + sqt; d++)
{
// if the number that we have inserted is already 
// present in that sub-grid then return false
if (b[r1][d] == n)
{
return false;
}
}
}

// if there is no clash in the grid, then it is safe and 
// true is returned
return true;
}

public boolean solveSudoku(int[][] b, int num)
{
int r = -1;
int c = -1;
boolean isVacant = true;
for (int i = 0; i < num; i++)
{
for (int j = 0; j < num; j++)
{
if (b[i][j] == 0)
{
r = i;
c = j;

// false value means 
// there is still some 
// vacant cells in the grid
isVacant = false;
break;
}
}

if (!isVacant) 
{
break;
}
}

// there is no empty space left
// in the grid
if (isVacant)
{
return true;
}

// otherwise for each row do the backtracking
for (int no = 1; no <= num; no++)
{
if (isSafe(b, r, c, no))
{
b[r][c] = no;
if (solveSudoku(b, num))
{
// display(board, num);
return true;
}
else
{

b[r][c] = 0;
}
}
}
return false;
}

public void display(int[][] b, int n)
{

// We have got the solution, just display it
for (int i = 0; i < n; i++)
{
for (int d = 0; d < n; d++)
{
System.out.print(b[i][d]);
System.out.print(" ");
}

System.out.print("\n");

if ((i + 1) % (int)Math.sqrt(n) == 0)
{
System.out.print("");
}
}
}

// main method
public static void main(String argvs[])
{

// the 9 x 9  grid 
int[][] b = new int[][] { { 7, 0, 0, 0, 0, 0, 2, 0, 0 }, 
                                        { 4, 0, 2, 0, 0, 0, 0, 0, 3 }, 
                                        { 0, 0, 0, 2, 0, 1, 0, 0, 0 }, 
                                        { 3, 0, 0, 1, 8, 0, 0, 9, 7 }, 
                                        { 0, 0, 9, 0, 7, 0, 6, 0, 0 }, 
                                        { 6, 5, 0, 0, 3, 2, 0, 0, 1 }, 
                                        { 0, 0, 0, 4, 0, 9, 0, 0, 0 }, 
                                        { 5, 0, 0, 0, 0, 0, 1, 0, 6 }, 
                                        { 0, 0, 6, 0, 0, 0, 0, 0, 8 } 
                                     } ;

// creating an object of the class SudokuPuzzle
SudokuPuzzle obj = new SudokuPuzzle();

// computing the size of the grid
int size = b.length;

System.out.println("The grid is: ");
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size; j++)
{
System.out.print(b[i][j] + " ");  
}

System.out.println();
}
System.out.println();
if (obj.solveSudoku(b, size))
{
// display solution

System.out.println("The solution of the grid is: ");
obj.display(b, size);
}
else 
{
System.out.println("There is no solution available.");
}
}
}

输出

The grid is: 
7 0 0 0 0 0 2 0 0 
4 0 2 0 0 0 0 0 3 
0 0 0 2 0 1 0 0 0 
3 0 0 1 8 0 0 9 7 
0 0 9 0 7 0 6 0 0 
6 5 0 0 3 2 0 0 1 
0 0 0 4 0 9 0 0 0 
5 0 0 0 0 0 1 0 6 
0 0 6 0 0 0 0 0 8 

The solution of the grid is: 
7 6 5 8 4 3 2 1 9 
4 1 2 6 9 7 8 5 3 
9 3 8 2 5 1 7 6 4 
3 2 4 1 8 6 5 9 7 
1 8 9 5 7 4 6 3 2 
6 5 7 9 3 2 4 8 1 
8 7 1 4 6 9 3 2 5 
5 9 3 7 2 8 1 4 6 
2 4 6 3 1 5 9 7 8

时间复杂度：对于每个空单元格，有9个可用选项，因此时间复杂度为O(9 ^ (n x n))。

空间复杂度：O(n x n)。因为还需要存储输出网格。

下一主题Java中的圣诞树图案

Java 中的数独

使用回溯法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的数独

使用回溯法

算法

实施

相关帖子

DecimalStyle getDecimalSeparator() method in Java with Examples

Java 中字符串的所有可能组合

Array Rotation in Java

Java 字体

Java Boyer Moore

Java 中从给定数组构建最大数字

Java Flight Recorder

Java Program to Find the Frequency of All Duplicate Elements in an Array

How to convert String to Integer and Integer to String in java

Java 异常消息示例和解释

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器