2 files changed, 30 insertions, 12 deletions

diff --git a/doc/h48.md b/doc/h48.md
index 6b31503..30b5171 100644
--- a/doc/h48.md
+++ b/doc/h48.md
@@ -334,12 +334,15 @@ encountered in this step is of course added to the list of solutions.
 #### Heuristically sorting tasks
 
 The tasks described in the previous paragraph (multi-threading) are
-initially searched in an arbitrary order. However, after searching at a
-sufficient depth, we have gathered some data that allows us to make some
-heuristical improvements: the tasks that leads to visiting more positions
-(or in other words, where we go over the estimated lower bounds less
-often), are more likely to yield the optimal solution. Thus we sort the
-tasks based on this.
+initially searched in an arbitrary order. However, after searching
+at a sufficient depth, we have gathered some data that allows us to
+make some heuristical improvements: the tasks that leads to visiting
+more positions (or in other words, where we go over the estimated lower
+bounds less often), are more likely to yield the optimal solution. Thus
+we sort the tasks based on this, adjusting by a small factor due to the
+fact that sequences ending in U, R or F moves have more continuations
+than those ending in D, L or B moves - as we don't allow, for example,
+both U D and D U, but only the former.
 
 Preliminary benchmark show a performance improvement of around 40%
 when searching a single solution. When searching for multiple optimal
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index 42d15f8..6026ec7 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -12,7 +12,7 @@
 typedef struct {
         cube_t cube;
         uint8_t moves[H48_STARTING_MOVES];
-        int64_t nodes_visited;
+        int64_t rank;
 } solve_h48_task_t;
 
 typedef struct {
@@ -283,6 +283,7 @@ STATIC void *
 solve_h48_runthread(void *arg)
 {
         int i, j;
+        uint8_t lastmove;
         int64_t nprev;
         dfsarg_solve_h48_t *dfsarg;
 
@@ -295,8 +296,6 @@ solve_h48_runthread(void *arg)
                 while (*dfsarg->status == NISSY_STATUS_PAUSE)
                         msleep(BASE_SLEEP_TIME);
 
-                dfsarg->tasks[i].nodes_visited = 0;
-
                 solution_moves_reset(dfsarg->solution_moves);
                 memcpy(dfsarg->solution_moves->moves,
                     dfsarg->tasks[i].moves, H48_STARTING_MOVES);
@@ -317,7 +316,20 @@ solve_h48_runthread(void *arg)
 
                 solve_h48_dfs(dfsarg);
 
-                dfsarg->tasks[i].nodes_visited = dfsarg->nodes_visited - nprev;
+                /*
+                We compute the "rank" of each taks, which is used in the next
+                step of the IDFS to sort them. This heuristically leads us
+                faster to a solution.  The rank is computed by taking the
+                number of nodes visited, adjusted by a factor of about
+                sqrt(2)/sqrt(3) because there are more sequences starting with
+                U, R and F than with D, L and B, as we don't allow e.g. both
+                U D and D U, but only U D.
+                This trick was suggested by Chen Shuang, the implementation is
+                inspired by Andrew Skalski's vcube.
+                */
+                lastmove = dfsarg->tasks[i].moves[H48_STARTING_MOVES-1];
+                dfsarg->tasks[i].rank = (dfsarg->nodes_visited - nprev) *
+                    (movebase(lastmove) % 2 == 0 ? 47525 : 58206);
                 nprev = dfsarg->nodes_visited;
         }
 
@@ -417,8 +429,11 @@ solve_h48_log_solutions(solution_list_t s[static 1], size_t e)
 STATIC int
 solve_h48_compare_tasks(const void *x, const void *y)
 {
-        return ((solve_h48_task_t *)y)->nodes_visited
-            - ((solve_h48_task_t *)x)->nodes_visited;
+        int64_t nodes_x = ((solve_h48_task_t *)x)->rank;
+        int64_t nodes_y = ((solve_h48_task_t *)y)->rank;
+
+        /* Same as returning nodes_y - nodes_x, but avoids overflow */
+        return (nodes_x < nodes_y) - (nodes_x > nodes_y);
 }
 
 STATIC int64_t