如何高效解决Kakurasu谜题？Java实现及动态规划应用问询

Hey there! Let's break down how to tackle Kakurasu puzzles efficiently, then dive into implementing a dynamic programming (DP) solution in Java—since that's what you're stuck on. First, a quick recap for context: Kakurasu is an n×n grid where each row/column has a target sum. You mark cells such that the sum of column numbers in a marked row equals the row's target, and the sum of row numbers in a marked column equals the column's target.

一、通用高效解法思路 #

Before jumping into code, let's cover the core strategies to solve Kakurasu fast:

• Constraint Propagation: Start with rows/columns that have small target sums or limited possible combinations. For example, if a row's target is 3, only {1,2} or {3} are valid—this instantly narrows down your options and eliminates impossible paths early.
• Pruned Backtracking: When exploring possible choices, if a current selection makes a row/column's remaining sum unreachable (e.g., remaining sum is negative, or smaller than the smallest possible remaining cell value), backtrack immediately instead of wasting time on dead ends.
• Dynamic Programming: Great for smaller puzzles (n ≤ 10 roughly). It avoids redundant calculations by storing valid intermediate states, which we'll focus on next.

二、Java动态规划实现详解 #

The key challenge with DP for Kakurasu is defining a manageable state. Since we process rows one by one, our state needs to track the current sum of each column (since column sums depend on the rows we've marked so far). Here's a step-by-step implementation:

1. Precompute Row Candidates #

First, for each row, generate all valid column subsets that add up to the row's target sum. This saves us from recalculating these subsets during the DP phase.

2. DP State Definition #

We'll use a HashMap where:

• Key: An immutable list representing the current sum of each column (so we can track unique states)
• Value: The path of row selections that led to this state (to reconstruct the solution later)

3. State Transition #

• Initialize the DP with all valid first-row selections and their corresponding column sum states.
• For each subsequent row, iterate over all previous valid states, apply each possible row selection, compute the new column sum state, and keep only states where no column sum exceeds its target.
• After processing all rows, check if any state matches the exact column target sums—that's our solution.

Full Java Code Example #

import java.util.*;

public class KakurasuSolver {
    private int gridSize;
    private int[] rowTargets;
    private int[] colTargets;
    private List<List<Set<Integer>>> rowCandidateSubsets;

    public KakurasuSolver(int n, int[] rowSums, int[] colSums) {
        this.gridSize = n;
        this.rowTargets = rowSums;
        this.colTargets = colSums;
        this.rowCandidateSubsets = precomputeRowCandidates();
    }

    // Precompute all valid column subsets for each row
    private List<List<Set<Integer>>> precomputeRowCandidates() {
        List<List<Set<Integer>>> allCandidates = new ArrayList<>();
        for (int rowIdx = 0; rowIdx < gridSize; rowIdx++) {
            int target = rowTargets[rowIdx];
            List<Set<Integer>> rowSubsets = new ArrayList<>();
            backtrackColumnSubsets(1, target, new HashSet<>(), rowSubsets);
            allCandidates.add(rowSubsets);
        }
        return allCandidates;
    }

    private void backtrackColumnSubsets(int currentCol, int remainingSum, Set<Integer> currentSelection, List<Set<Integer>> result) {
        if (remainingSum == 0) {
            result.add(new HashSet<>(currentSelection));
            return;
        }
        if (currentCol > gridSize || remainingSum < 0) {
            return;
        }
        // Include current column
        currentSelection.add(currentCol);
        backtrackColumnSubsets(currentCol + 1, remainingSum - currentCol, currentSelection, result);
        currentSelection.remove(currentCol);
        // Exclude current column
        backtrackColumnSubsets(currentCol + 1, remainingSum, currentSelection, result);
    }

    // DP-based solver
    public List<Set<Integer>> findSolution() {
        HashMap<List<Integer>, List<Set<Integer>>> dpState = new HashMap<>();

        // Initialize DP with first row candidates
        for (Set<Integer> firstRowChoice : rowCandidateSubsets.get(0)) {
            List<Integer> initialColSums = new ArrayList<>(Collections.nCopies(gridSize, 0));
            boolean isValid = true;
            int firstRowNum = 1; // Rows are 1-indexed for sum calculations

            for (int col : firstRowChoice) {
                int newColSum = initialColSums.get(col - 1) + firstRowNum;
                if (newColSum > colTargets[col - 1]) {
                    isValid = false;
                    break;
                }
                initialColSums.set(col - 1, newColSum);
            }

            if (isValid) {
                List<Set<Integer>> path = new ArrayList<>();
                path.add(firstRowChoice);
                dpState.put(Collections.unmodifiableList(initialColSums), path);
            }
        }

        // Process remaining rows
        for (int rowIdx = 1; rowIdx < gridSize; rowIdx++) {
            HashMap<List<Integer>, List<Set<Integer>>> newDpState = new HashMap<>();
            int currentRowNum = rowIdx + 1;

            for (Map.Entry<List<Integer>, List<Set<Integer>>> entry : dpState.entrySet()) {
                List<Integer> prevColSums = entry.getKey();
                List<Set<Integer>> prevPath = entry.getValue();

                for (Set<Integer> currentRowChoice : rowCandidateSubsets.get(rowIdx)) {
                    List<Integer> newColSums = new ArrayList<>(prevColSums);
                    boolean isValid = true;

                    for (int col : currentRowChoice) {
                        int updatedSum = newColSums.get(col - 1) + currentRowNum;
                        if (updatedSum > colTargets[col - 1]) {
                            isValid = false;
                            break;
                        }
                        newColSums.set(col - 1, updatedSum);
                    }

                    if (!isValid) continue;

                    List<Integer> immutableState = Collections.unmodifiableList(newColSums);
                    if (!newDpState.containsKey(immutableState)) {
                        List<Set<Integer>> newPath = new ArrayList<>(prevPath);
                        newPath.add(currentRowChoice);
                        newDpState.put(immutableState, newPath);
                    }
                }
            }

            dpState = newDpState;
            if (dpState.isEmpty()) return null; // No valid paths left
        }

        // Check for the final valid state (all columns meet their targets)
        for (Map.Entry<List<Integer>, List<Set<Integer>>> entry : dpState.entrySet()) {
            List<Integer> finalColSums = entry.getKey();
            boolean isSolution = true;
            for (int colIdx = 0; colIdx < gridSize; colIdx++) {
                if (!finalColSums.get(colIdx).equals(colTargets[colIdx])) {
                    isSolution = false;
                    break;
                }
            }
            if (isSolution) return entry.getValue();
        }

        return null; // No solution exists
    }

    public static void main(String[] args) {
        // Example 3x3 Kakurasu puzzle
        int n = 3;
        int[] rowSums = {3, 4, 3};
        int[] colSums = {2, 4, 4};

        KakurasuSolver solver = new KakurasuSolver(n, rowSums, colSums);
        List<Set<Integer>> solution = solver.findSolution();

        if (solution != null) {
            System.out.println("Found a solution:");
            for (int i = 0; i < solution.size(); i++) {
                System.out.printf("Row %d: Selected columns %s%n", i+1, solution.get(i));
            }
        } else {
            System.out.println("No valid solution exists for this puzzle.");
        }
    }
}

Key Notes on the Code #

• Candidate Precomputation: The precomputeRowCandidates method uses backtracking to generate all valid column subsets for each row—this avoids redundant work during DP.
• State Management: Using an immutable list for column sums ensures we can use it as a key in the HashMap, tracking unique states efficiently.
• Early Pruning: We discard any state where a column sum exceeds its target immediately, keeping the DP state space as small as possible.

When to Use DP vs. Backtracking #

• DP Works Best: For small grids (n ≤ 10) where the state space is manageable. It's great if you need to solve multiple similar puzzles, as you can reuse state logic.
• Backtracking is Better: For larger grids, since DP state space grows exponentially with grid size. Pair it with constraint propagation to prune dead ends quickly.

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