数独ソルバー複数解

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