Рекурсивное решение головоломки судоку с использованием теоретического отслеживания ⇐ C++

[Anonymous]

Ответ: Мой псевдо нечеткий в рекурсивном аспекте, но это видео полезно вместе с ресурсами ниже

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

http://norvig.com/sudoku.html

не может понять реализацию этого рекургоритма рекурсивного обращения в отношении головоломки судоку. < /strong> < /p>

i «Я пытаюсь решить головоломку судоку, используя рекурсивную обратную связь. Я все еще не смог обернуть общий алгоритм в моей голове, учитывая проблемный домен, в котором я работаю. Стандартный, но я не могу следовать логике и знаю, что происходит внизу. < /p>

Изменить: «Опять же, выпустил определение класса, оставила объявление и поместил псевдод» < /p>

Вот мой псевдокод, использующий это. < /P>

Pseudo -код (C ++ реализация)
игра в Backtrack (81,9) // Представляет все возможные Комбинации ввода и значений для игры < /p>

//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 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 != 0
//leave alone, original state of board
else
if (valid move) //a guess is allowed in this column/row/square of the board
solution = puzzle_guess //guess a move and insert
else // one of previous guesses were wrong
game.prune(i); //backtracks, or reverses guesses until valid move
}
< /code>

// начальное состояние игры < /p>

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
< /code>

Спасибо < /p>

Единственная подсказка - это объявление с использованием игры Backtrack (81,9) // Узнав 81, возможно, числа и 9 для 9 различных вариантов. < /p>

#ifndef BACKTRACK_H
#define BACKTRACK_H

#include
#include

class BackTrack {
public:
typedef std::vector::const_iterator const_iterator;
typedef std::vector::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
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 arities;
std::vector 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
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


Подробнее здесь: https://stackoverflow.com/questions/181 ... oretically