/home/archives/knight-path/branch.1/branch.0/delta5682.018/knight-path/solver/maze.cc

Go to the documentation of this file.

//
// knight-path - shortest knight path between two squares
// Copyright (C) 2011 Peter Miller
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or (at
// your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License along
// with this program. If not, see <http://www.gnu.org/licenses/>.
//

#include <deque>

#include <knight-path/solver/maze.h>


solver_maze::~solver_maze()
{
}


solver_maze::solver_maze() :
    solver()
{
}


solver_maze::pointer
solver_maze::create(void)
{
    return pointer(new solver_maze());
}


solver::list_t
solver_maze::solve(const position &from, const position &to)
{
    if (from == to)
    {
        // handle the trivial case
        list_t result;
        result.push_back(to);
        return result;
    }

    enum { unvisited = 99 };

    struct square
    {
        int distance;
        position predecessor;

        square() : distance(unvisited) { }
        square(int d, const position &ap) : distance(d), predecessor(ap) { }
    };

    //
    // We model the chass board by annotating it with the distances
    // between each square and the starting point, and also with the
    // next point backwards in the path.
    //
    // The board array could be replaced by a std::map<position> however this
    // comes with a penalty: O(log n) rather than O(1).  Conversely, the board
    // array means we need to be able to use the position::get_x and get_y
    // methods; a map would mean we could leave them private.  Today we choose
    // speed, and thus choose grope otherwise private members.
    //
    square board[8][8];
    board[from.get_y()][from.get_x()] = square(0, from);

    //
    // Starting from the "from" position, look for additional places
    // reachable by knight moves.
    //
    std::deque<position> work;
    work.push_back(from);
    while (!work.empty())
    {
        position p = work.front();
        work.pop_front();
        int dist = 1 + board[p.get_y()][p.get_x()].distance;

        // ask for a list or reachable positions
        position::list_t candidates = p.knight_moves();

        // check each possible knight move
        for
        (
            position::list_t::const_iterator it = candidates.begin();
            it != candidates.end();
            ++it
        )
        {
            square &b = board[it->get_y()][it->get_x()];
            if (b.distance == unvisited)
            {
                work.push_back(*it);
                b.distance = dist;
                b.predecessor = p;
            }
            else
            {
                //
                // Because we always push new work onto the back of the queue,
                // and we always pop the next job from the front of the
                // queue, it means that the work queue is always ordered from
                // shortest-path to longest-path.
                //
                assert(dist >= b.distance);
#if 0
                if (dist < b.distance)
                {
                    b.distance = dist;
                    b.predecessor = p;
                }
#endif
            }

            //
            // The shortest-path implicit in the ordering means that when we
            // first reach the "to" square, we have found a shortest path --
            // there may be others as short, and there may be others longer, but
            // we can stop when we first reach the "to" square.
            //
            if (*it == to)
            {
                work.clear();
                break;
            }
        }

#if 0
        //
        // For debug, print the in-progress board, annotated with distances
        //
        std::cerr << __FILE__ << ": " << __LINE__ << ": p = " << p << std::endl;
        for (int y = 7; y >= 0; --y)
        {
            std::cerr << "  +---+---+---+---+---+---+---+---+" << std::endl;
            std::cerr << (y + 1);
            std::cerr << " |";
            for (int x = 0; x < 8; ++x)
            {
                const square &b = board[y][x];
                std::cerr << ' ';
                if (b.distance == unvisited)
                    std::cerr << ' ';
                else
                    std::cerr << b.distance;
                std::cerr << " |";
            }
            std::cerr << std::endl;
        }
        std::cerr << "  `---+---+---+---+---+---+---+---'" << std::endl;
        std::cerr << "    A   B   C   D   E   F   G   H" << std::endl;
#endif
    }

    //
    // Build the answer by tracing the path backwards.
    //
    list_t result;
    position p = to;
    while (p != from)
    {
        square &b = board[p.get_y()][p.get_x()];
        assert(b.distance != unvisited);
        result.push_front(p);
        p = b.predecessor;
    }
    return result;
}