数独求解器消除策略实现优化：修复next_move方法重复返回已填充位置的问题
Let's break down what's wrong with your current code, then walk through a correct implementation of the Minimum Remaining Values (MRV) heuristic (the elimination strategy you're referencing from Norvig's work) that will boost your solver's performance and avoid returning filled cells.
What's Wrong With Your Current Code
Your current approach has three key flaws:
- Narrow logic: You first pick the row with the most filled cells, then pick a column in that row with the most filled cells. This ignores empty cells in other rows that might have far fewer valid candidates (stronger constraints)—the whole point of the heuristic.
- Missing 3x3 box constraints: Sudoku rules require considering the 3x3 box a cell belongs to, but your code doesn't factor this in. This leads to inaccurate constraint calculations.
- Edge case risk: While your code tries to target empty cells in the selected row, if your max-value variables aren't updated correctly (e.g., all empty columns in the row have the same filled count), you might accidentally retain an old value that points to a now-filled cell after subsequent solves.
Correct Implementation: MRV Heuristic
Norvig's strategy centers on choosing the empty cell with the fewest valid candidates (since this minimizes the number of branching paths in your backtracking solver). Here's a robust implementation:
Step 1: Helper Function to Get Valid Candidates
First, a helper to calculate all possible numbers that can go in an empty cell, respecting row, column, and box rules:
def get_valid_candidates(sudoku, x, y): used_numbers = set() # Add all numbers from the cell's row used_numbers.update(sudoku[x]) # Add all numbers from the cell's column used_numbers.update(row[y] for row in sudoku) # Add all numbers from the cell's 3x3 box box_start_x = (x // 3) * 3 box_start_y = (y // 3) * 3 for bx in range(box_start_x, box_start_x + 3): for by in range(box_start_y, box_start_y + 3): used_numbers.add(sudoku[bx][by]) # Return numbers 1-9 not in used_numbers return [num for num in range(1, 10) if num not in used_numbers]
Step 2: next_move Function Using MRV
This function iterates over all empty cells, calculates their candidate counts, and returns the cell with the fewest candidates (we even shortcut early if we find a cell with only 1 candidate, since that's a guaranteed fill):
def next_move(sudoku): best_cell = None min_candidate_count = 10 # Initialize to a value higher than max possible candidates (9) for x in range(9): for y in range(9): # Skip already filled cells if sudoku[x][y] != 0: continue candidates = get_valid_candidates(sudoku, x, y) count = len(candidates) # If we find a cell with only 1 candidate, return it immediately if count == 1: return [x, y] # Update best cell if current has fewer candidates if count < min_candidate_count: min_candidate_count = count best_cell = [x, y] # Return None if no empty cells remain (sudoku is solved) return best_cell
Why This Works
- No filled cells returned: We explicitly skip any cell that's already filled (
sudoku[x][y] != 0), so there's no chance of returning a non-empty position. - Optimal performance: By choosing cells with the fewest candidates first, we drastically reduce the number of backtracking steps needed. For example, filling a cell with only 1 valid option eliminates entire branches of unnecessary checks.
- Complete constraint checking: We consider rows, columns, and boxes, which aligns with full Sudoku rules and ensures accurate candidate counts.
Testing With Your Sudoku Grid
For your sample grid:
sudoku = [ [0, 0, 0, 0, 0, 0, 0, 5, 0], [2, 0, 7, 0, 0, 9, 0, 0, 0], [6, 0, 0, 3, 5, 1, 0, 0, 0], [5, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 3, 0, 0, 0, 0, 0, 8], [0, 0, 0, 8, 2, 0, 5, 3, 0], [0, 0, 0, 0, 7, 0, 8, 0, 4], [0, 0, 6, 2, 0, 0, 0, 0, 0], [0, 8, 0, 0, 0, 0, 7, 0, 0] ]
Calling next_move(sudoku) will return the empty cell with the fewest valid candidates (likely a cell with 2-3 options) instead of just the first empty cell, leading to much faster solving.
内容的提问来源于stack exchange，提问作者gaming4 mining
