From 3f2baedfbb6b08093ef6df37cbabc2ff15765b9f Mon Sep 17 00:00:00 2001 From: Scott Worley Date: Fri, 1 Jan 2016 21:53:39 -0800 Subject: [PATCH 1/1] Find some long-distance boards Output: 64: 0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 ... 64: 12 11 10 13 0 15 14 9 4 7 1 6 3 8 2 5 64: 15 0 9 13 12 11 10 14 7 3 2 6 4 8 5 1 64: 0 12 10 13 11 15 14 9 8 7 5 2 4 3 6 1 64: 11 0 10 9 12 15 13 14 4 7 5 1 8 3 6 2 ... --- find_long_distance_boards.cc | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) create mode 100644 find_long_distance_boards.cc diff --git a/find_long_distance_boards.cc b/find_long_distance_boards.cc new file mode 100644 index 0000000..22c6c2e --- /dev/null +++ b/find_long_distance_boards.cc @@ -0,0 +1,34 @@ +#include "sliding_tile_lib.h" +#include "gflags/gflags.h" + +#include +#include + +int main(int argc, char** argv) { + gflags::ParseCommandLineFlags(&argc, &argv, false); + + Board goal{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}}; + InvertedBoard invgoal = goal.invert(); + + Board rev{{0,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}}; + std::cout << rev.distance(invgoal) << ": " << rev << std::endl; + + std::random_device rd; + std::mt19937 rng(rd()); + + int max_distance = 0; + while (true) { + Board b{{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}}; + for (int i = 0; i < BOARD_SIZE; i++) { + std::uniform_int_distribution<> get_random_number(0, i); + std::swap(b.board[i], b.board[get_random_number(rng)]); + } + int dist = b.distance(invgoal); + if (dist > max_distance) { + max_distance = dist; + } + if (dist > max_distance - 2) { + std::cout << dist << ": " << b << std::endl; + } + } +} -- 2.44.1