/home/archives/knight-path/branch.1/branch.0/delta5682.018/knight-path/solver/taxi.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 <knight-path/solver/taxi.h>
#include <knight-path/taxi_distance.h>


solver_taxi::~solver_taxi()
{
}


solver_taxi::solver_taxi()
{
}


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


solver::list_t
solver_taxi::solve(const position &from, const position &to)
{
    shortest_solution.clear();
    list_t path;
    // By including the from position in the path, we can eliminate
    // backtracking to there.
    path.push_back(from);
    ply(from, to, path);

    // Return a list of positions through which the Knight passes.
    // It must include the ending position, but exclude the starting
    // position.
    list_t result = shortest_solution;
    shortest_solution.clear();
    if (result.size() > 1)
        result.pop_front();
    return result;
}


void
solver_taxi::ply(const position &from, const position &to,
    const list_t &progress)
{
    // See if we have arrived at the destination.
    if (from == to)
    {
        if
        (
            shortest_solution.empty()
        ||
            progress.size() < shortest_solution.size()
        )
        {
            shortest_solution = progress;
        }
        return;
    }

    // The longest possible path is six jumps
    // plus one for the start position.
    size_t too_big = shortest_solution.empty() ? 7 : shortest_solution.size();
    if (progress.size() >= too_big)
        return;

    //
    // Ask the position for a list of knight move positions
    // that can be reached from there.
    //
    position::list_t possibilities = from.knight_moves();

    //
    // Sort the list of positions by their distance from the goal position.
    //
    sort(possibilities.begin(), possibilities.end(), taxi_distance(to));

    //
    // Try each of those possibilities.
    //
    for
    (
        position::list_t::const_iterator it = possibilities.begin();
        it != possibilities.end();
        ++it
    )
    {
        // Don't revisit any position.
        if (std::find(progress.begin(), progress.end(), *it) == progress.end())
        {
            list_t one_longer(progress);
            one_longer.push_back(*it);
            ply(*it, to, one_longer);
        }
    }
}