4

回答:我的伪在递归方面是模糊的,但这个视频与下面的资源一起很有帮助

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

http://norvig.com/sudoku.html

对于数独游戏,无法掌握这种回溯递归算法的实现。

我正在尝试使用递归回溯解决数独难题。考虑到我正在处理的问题领域,我仍然无法将通用算法包装在脑海中。

我尝试使用的回溯算法似乎是标准的,但我无法遵循逻辑并知道下面发生了什么。

包括回溯算法及其定义。

编辑:“再次,取出类定义,留下声明并放上伪代码”

这是我利用它的伪代码。

伪代码(C++ 实现)回溯游戏 (81,9) // 表示游戏输入和值的所有可能组合

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

//游戏初始状态

    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

谢谢

唯一需要知道的线索是声明使用回溯游戏 (81,9) // 表示 81 个可能的数字和 9 表示 9 个不同的选项。

#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
4

2 回答 2

8

这是一个简单的伪代码,可以帮助您理解递归和回溯:

solve(game):
    if (game board is full)
        return SUCCESS
    else
        next_square = getNextEmptySquare()
        for each value that can legally be put in next_square
            put value in next_square (i.e. modify game state)
            if (solve(game)) return SUCCESS
            remove value from next_square (i.e. backtrack to a previous state)
    return FAILURE

getNextEmptySquare()一旦理解了这一点,接下来就是通过以不同方式修剪状态空间图来了解各种实现将如何影响性能。

我在您的原始伪代码中没有看到任何递归或有条理的搜索,尽管它并不完全清楚,它似乎只是一遍又一遍地尝试随机排列?

于 2013-08-11T06:28:36.107 回答
2

关于数独的要点是,你有大量的状态:9^81 是 78 位的数字。因此,任何从左上角字段开始向右下角处理的“愚蠢”回溯算法都可能陷入看似“无休止”的循环中。

因此,我的建议是像人类一样解决数独问题:找到一个字段,已经填写的数字只允许一个特定的值,然后填写该字段。然后寻找下一个这样的字段。如果不存在更多空字段,只有一个值是合法的,则查找最多允许两个(或通常是可能的最小数量)值的字段,并尝试其中一个值,然后继续递归。回溯,如果出现任何矛盾,然后为一个字段尝试下一个值,即有几种选择。

在伪代码中:

solve(game)
    if (game->is_solved())
        game->print()
        return SUCCESS
    else
        next_square = game->find_most_constrained_square()
        foreach value = next_square->possible_values
            mygame = copyof(game)
            mygame->move(next_square, value)
            if solve(mygame) return SUCCESS
        endforeach
        return FAILURE
    endif

函数 find_most_constrained_square() 计算每个空字段,仍然可以放多少不同的数字,并返回该字段的索引,该字段具有最少的可能性。这甚至可以是一个有 0 个选项的字段。

通过修改后的递归,即使在慢速计算机上使用慢速语言,Sudoko 问题也应该很快得到解决。不要忘记扔掉在 foreach 内循环中制作的各种游戏状态副本!

于 2013-08-11T10:44:56.413 回答