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
...

diff --git a/find_long_distance_boards.cc b/find_long_distance_boards.cc
new file mode 100644 (file)
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 <iostream>
+#include <random>
+
+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;
+    }
+  }
+}