数独求解器多解查找实现：现有程序如何新增多解功能

Hey there! Let's tackle your Sudoku multi-solution problem step by step. The core issue with your current solveSudoku function is that it returns immediately after finding the first valid solution, which stops any further backtracking to uncover other possible solutions. Here's how to fix it and add the requested functionality:

Key Changes Needed #

1. Preserve the original grid: We need to keep a copy of the initial unsolved board so every time we look for a new solution, we start from the original state (not the previous solution).
2. Collect all solutions: Instead of returning true on the first solution, we'll collect all valid solved boards in a list.
3. Modify the solve logic: Adjust the recursive solver to continue backtracking after finding a solution to uncover other possibilities.
4. Update the menu handler: For option 'A', we'll iterate through the collected solutions and display them one by one, or notify the user if no more solutions exist.

Modified Code Implementation #

Here's the full, updated code with all required functionality:

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

public class SudokuSolver {
    // Original unsolved grid (preserved to reset for each solution search)
    private static int[][] originalGrid;
    // List to store all found solutions
    private static List<int[][]> solutions = new ArrayList<>();
    private static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        // Initialize your sample grid
        int[][] grid = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
                        {5, 2, 0, 0, 0, 0, 0, 0, 0},
                        {0, 8, 7, 0, 0, 0, 0, 3, 1},
                        {0, 0, 3, 0, 1, 0, 0, 8, 0},
                        {9, 0, 0, 8, 6, 3, 0, 0, 5},
                        {0, 5, 0, 0, 9, 0, 6, 0, 0},
                        {1, 3, 0, 0, 0, 0, 2, 5, 0},
                        {0, 0, 0, 0, 0, 0, 0, 7, 4},
                        {0, 0, 5, 2, 0, 6, 3, 0, 0}};
        
        // Create a deep copy of the original grid to avoid modifying it during solving
        originalGrid = deepCopy(grid);
        // Find all possible solutions upfront
        findAllSolutions(deepCopy(originalGrid));
        
        // Display initial solution if available
        if (!solutions.isEmpty()) {
            System.out.println("Solving the puzzle below:");
            printGrid(originalGrid);
            System.out.println("\nA solution is:");
            printGrid(solutions.get(0));
            handleUserInput(1); // Start at index 1 for the next solution
        } else {
            System.out.println("No valid solutions found for this Sudoku.");
        }
    }

    // Helper to create a deep copy of the grid (critical for preserving original state)
    private static int[][] deepCopy(int[][] grid) {
        int[][] copy = new int[9][9];
        for (int i = 0; i < 9; i++) {
            System.arraycopy(grid[i], 0, copy[i], 0, 9);
        }
        return copy;
    }

    // Modified solver to collect all solutions instead of stopping at the first one
    private static void findAllSolutions(int[][] board) {
        int[] coordinates = new int[2];
        if (!findEmptySpot(board, coordinates)) {
            // Add a copy of the solved board to solutions (not the reference)
            solutions.add(deepCopy(board));
            return;
        }
        int x = coordinates[0];
        int y = coordinates[1];

        for (int num = 1; num <= 9; num++) {
            if (isAvailable(board, x, y, num)) {
                board[x][y] = num;
                findAllSolutions(board);
                board[x][y] = 0; // Backtrack to try other numbers
            }
        }
    }

    // Your existing validation functions (unchanged, with a minor cleanup in isSquareAvailable)
    private static boolean isRowAvailable(int[][] board, int coordinateX, int value) {
        for (int i = 0; i < 9; i++) {
            if (board[coordinateX][i] == value) return false;
        }
        return true;
    }

    private static boolean isColumnAvailable(int[][] board, int coordinateY, int value) {
        for (int i = 0; i < 9; i++) {
            if (board[i][coordinateY] == value) return false;
        }
        return true;
    }

    private static boolean isSquareAvailable(int[][] board, int coordinateX, int coordinateY, int value) {
        // Simplified calculation for the top-left corner of the 3x3 square
        int squareStartX = coordinateX - coordinateX % 3;
        int squareStartY = coordinateY - coordinateY % 3;
        for (int i = squareStartX; i < squareStartX + 3; i++) {
            for (int j = squareStartY; j < squareStartY + 3; j++) {
                if (board[i][j] == value) return false;
            }
        }
        return true;
    }

    private static boolean isAvailable(int[][] board, int coordinateX, int coordinateY, int value) {
        return isRowAvailable(board, coordinateX, value) &&
               isColumnAvailable(board, coordinateY, value) &&
               isSquareAvailable(board, coordinateX, coordinateY, value) &&
               board[coordinateX][coordinateY] == 0;
    }

    private static boolean findEmptySpot(int[][] board, int[] coordinates) {
        for (coordinates[0] = 0; coordinates[0] < 9; coordinates[0]++) {
            for (coordinates[1] = 0; coordinates[1] < 9; coordinates[1]++) {
                if (board[coordinates[0]][coordinates[1]] == 0) return true;
            }
        }
        return false;
    }

    // Handle user menu input with the requested options
    private static void handleUserInput(int currentSolutionIndex) {
        while (true) {
            System.out.println("\nWhat would you like to do? (A) find another solution, (B) change a constraint (C) quit");
            System.out.print("Input: ");
            String response = scanner.nextLine().trim().toUpperCase();
            if (response.isEmpty()) continue;
            char upperResponse = response.charAt(0);

            switch (upperResponse) {
                case 'A':
                    if (currentSolutionIndex < solutions.size()) {
                        System.out.println("\nAnother solution is:");
                        printGrid(solutions.get(currentSolutionIndex));
                        currentSolutionIndex++;
                    } else {
                        System.out.println("\nNo more solutions available for this Sudoku.");
                    }
                    break;
                case 'B':
                    System.out.println("\nModifying constraints...");
                    originalGrid = changeConstraint();
                    // Reset solutions and re-calculate from the new grid
                    solutions.clear();
                    findAllSolutions(deepCopy(originalGrid));
                    if (!solutions.isEmpty()) {
                        System.out.println("\nNew solution after modification:");
                        printGrid(solutions.get(0));
                        currentSolutionIndex = 1;
                    } else {
                        System.out.println("\nNo valid solutions found after modification.");
                    }
                    break;
                case 'C':
                    System.out.println("Exiting program.");
                    scanner.close();
                    return;
                default:
                    System.out.println("Please enter valid option (A/B/C)");
            }
        }
    }

    // Implementation for changing grid constraints (user can edit a cell)
    private static int[][] changeConstraint() {
        System.out.print("Enter row (0-8): ");
        int row = scanner.nextInt();
        System.out.print("Enter column (0-8): ");
        int col = scanner.nextInt();
        System.out.print("Enter value (1-9, 0 to clear): ");
        int val = scanner.nextInt();
        scanner.nextLine(); // Consume leftover newline

        // Validate input before making changes
        if (row >=0 && row <9 && col >=0 && col <9 && val >=0 && val <=9) {
            originalGrid[row][col] = val;
        } else {
            System.out.println("Invalid input, no changes made to the grid.");
        }
        return deepCopy(originalGrid);
    }

    // Helper to print the grid in a readable format
    private static void printGrid(int[][] grid) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Key Explanations #

• Deep Copy: We use deepCopy to ensure we never modify the original grid during solving, and to store distinct copies of each solution (since arrays are reference types).
• Solution Collection: The findAllSolutions function replaces the boolean return with a void, adding a copy of the solved grid to the solutions list whenever it finds a complete board, then continues backtracking to find more possibilities.
• Menu Handling: For option 'A', we track the current solution index and display the next one if available. If the user modifies the grid (option 'B'), we reset the solutions list and re-calculate all possible solutions from the new grid state.

This implementation will let users cycle through all valid solutions, modify board constraints, or quit as needed.

内容的提问来源于stack exchange，提问作者Squidgy14