时间戳

首页 > 解决方案 > Java 程序无故无限运行 - 没有 StackOverflow 但程序永远不会终止 - 数独生成器

java - Java 程序无故无限运行 - 没有 StackOverflow 但程序永远不会终止 - 数独生成器

问题描述

我正在尝试在 java 9+ 中构建一个基本的数独生成器。

该代码看起来很好，直到它停止返回一个新数字的随机点，但是生成随机数的函数仍然会产生我用日志测试的数字。但它达到某个数字并停止打印。我不知道为什么。我对算法和回溯非常陌生，因此您可以提供任何见解，我们将不胜感激。

下面的代码

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Scratch_5
{

    static boolean safe = true;
    static int[][] grid = new int[9][9];
    public static void main(String[] args)
    {
        for(int i = 0; i < grid.length; i++)
        {
            for(int j = 0; j < grid[i].length; j++)
            {
                int temp = 0;
                do
                {
                    temp = getNumber();
                }while (!noConflict(grid, i, j, temp));
                grid[i][j] = temp;
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }

    }

    static int getNumber()
    {
        Random r = new Random();

        int temp = 0;
        temp = r.nextInt(10-0);
        return temp;
    }
    public static boolean noConflict(int[][] array, int row, int col, int num) {

        for (int i = 0; i < 9; i++) {
            if (array[row][i] == num) {
                return false;
            }
            if (array[i][col] == num) {
                return false;
            }
        }

        int gridRow = row - (row % 3);
        int gridColumn = col - (col % 3);
        for (int p = gridRow; p < gridRow + 3; p++) {
            for (int q = gridColumn; q < gridColumn + 3; q++) {
                if (array[p][q] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}

谢谢你。

标签： javaalgorithmbacktracking

解决方案

你的逻辑有缺陷。您将创建无法完成的配置，因此您将陷入 do while 循环。让我用一个简单的例子来证明这一点：

1 2 3 4 5 6 7 8 9
4 5 6 1 2 3 . . .

任何带点的位置都不能填充，因为框里已经有 7、8 或 9。

您可以编写一个数独求解器，然后将随机数放入网格中并尝试​​求解。一旦有一个唯一的解决方案（这可以通过从底部解决来检查，尝试 1 然后 2 然后 3 等等，从顶部尝试先 9 然后 8 然后 7 等等，如果 2 个解决方案匹配它是独一无二的），你有一个数独（不是你想要生成的数独）。

推荐阅读