n_queens_components.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki
3 //
5 // accompanying file LICENSE_1_0.txt or copy at
7 //=======================================================================
15 #ifndef PAAL_N_QUEENS_COMPONENTS_HPP
16 #define PAAL_N_QUEENS_COMPONENTS_HPP
17
19
20 #include <boost/iterator/function_input_iterator.hpp>
22
23 namespace paal {
24 namespace local_search {
25
29 struct Move {
36  Move(int from, int to) : m_from(from), m_to(to) {}
37
43  int get_from() const { return m_from; }
44
50  int get_to() const { return m_to; }
51
52  private:
53  int m_from;
54  int m_to;
55 };
56
60 struct make_move {
69  Move operator()(int from, int to) const { return Move(from, to); }
70 };
71
76  template <typename Solution>
83  bool operator()(Solution &sol, Move move) const {
84  sol.swap_queens(move.get_from(), move.get_to());
85  return true;
86  }
87 };
88
89 namespace detail {
90
91 struct tuple_to_move {
92  using result_type = Move;
93  result_type operator()(std::tuple<int, int> t) const {
94  return Move(std::get<0>(t), std::get<1>(t));
95  }
96 };
97 }
98
103
109  template <typename Solution> struct types_eval {
110  using SolutionIter = decltype(std::declval<Solution>().begin());
111  using Subset =
113  using IterPair = std::pair<Subset, Subset>;
114  using Range = boost::iterator_range<Subset>;
115  };
116
117  public:
126  template <typename Solution>
128  const Solution &solution) const->typename types_eval<Solution>::Range {
129  return data_structures::make_subsets_iterator_range<2>(
130  solution.begin(), solution.end(), make_move{});
131  }
132 };
133
147  template <typename Solution>
148  int operator()(const Solution &solution, Move move) const {
149  int x1 = move.get_from();
150  int y1 = solution.get_y(x1);
151  int x2 = move.get_to();
152  int y2 = solution.get_y(x2);
153
154  return -solution.get_num_attacing(x1, y2) -
155  solution.get_num_attacing(x2, y1) +
156  solution.get_num_attacing(x1, y1) - 2 +
157  solution.get_num_attacing(x2, y2) - 2 -
158  2 * (std::abs(x1 - x2) == std::abs(y1 - y2));
159  }
160 };
161 }
162 }
163
164 #endif // PAAL_N_QUEENS_COMPONENTS_HPP
Move(int from, int to)
constructor
Move operator()(int from, int to) const
operator()
auto operator()(const Solution &solution) const -> typename types_eval< Solution >::Range
operator() returns all the elements
int get_to() const
getter for m_to
class describing Move
Iterator to all k-subsets of given collection.
int get_from() const
getter for m_from
int operator()(const Solution &solution, Move move) const
computes difference in cost
bool local_search(Solution &solution, SearchStrategy searchStrategy, ContinueOnSuccess succ, ContinueOnFail fail, components...comps)
detail
bool operator()(Solution &sol, Move move) const
Operator swaps elements of the solution range.