De Manière Récursive La Résolution D'Un Puzzle De Sudoku À L'Aide De Mandature Théoriquement

Réponse: Mon pseudo est floue dans l'aspect récursif, mais cette vidéo est utile avec les ressources ci-dessous

http://www.youtube.com/watch?v=p-gpaIGRCQI

http://norvig.com/sudoku.html

Ne pouvez pas saisir la mise en œuvre de cette backtrack algorithme récursif à l'égard d'un puzzle de sudoku.

J'essaie de résoudre un puzzle de sudoku en utilisant récursive de retours en arrière. J'ai toujours pas en mesure d'envelopper l'algorithme général autour de ma tête étant donné le domaine du problème, je suis en train de travailler.

La mandature algorithme que je suis en train d'utilisation semble être la norme, mais je ne peux pas suivre la logique et de savoir ce qui se passe en dessous.

Inclus est la mandature de l'algorithme et de sa définition.

Edit: "Encore une fois, a pris la définition de la classe, de gauche la déclaration et de mettre en place le code de pseudo"

Voici mon pseudo l'utilisation de ce.

Pseudo-Code (C++ mettre en œuvre)
backtrack jeu (81,9) //représente toutes les combinaisons possibles d'entrée et les valeurs de jeu

    //All info is loading into a vector of size 81 with the initial state 
    //puzzle = the initial state 9x9 grid from left to right of integers  
        vector <int> puzzle
while(!not solved && not the end of the vector){
     for(int i =puzzle.begin::iterator i , puzzle.end()) //from 0-80 of the vector until end
        if puzzle[i] != 0
             //leave alone, original state of board
        else
              if (valid move) //a guess is allowed in this column/row/square of the board  
                   solution[i] = puzzle_guess[i]  //guess a move and insert 
              else  //one of previous guesses were wrong
                   game.prune(i); //backtracks, or reverses guesses until valid move
}

//état initial du jeu

    4 0 0  6 0 5  2 0 3
    0 0 0  0 4 9  0 7 5
    0 0 0  1 0 7  6 0 0

    6 0 1  0 0 0  4 8 7
    0 8 0  0 0 0  0 3 0
    2 7 4  0 0 0  5 0 6

    0 0 8  7 0 3  0 0 0
    3 1 0  9 6 0  0 0 0
    7 0 9  2 0 8  0 0 1

Merci

Le seul indice à savoir, c'est la déclaration en utilisant backtrack jeu (81,9) //ce qui signifie l'81, éventuellement, de chiffres et de 9 pour les 9 différentes options.

#ifndef BACKTRACK_H
#define BACKTRACK_H
#include <vector>
#include <algorithm>
class BackTrack {
public:
typedef std::vector<unsigned>::const_iterator const_iterator;
typedef std::vector<unsigned>::const_iterator iterator;
BackTrack (unsigned nVariables, unsigned arity=2);
//Create a backtracking state for a problem with
//nVariables variables, each of which has the same
//number of possible values (arity).
template <class Iterator>
BackTrack (Iterator arityBegin,
Iterator arityEnd);
//Create a backtracking state in which each variable may have
//a different number of possible values. The values are obtained
//as integers stored in positions arityBegin .. arityEnd as per
//the usual conventions for C++ iterators. The number of
//variables in the system are inferred from the number of
//positions in the given range.
unsigned operator[] (unsigned variableNumber) const;
//Returns the current value associated with the indicated
//variable.
unsigned numberOfVariables() const;
//Returns the number of variables in the backtracking system.
unsigned arity (unsigned variableNumber) const;
//Returns the number of potential values that can be assigned
//to the indicated variable.
bool more() const;
//Indicates whether additional candidate solutions exist that
//can be reached by subsequent ++ or prune operaations.
void prune (unsigned level);
//Indicates that the combination of values associated with
//variables 0 .. level-1 (inclusive) has been judged unacceptable
//(regardless of the values that could be given to variables
//level..numberOfVariables()-1.  The backtracking state will advance
//to the next solution in which at least one of the values in the
//variables 0..level-1 will have changed.
BackTrack& operator++();
//Indicates that the combination of values associated with
//variables 0 .. nVariables-1 (inclusive) has been judged unacceptable.
//The backtracking state will advance
//to the next solution in which at least one of the values in the
//variables 0..level-1 will have changed.
BackTrack operator++(int);
//Same as other operator++, but returns a copy of the old backtrack state
//Iterator operations for easy access to the currently assigned values
const_iterator begin() const {return values.begin();}
iterator begin()             {return values.begin();}
const_iterator end() const {return values.end();}
iterator       end()       {return values.end();}
private:
bool done;
std::vector<unsigned> arities;
std::vector<unsigned> values;
};
inline
unsigned BackTrack::operator[] (unsigned variableNumber) const
//Returns the current value associated with the indicated
//variable.
{
return values[variableNumber];
}
inline
unsigned BackTrack::numberOfVariables() const
//Returns the number of variables in the backtracking system.
{
return values.size();
}
inline
unsigned BackTrack::arity (unsigned variableNumber) const
//Returns the number of potential values that can be assigned
//to the indicated variable.
{
return arities[variableNumber];
}
inline
bool BackTrack::more() const
//Indicates whether additional candidate solutions exist that
//can be reached by subsequent ++ or prune operaations.
{
return !done;
}
template <class Iterator>
BackTrack::BackTrack (Iterator arityBegin,
Iterator arityEnd):
//Create a backtracking state in which each variable may have
//a different number of possible values. The values are obtained
//as integers stored in positions arityBegin .. arityEnd as per
//the usual conventions for C++ iterators. The number of
//variables in the system are inferred from the number of
//positions in the given range.
arities(arityBegin, arityEnd), done(false) 
{
fill_n (back_inserter(values), arities.size(), 0);
}
#endif

OriginalL'auteur Bjarn127 | 2013-08-11