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

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

题目:现有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;
}