多米诺覆盖问题的回溯解法

题目:现有6*6大小的棋盘和18张多米诺骨牌,每张牌能覆盖2个棋格,求将多米诺骨牌完全覆盖棋盘的所有组合?

?

?

#include <iostream>#include <string>#include <map>#include <stack>#include <set>#include <sstream>using namespace std;const int MAX_LENGTH = 2 * 3;set<string> result;//=================// 棋盘位置类//=================class Position{private:    int x;    int y;public:    Position() : x(-1), y(-1)    {    }    Position(const Position& position) : x(position.getX()), y(position.getY())    {    }    Position(int x, int y) : x(x), y(y)    {        if (x < 0 || x >= MAX_LENGTH)        {            x = -1;        }        if (y < 0 || y >= MAX_LENGTH)        {            y = -1;        }    }    int getX() const    {        return x;    }    int getY() const    {        return y;    }    Position getRight()    {        return Position(x, y + 1);    }    Position getBottom()    {        return Position(x + 1, y);    }    bool valid() const    {        return x >= 0 && x < MAX_LENGTH && y >= 0 && y < MAX_LENGTH;    }    bool operator==(const Position& right) const    {        return x == right.getX() && y == right.getY();    }};//=================// 棋子类//=================class Chessman{private:    pair<Position, Position> positions;public:    Chessman()    {    }        Chessman(const pair<Position, Position>& positions) : positions(positions)    {    }    pair<Position, Position> getPositions() const    {        return positions;    }    bool valid() const    {        if (!positions.first.valid() || !positions.second.valid())        {            return false;        }        if (positions.first == positions.second)        {            return false;        }        return true;    }    bool isXdirection() const    {        if (!valid())        {            return false;        }        return positions.first.getX() == positions.second.getX();    }};//=================// 棋盘类//=================class Chessboard{private:    size_t board[MAX_LENGTH][MAX_LENGTH];    stack<Chessman> chessmen;public:    Chessboard()    {        for (int i = 0; i < MAX_LENGTH; i++)        {            for (int j = 0; j < MAX_LENGTH; j++)            {                board[i][j] = 0;            }        }    }    bool hold(const Chessman& chessman)    {        pair<Position, Position> positions = chessman.getPositions();        Position first = positions.first;        if (!first.valid() || board[first.getX()][first.getY()])        {                        return false;        }                Position second = positions.second;        if (!second.valid() || board[second.getX()][second.getY()])        {                        return false;        }        board[first.getX()][first.getY()]   = chessmen.size() + 1;        board[second.getX()][second.getY()] = chessmen.size() + 1;        chessmen.push(chessman);        if (isFinished())        {            string solution = getSolutionString();            result.insert(solution);            cout<<"Solution Num : "<<result.size()<<endl;            cout<<solution<<endl;            cout<<"====================================="<<endl;        }        return true;    }    bool unhold(Chessman& pop)    {        pop = chessmen.top();        board[pop.getPositions().first.getX()][pop.getPositions().first.getY()]   = 0;        board[pop.getPositions().second.getX()][pop.getPositions().second.getY()] = 0;        chessmen.pop();        return true;    }    bool isHold(const Position& position) const    {        if (position.valid())        {            if (board[position.getX()][position.getY()])            {                return true;            }        }        return false;    }    bool isFinished() const    {        return chessmen.size() == MAX_LENGTH * MAX_LENGTH / 2;    }    string getSolutionString()    {        ostringstream rtn;        for (int i = 0; i < MAX_LENGTH; i++)        {            for (int j = 0; j < MAX_LENGTH; j++)            {                if (i != 0 && j == 0)                {                    rtn<<endl;                }                rtn.width(4);                rtn<<board[i][j];                            }        }        return rtn.str();    }  };int main(int argc, char** argv){    Chessboard board;    bool done = false;    for (int i = 0; i < MAX_LENGTH && !done; i++)    {        for (int j = 0; j < MAX_LENGTH && !done; j++)        {            if (!board.isFinished())            {                     Position currgrid(i, j);                   if (board.isHold(currgrid))                {                    continue;                }                Chessman chessmanR(make_pair(currgrid, currgrid.getRight()));                Chessman chessmanB(make_pair(currgrid, currgrid.getBottom()));                if (board.hold(chessmanR) || board.hold(chessmanB))                {                    continue;                }            }            while (true)            {                Chessman pop;                board.unhold(pop);                                Position popposition = pop.getPositions().first;                i = popposition.getX();                j = popposition.getY();                if (pop.isXdirection())                {                    Chessman change(make_pair(popposition, popposition.getBottom()));                    if (board.hold(change))                    {                        break;                    }                }                if (i == 0 && j == 0)                {                    done = true;                    break;                }            }        }    }    cout<<"OK, Done."<<endl;    return 0;}