2

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

该算法使用回溯（因此，使用堆栈）

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);
    }
}
4

2 回答 2

0

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

于 2011-06-27T05:05:56.913 回答
0

这是我很久以前写的。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <algorithm>
#include <iterator>
#include <iomanip>

bool same_row ( int row, int col ) {
    return ( (row / 9 )== (col / 9 ));

}

bool same_col(int row, int col ) {
    return (((row - col) % 9) == 0);

}

bool same_block(int row, int col) {
    return ( (((row/27) == (col/27)))&&(((row % 9)/3) == ((col % 9)/3)));

}

void solve_r(std::vector<int> data) {
    std::vector<int>::iterator found = std::find(data.begin(), data.end(), 0);
    if ( found == data.end()) {
        std::cout << "---+---+---+---+---+---+---+---+---+" << std::endl;
        int limit = 0;
        for ( std::vector<int>::iterator itr = data.begin(); itr != data.end(); ++itr) {
            std::cout << std::setw(3) << *itr  << "|" ;
            if ( limit == 8 ){
                std::cout << std::endl;
                std::cout << "---+---+---+---+---+---+---+---+---+" << std::endl;
                limit  = 0;
            } else {
                limit++;
            }
        }
        std::cout << std::endl << std::endl;
        return;

    }
    int i = (int)(found - data.begin());
    std::set<int> excluded_numbers;
    for ( int j = 0; j < 81; j++) {
        if ( same_row(i,j) || same_col(i,j) || same_block(i,j)) {
            excluded_numbers.insert(data[j]);
        }
    }
    for ( int m = 1; m <= 9; m++) {
        std::set<int>::iterator found = excluded_numbers.find(m);
        if ( found == excluded_numbers.end()) {
            data[i] = m;
            solve_r(data);
        }
    }
}

int main( int argc, char** argv) {
    std::ifstream inFile(argv[1]);
    if(!inFile) {
        exit ( 0 );
    }

    std::vector<int> data;
    std::string str = "";
    while(std::getline(inFile, str)) {
        data.clear();
        for ( std::string::iterator itr = str.begin(); itr != str.end(); ++itr) {
            std::string s;
            s.push_back(*itr);
            std::stringstream ss(s);
            int i = 0;
            ss >> i;
            data.push_back(i);
        }
        solve_r(data);
    }
}


avinash@avinash-laptop:~/work/suduko$ cat 40.inp 
096040001100060004504810390007950043030080000405023018010630059059070830003590007
avinash@avinash-laptop:~/work/suduko$ ./suduko 40.inp 
---+---+---+---+---+---+---+---+---+
  3|  9|  6|  2|  4|  5|  7|  8|  1|
---+---+---+---+---+---+---+---+---+
  1|  7|  8|  3|  6|  9|  5|  2|  4|
---+---+---+---+---+---+---+---+---+
  5|  2|  4|  8|  1|  7|  3|  9|  6|
---+---+---+---+---+---+---+---+---+
  2|  8|  7|  9|  5|  1|  6|  4|  3|
---+---+---+---+---+---+---+---+---+
  9|  3|  1|  4|  8|  6|  2|  7|  5|
---+---+---+---+---+---+---+---+---+
  4|  6|  5|  7|  2|  3|  9|  1|  8|
---+---+---+---+---+---+---+---+---+
  7|  1|  2|  6|  3|  8|  4|  5|  9|
---+---+---+---+---+---+---+---+---+
  6|  5|  9|  1|  7|  4|  8|  3|  2|
---+---+---+---+---+---+---+---+---+
  8|  4|  3|  5|  9|  2|  1|  6|  7|
---+---+---+---+---+---+---+---+---+
  Solving
  -------------------------------
  User CPU Time  : 0 s
  System CPU Time: 0 s
  Wait Time      : 0.001 s
  -------------------------------
  Elapsed Time   : 0.001 s
于 2011-07-18T11:23:29.663 回答