c++ - 数独求解器多解

Question

下面我有一个 9x9 数独解算器的大纲，但我不确定如何将多个解决方案合并到具有部分条目的特定数独中，如果它还没有的话。有人可以帮我解决这个问题吗？

该算法使用回溯(因此，使用堆栈)

Algorithm findSolutions:
  Given:
    (cell, value) findDecidableCell(puzzle) - returns reference to a cell (if any) whose value 
        can be immediately decided along that value
    void Puzzle::decide(cell, value) - note that value has been decided for cell
    bool Puzzle::solved() - return true if the puzzle has been solved

  Input: 
    puzzle - ADT representing the set of possible solutions to current puzzle
    strategies[] - list of deductive strategies

  Returns:
    list of solutions

---

list<Puzzle> solutions
stack<Puzzle> alternatives  // holds alternate outcomes of speculative simplifications
alternatives.push(puzzle)   // our start state is our first alternative

while(!alternatives.empty()) {          // more solutions possible
    puzzle = alternatives.pop()

    // decide all immediately decidable cells
    while((cell, value) = findDecidableCell(puzzle)) {
        puzzle.decide(cell, value)
    }

    // try simplification strategies until we hit a dead end or solution
    simplificationFound = true
    while(!puzzle.solved() && simplificationFound) {
        // try deductive strategies
        simplificationFound = false
        for(i = 0; i < strategies.length && !simplificationFound; ++i) {
            simplificationFound = strategies[i].simplify(&puzzle)
        } 

        // fall back to guessing
        if(!simplificationFound) {
            Puzzle alternative;
            if(simplificationFound = guess(&puzzle, &alternative)) {
                // guess may be wrong, record alternate outcome
                alternatives.push(alternative);
            }
        }

        // decide all immediately decidable cells before looking for
        // further simplifications
        if(simplificationFound) {
            while((cell, value) = findDecidableCell(puzzle)) {
                puzzle.decide(cell, value)
            }
        }
    }

    // We either found a solution or a contradiction (no simplifications)
    if(puzzle.solved()) {
        solutions.push_back(puzzle);
    }
}

Answer 1

基础看起来不错。要找到某个难题的所有解决方案，您必须做的是，当您找到解决方案时，您将该解决方案存储在列表中，然后继续，就好像您没有解决方案一样。所以你回溯并尝试另一个猜测。