數獨求解器多種解決方案

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

基礎好看。你有什麼辦法找到某個難題的所有解決方案是，當你找到一個解決方案時，你將該解決方案存儲在一個列表中，然後繼續下去，就好像你沒有解決方案。所以你回溯並嘗試另一種猜測。

Answer 2

這是我寫的很長一段時間。

#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