n_queens_components.hpp

Go to the documentation of this file.

//=======================================================================
// Copyright (c) 2013 Piotr Wygocki
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef PAAL_N_QUEENS_COMPONENTS_HPP
#define PAAL_N_QUEENS_COMPONENTS_HPP

#include "paal/data_structures/subset_iterator.hpp"

#include <boost/iterator/function_input_iterator.hpp>
#include <boost/range/adaptor/transformed.hpp>

namespace paal {
namespace local_search {

struct Move {
    Move(int from, int to) : m_from(from), m_to(to) {}

    int get_from() const { return m_from; }

    int get_to() const { return m_to; }

  private:
    int m_from;
    int m_to;
};

struct make_move {
    Move operator()(int from, int to) const { return Move(from, to); }
};

struct n_queens_commit {
    template <typename Solution>
        bool operator()(Solution &sol, Move move) const {
        sol.swap_queens(move.get_from(), move.get_to());
        return true;
    }
};

namespace detail {

struct tuple_to_move {
    using result_type = Move;
    result_type operator()(std::tuple<int, int> t) const {
        return Move(std::get<0>(t), std::get<1>(t));
    }
};
} 

class n_queensget_moves {

    template <typename Solution> struct types_eval {
        using SolutionIter = decltype(std::declval<Solution>().begin());
        using Subset =
            data_structures::subsets_iterator<2, SolutionIter, make_move>;
        using IterPair = std::pair<Subset, Subset>;
        using Range = boost::iterator_range<Subset>;
    };

  public:
    template <typename Solution>
    auto operator()(
        const Solution &solution) const->typename types_eval<Solution>::Range {
        return data_structures::make_subsets_iterator_range<2>(
                solution.begin(), solution.end(), make_move{});
    }
};

struct n_queens_gain {
    template <typename Solution>
    int operator()(const Solution &solution, Move move) const {
        int x1 = move.get_from();
        int y1 = solution.get_y(x1);
        int x2 = move.get_to();
        int y2 = solution.get_y(x2);

        return -solution.get_num_attacing(x1, y2) -
               solution.get_num_attacing(x2, y1) +
               solution.get_num_attacing(x1, y1) - 2 +
               solution.get_num_attacing(x2, y2) - 2 -
               2 * (std::abs(x1 - x2) == std::abs(y1 - y2));
    }
};
} 
} 

#endif // PAAL_N_QUEENS_COMPONENTS_HPP