以编程方式求解数独

Question

我正在尝试使用Java解决一个数独难题。目前该类无法正确解数独。

此类尝试在9x9矩阵中查找0（空格），并在列表中记下0的位置，以供以后参考。然后，它将使用这些位置来求解该0。不幸的是，它似乎不像我希望的那样起作用。

这是我使用的9x9矩阵：

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

这个9x9矩阵中有51个0，但是当它解决这个难题时，出于某种奇怪的原因，它会附加66个位置。我似乎无法准确指出问题所在。任何帮助都将不胜感激！

这是它尝试的解决方案：

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

代码：

package com.dc.soduku;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


public class Sudoku {

    int[][] grid = new int[9][9];
    int emptyCell = 0;
    List<String> EmptyCells = new ArrayList<String>();

    public Sudoku() {

        for (int i = 0; i < 9; i++) {
            for (int x = 0; x < 9; x++) {

                Scanner scanner = new Scanner(System.in);

                System.out.println("Row " + i + " Column " + x + " (Enter values from 1-9): ");
                int temp = scanner.nextInt();

                grid[i][x] = temp;
            }

        }

    }

    public Sudoku(int[][] gridInput) {

        grid = gridInput;

    }

    public void emptyCellsChecker() {

        int count = 0;

        EmptyCells.clear();

        for (int i = 0; i < 9; i++) {
            for (int x = 0; x < 9; x++) {

                if (grid[i][x] == 0) {

                    System.out.println("Blank at row " + i + " column " + x + ".");
                    count++;

                    EmptyCells.add(i + "," + x);

                }

            }
        }

        System.out.println("Total number of empty cells: " + count);
        // System.out.print(mm.toString());
        System.out.println((EmptyCells.get(1)).substring(0, 1));
        System.out.println((EmptyCells.get(1)).substring(2, 3));

    }

    public void printSudoku() {

        for (int i = 0; i < 9; i++) {
            for (int x = 0; x < 9; x++) {

                System.out.print(grid[i][x] + " ");

            }

            System.out.println("");

        }

    }

    public void appendCell(int row, int col, int replacement) {

        this.grid[row][col] = replacement;

    }

    public int getCell(int row, int col) {

        return grid[row][col];

    }

    public boolean isEmpty() {

        for (int i = 0; i < 9; i++) {
            for (int x = 0; x < 9; x++) {
                if (grid[i][x] == emptyCell) {
                    return true;
                }
            }
        }

        return false;

    }

    public boolean checkRow(int row, int guess) {

        for (int i = 0; i < 9; i++) {
            if (grid[row][i] == guess) {
                return false;
            }

        }

        return true;

    }

    public boolean checkColumn(int col, int guess) {

        for (int i = 0; i < 9; i++) {
            if (grid[i][col] == guess) {
                return false;
            }

        }
        return true;
    }

    public boolean checkBox(int row, int col, int guess) {

        row = (row / 3) * 3;
        col = (col / 3) * 3;

        for (int r = 0; r < 3; r++) {
            for (int c = 0; c < 3; c++) {
                if (grid[row + r][col + c] == guess) {
                    return false;
                }
            }
        }

        return true;
    }

    public boolean checkGuess(int row, int col, int guess) {

        return (checkRow(row, guess) && checkColumn(col, guess) && checkBox(row, col, guess));
    }

    public void solve() {

        int nEmptyCells = EmptyCells.size();
        String tempR, tempC;
        int tRow, tCol, counter = 0;

        if (isEmpty() == false) {

            System.out.println(
                    "Sudoku has no empty cells, you have either provided a solved sudoku or entered something incorrectly.");

        } else {

            for (int i = 0; i < nEmptyCells; i++) {

                tempR = ((EmptyCells.get(i)).substring(0, 1));
                tempC = ((EmptyCells.get(i)).substring(2, 3));

                tRow = Integer.parseInt(tempR);
                tCol = Integer.parseInt(tempC);

                for (int v = 1; v < 10; v++) {

                    if (checkGuess(tRow, tCol, v) == true) {

                        this.grid[tRow][tCol] = v;

                        counter++;
                        System.out.println("Solved row " + tRow + " column " + tCol + " with " + v);
                    }

                }

            }

        }

        System.out.println("Total appended: " + counter);

    }

}

Answer 1

简而言之，你的问题是“对于给定的输入，当只有51个空单元格时，为什么我会得到66个附录？”

您当前的算法：

• 对于网格中的每个空单元格
• 使用网格的当前状态
• 猜每个数字1到9
• 验证当前猜测作为科尔、行和框中的可能解决方案
• 使用可能的解决方案更新网格状态
• 继续尝试每个数字到9

为了回答您的问题，您接受所有可能的解决方案，作为给定网格当前状态的特定单元的解决方案。根据您的算法，它可以正确地生成66个解决方案。

你可以做的是：

• 记录网格中每个空单元格的所有可能解决方案，无需网格更新

Answer 2

回溯算法也解决了此问题：

数独回溯算法（Java）

带回溯的数独求解算法