nissy-core

The "engine" of nissy, including the H48 optimal solver.
git clone https://git.tronto.net/nissy-core
Download | Log | Files | Refs | README | LICENSE

solve.h (18358B)


      1 #define H48_STARTING_MOVES 4
      2 
      3 #if H48_STARTING_MOVES == 3
      4 #define H48_STARTING_CUBES 3240 /* Number of 3-move sequences */
      5 #elif H48_STARTING_MOVES == 4
      6 #define H48_STARTING_CUBES 43254 /* Number of 4-move sequences */
      7 #endif
      8 
      9 #define H48_SORT_TASKS_MIN_DEPTH 16
     10 #define H48_LOG_PROGRESS_MIN_DEPTH 15
     11 
     12 typedef struct {
     13 	cube_t cube;
     14 	uint8_t moves[H48_STARTING_MOVES];
     15 	int64_t rank;
     16 } solve_h48_task_t;
     17 
     18 typedef struct {
     19 	cube_t start_cube;
     20 	cube_t cube;
     21 	cube_t inverse;
     22 	int8_t target_depth;
     23 	solution_moves_t *solution_moves;
     24 	solution_settings_t *solution_settings;
     25 	solution_list_t *solution_list;
     26 	int8_t lb_normal;
     27 	int8_t lb_inverse;
     28 	bool use_lb_normal;
     29 	bool use_lb_inverse;
     30 	uint8_t h;
     31 	uint8_t k;
     32 	uint8_t base;
     33 	const uint32_t *cocsepdata;
     34 	const unsigned char *h48data;
     35 	const unsigned char *h48data_fallback_h0k4;
     36 	const unsigned char *h48data_fallback_eoesep;
     37 	uint64_t movemask_normal;
     38 	uint64_t movemask_inverse;
     39 	int64_t nodes_visited;
     40 	int64_t table_fallbacks;
     41 	int64_t table_lookups;
     42 	int8_t threads;
     43 	int ntasks;
     44 	solve_h48_task_t *tasks;
     45 	int thread_id;
     46 	pthread_mutex_t *solutions_mutex;
     47 	_Atomic int *status;
     48 	_Atomic bool thread_done;
     49 } dfsarg_solve_h48_t;
     50 
     51 typedef struct {
     52 	cube_t cube;
     53 	int8_t nmoves;
     54 	uint8_t moves[H48_STARTING_MOVES];
     55 	int8_t minmoves;
     56 	int8_t maxmoves;
     57 	int8_t *shortest_sol;
     58 } dfsarg_solve_h48_maketasks_t;
     59 
     60 STATIC long long solve_h48_dispatch(oriented_cube_t, const char *, unsigned,
     61     unsigned, unsigned, unsigned, unsigned, unsigned, unsigned long long,
     62     const unsigned char *, unsigned, char *,
     63     long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *);
     64 STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t [static 1]);
     65 STATIC int64_t solve_h48_maketasks(
     66     dfsarg_solve_h48_t [static 1], dfsarg_solve_h48_maketasks_t [static 1],
     67     solve_h48_task_t [static H48_STARTING_CUBES], int [static 1]);
     68 STATIC void *solve_h48_runthread(void *);
     69 STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t [static 1]);
     70 STATIC void solve_h48_log_solutions(solution_list_t [static 1], size_t);
     71 STATIC int solve_h48_compare_tasks(const void *, const void *);
     72 STATIC int64_t solve_h48(oriented_cube_t, uint8_t, uint8_t, uint8_t, uint8_t,
     73     uint8_t, uint64_t, const unsigned char *, size_t, char *,
     74     long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *);
     75 
     76 STATIC long long solve_h48_dispatch(
     77 	oriented_cube_t oc,
     78         const char *solver,
     79         unsigned nissflag,
     80         unsigned minmoves,
     81         unsigned maxmoves,
     82         unsigned maxsols,
     83         unsigned optimal,
     84         unsigned threads,
     85         unsigned long long data_size,
     86         const unsigned char *data,
     87         unsigned sols_size,
     88         char *sols,
     89         long long stats[static NISSY_SIZE_SOLVE_STATS],
     90         int (*poll_status)(void *),
     91         void *poll_status_data
     92 )
     93 {
     94 	uint8_t h, k;
     95 	long long err;
     96 
     97 	err = parse_h48_hk(solver, &h, &k);
     98 	if (err != NISSY_OK)
     99 		return err;
    100 
    101 	return solve_h48(oc, minmoves, maxmoves, maxsols, optimal, threads,
    102 	    data_size, data, sols_size, sols, stats,
    103 	    poll_status, poll_status_data);
    104 }
    105 
    106 STATIC_INLINE bool
    107 solve_h48_stop(dfsarg_solve_h48_t arg[static 1])
    108 {
    109 	uint32_t data, data_inv;
    110 	int64_t coord;
    111 	int8_t target, nh, n;
    112 	uint8_t pval_cocsep, pval_eoesep;
    113 
    114 	n = arg->solution_moves->nmoves + arg->solution_moves->npremoves;
    115 	target = arg->target_depth - n;
    116 	if (target <= 0 ||
    117 	    arg->solution_list->nsols >= arg->solution_settings->maxsolutions ||
    118 	    n > arg->solution_list->shortest_sol +
    119 	        arg->solution_settings->optimal)
    120 		return true;
    121 
    122 	arg->movemask_normal = arg->movemask_inverse = MM18_ALLMOVES;
    123 	arg->nodes_visited++;
    124 
    125 	/* Preliminary probing using last computed bound, if possible */
    126 
    127 	if ((arg->use_lb_normal && arg->lb_normal > target) ||
    128 	    (arg->use_lb_inverse && arg->lb_inverse > target))
    129 		return true;
    130 
    131 	/* Preliminary corner probing */
    132 
    133 	if (get_h48_cdata(arg->cube, arg->cocsepdata, &data) > target ||
    134 	    get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv) > target)
    135 		return true;
    136 
    137 	/* Inverse probing */
    138 
    139 	if (!arg->use_lb_inverse) {
    140 		coord = coord_h48_edges(
    141 		    arg->inverse, COCLASS(data_inv), TTREP(data_inv), arg->h);
    142 		arg->lb_inverse = get_h48_pval(arg->h48data, coord, arg->k);
    143 		arg->table_lookups++;
    144 
    145 		if (arg->k == 2 && arg->lb_inverse == 0) {
    146 			arg->table_fallbacks++;
    147 
    148 			pval_cocsep = get_h48_pval(
    149 			    arg->h48data_fallback_h0k4, coord >> arg->h, 4);
    150 			pval_eoesep = get_eoesep_pval_cube(
    151 			    arg->h48data_fallback_eoesep, arg->inverse);
    152 			arg->lb_inverse = MAX(pval_cocsep, pval_eoesep);
    153 		} else {
    154 			arg->lb_inverse += arg->base;
    155 		}
    156 
    157 		arg->use_lb_inverse = true;
    158 	}
    159 
    160 	if (arg->lb_inverse > target)
    161 		return true;
    162 	nh = arg->lb_inverse == target;
    163 	arg->movemask_normal = nh * MM18_NOHALFTURNS + (1-nh) * MM18_ALLMOVES;
    164 
    165 	/* Normal probing */
    166 
    167 	if (!arg->use_lb_normal) {
    168 		coord = coord_h48_edges(
    169 		    arg->cube, COCLASS(data), TTREP(data), arg->h);
    170 		arg->lb_normal = get_h48_pval(arg->h48data, coord, arg->k);
    171 		arg->table_lookups++;
    172 
    173 		if (arg->k == 2 && arg->lb_normal == 0) {
    174 			arg->table_fallbacks++;
    175 
    176 			pval_cocsep = get_h48_pval(
    177 			    arg->h48data_fallback_h0k4, coord >> arg->h, 4);
    178 			pval_eoesep = get_eoesep_pval_cube(
    179 			    arg->h48data_fallback_eoesep, arg->cube);
    180 			arg->lb_normal = MAX(pval_cocsep, pval_eoesep);
    181 		} else {
    182 			arg->lb_normal += arg->base;
    183 		}
    184 
    185 		arg->use_lb_normal = true;
    186 	}
    187 
    188 	if (arg->lb_normal > target)
    189 		return true;
    190 	nh = arg->lb_normal == target;
    191 	arg->movemask_inverse = nh * MM18_NOHALFTURNS + (1-nh) * MM18_ALLMOVES;
    192 
    193 	return false;
    194 }
    195 
    196 STATIC int64_t
    197 solve_h48_dfs(dfsarg_solve_h48_t arg[static 1])
    198 {
    199 	int64_t ret, n;
    200 	uint8_t m, nm, lbn, lbi;
    201 	uint64_t mm_normal, mm_inverse;
    202 	bool ulbi, ulbn;
    203 	cube_t backup_cube, backup_inverse;
    204 
    205 	if (equal(arg->cube, SOLVED_CUBE)) {
    206 		nm = arg->solution_moves->nmoves
    207 		    + arg->solution_moves->npremoves;
    208 		if (arg->target_depth != nm)
    209 			return 0;
    210 		pthread_mutex_lock(arg->solutions_mutex);
    211 		ret = appendsolution(arg->solution_moves,
    212 		    arg->solution_settings, arg->solution_list);
    213 		pthread_mutex_unlock(arg->solutions_mutex);
    214 		return ret;
    215 	}
    216 
    217 	if (solve_h48_stop(arg))
    218 		return 0;
    219 
    220 	backup_cube = arg->cube;
    221 	backup_inverse = arg->inverse;
    222 	lbn = arg->lb_normal;
    223 	lbi = arg->lb_inverse;
    224 	ulbn = arg->use_lb_normal;
    225 	ulbi = arg->use_lb_inverse;
    226 
    227 	ret = 0;
    228 	mm_normal = arg->movemask_normal;
    229 	if (arg->solution_moves->nmoves > 0) {
    230 		m = arg->solution_moves->moves[arg->solution_moves->nmoves-1];
    231 		mm_normal &= allowedmask[movebase(m)];
    232 	}
    233 	mm_inverse = arg->movemask_inverse;
    234 	if (arg->solution_moves->npremoves > 0) {
    235 		m = arg->solution_moves->premoves[arg->solution_moves->npremoves-1];
    236 		mm_inverse &= allowedmask[movebase(m)];
    237 	}
    238 	if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) {
    239 		arg->solution_moves->nmoves++;
    240 		for (m = 0; m < 18; m++) {
    241 			if (!(mm_normal & MM_SINGLE(m)))
    242 				continue;
    243 			arg->solution_moves->moves[
    244 			    arg->solution_moves->nmoves-1] = m;
    245 			arg->cube = move(backup_cube, m);
    246 			arg->inverse = premove(backup_inverse, m);
    247 			arg->lb_inverse = lbi;
    248 			arg->use_lb_normal = false;
    249 			arg->use_lb_inverse = ulbi && m % 3 == 1;
    250 			n = solve_h48_dfs(arg);
    251 			if (n < 0)
    252 				return n;
    253 			ret += n;
    254 		}
    255 		arg->solution_moves->nmoves--;
    256 	} else {
    257 		arg->solution_moves->npremoves++;
    258 		for (m = 0; m < 18; m++) {
    259 			if(!(mm_inverse & MM_SINGLE(m)))
    260 				continue;
    261 			arg->solution_moves->premoves[
    262 			    arg->solution_moves->npremoves-1] = m;
    263 			arg->inverse = move(backup_inverse, m);
    264 			arg->cube = premove(backup_cube, m);
    265 			arg->lb_normal = lbn;
    266 			arg->use_lb_inverse = false;
    267 			arg->use_lb_normal = ulbn && m % 3 == 1;
    268 			n = solve_h48_dfs(arg);
    269 			if (n < 0)
    270 				return n;
    271 			ret += n;
    272 		}
    273 		arg->solution_moves->npremoves--;
    274 	}
    275 
    276 	arg->cube = backup_cube;
    277 	arg->inverse = backup_inverse;
    278 
    279 	return ret;
    280 }
    281 
    282 STATIC void *
    283 solve_h48_runthread(void *arg)
    284 {
    285 	int i, j;
    286 	uint8_t lastmove;
    287 	int64_t nprev;
    288 	dfsarg_solve_h48_t *dfsarg;
    289 
    290 	dfsarg = (dfsarg_solve_h48_t *)arg;
    291 
    292 	nprev = 0;
    293 	for (i = dfsarg->thread_id; i < dfsarg->ntasks; i += dfsarg->threads) {
    294 		if (*dfsarg->status == NISSY_STATUS_STOP)
    295 			goto solve_h48_runthread_end;
    296 		while (*dfsarg->status == NISSY_STATUS_PAUSE)
    297 			msleep(BASE_SLEEP_TIME);
    298 
    299 		solution_moves_reset(dfsarg->solution_moves);
    300 		memcpy(dfsarg->solution_moves->moves,
    301 		    dfsarg->tasks[i].moves, H48_STARTING_MOVES);
    302 		dfsarg->solution_moves->nmoves = H48_STARTING_MOVES;
    303 
    304 		dfsarg->cube = dfsarg->start_cube;
    305 		for (j = 0; j < H48_STARTING_MOVES; j++)
    306 			dfsarg->cube =
    307 			   move(dfsarg->cube, dfsarg->tasks[i].moves[j]);
    308 		dfsarg->inverse = inverse(dfsarg->cube);
    309 
    310 		dfsarg->lb_normal = 0;
    311 		dfsarg->lb_inverse = 0;
    312 		dfsarg->use_lb_normal = false;
    313 		dfsarg->use_lb_inverse = false;
    314 		dfsarg->movemask_normal = MM18_ALLMOVES;
    315 		dfsarg->movemask_inverse = MM18_ALLMOVES;
    316 
    317 		solve_h48_dfs(dfsarg);
    318 
    319 		/*
    320 		We compute the "rank" of each taks, which is used in the next
    321 		step of the IDFS to sort them. This heuristically leads us
    322 		faster to a solution.  The rank is computed by taking the
    323 		number of nodes visited, adjusted by a factor of about
    324 		sqrt(2)/sqrt(3) because there are more sequences starting with
    325 		U, R and F than with D, L and B, as we don't allow e.g. both
    326 		U D and D U, but only U D.
    327 		This trick was suggested by Chen Shuang, the implementation is
    328 		inspired by Andrew Skalski's vcube.
    329 		*/
    330 		lastmove = dfsarg->tasks[i].moves[H48_STARTING_MOVES-1];
    331 		dfsarg->tasks[i].rank = (dfsarg->nodes_visited - nprev) *
    332 		    (movebase(lastmove) % 2 == 0 ? 47525 : 58206);
    333 		nprev = dfsarg->nodes_visited;
    334 	}
    335 
    336 solve_h48_runthread_end:
    337 	dfsarg->thread_done = true;
    338 	return NULL;
    339 }
    340 
    341 STATIC int64_t
    342 solve_h48_maketasks(
    343 	dfsarg_solve_h48_t solve_arg[static 1],
    344 	dfsarg_solve_h48_maketasks_t maketasks_arg[static 1],
    345 	solve_h48_task_t tasks[static H48_STARTING_CUBES],
    346 	int ntasks[static 1]
    347 )
    348 {
    349 	int r;
    350 	int64_t appret;
    351 	uint8_t m, t;
    352 	uint64_t mm;
    353 	cube_t backup_cube;
    354 	solution_moves_t moves;
    355 
    356 	if (equal(maketasks_arg->cube, SOLVED_CUBE)) {
    357 		if (maketasks_arg->nmoves > maketasks_arg->maxmoves ||
    358 		    maketasks_arg->nmoves < maketasks_arg->minmoves ||
    359 		    solutions_done(solve_arg->solution_list,
    360 		        solve_arg->solution_settings, maketasks_arg->nmoves))
    361 			return NISSY_OK;
    362 
    363 		solution_moves_reset(&moves);
    364 		moves.nmoves = maketasks_arg->nmoves;
    365 		memcpy(moves.moves,
    366 		    maketasks_arg->moves, maketasks_arg->nmoves);
    367 
    368 		appret = appendsolution(&moves, solve_arg->solution_settings,
    369 		    solve_arg->solution_list);
    370 		return appret < 0 ? appret : NISSY_OK;
    371 	}
    372 
    373 	if (maketasks_arg->nmoves == H48_STARTING_MOVES) {
    374 		tasks[*ntasks].cube = maketasks_arg->cube;
    375 		memcpy(tasks[*ntasks].moves,
    376 		    maketasks_arg->moves, H48_STARTING_MOVES);
    377 		(*ntasks)++;
    378 		return NISSY_OK;
    379 	}
    380 
    381 	if (maketasks_arg->nmoves == 0) {
    382 		mm = MM18_ALLMOVES;
    383 	} else {
    384 		m = maketasks_arg->moves[maketasks_arg->nmoves-1];
    385 		mm = allowedmask[movebase(m)];
    386 	}
    387 
    388 	maketasks_arg->nmoves++;
    389 	backup_cube = maketasks_arg->cube;
    390 	for (m = 0; m < 18; m++) {
    391 		if (!(mm & MM_SINGLE(m)))
    392 			continue;
    393 		maketasks_arg->moves[maketasks_arg->nmoves-1] = m;
    394 		maketasks_arg->cube = move(backup_cube, m);
    395 		r = solve_h48_maketasks(
    396 		    solve_arg, maketasks_arg, tasks, ntasks);
    397 		if (r < 0)
    398 			return r;
    399 
    400 		/* Avoid symmetry-equivalent moves from the starting cube */
    401 		if (maketasks_arg->nmoves == 1)
    402 			for (t = 0; t < NTRANS; t++)
    403 				if (solve_arg->solution_settings->tmask &
    404 				    TM_SINGLE(t))
    405 					mm &= ~MM_SINGLE(transform_move(m, t));
    406 	}
    407 	maketasks_arg->nmoves--;
    408 	maketasks_arg->cube = backup_cube;
    409 
    410 	return NISSY_OK;
    411 }
    412 
    413 STATIC void
    414 solve_h48_log_solutions(solution_list_t s[static 1], size_t e)
    415 {
    416 	size_t i;
    417 	char b;
    418 	while (e != s->used) {
    419 		LOG("[h48 solve] Found solution: ");
    420 		for (i = e; s->buf[i] != '\n' && s->buf[i] != '\0'; i++) ;
    421 		b = s->buf[i];
    422 		s->buf[i] = '\0';
    423 		LOG("%s\n", s->buf + e);
    424 		s->buf[i] = b;
    425 		e = i + 1;
    426 	}
    427 }
    428 
    429 STATIC int
    430 solve_h48_compare_tasks(const void *x, const void *y)
    431 {
    432 	int64_t nodes_x = ((solve_h48_task_t *)x)->rank;
    433 	int64_t nodes_y = ((solve_h48_task_t *)y)->rank;
    434 
    435 	/* Same as returning nodes_y - nodes_x, but avoids overflow */
    436 	return (nodes_x < nodes_y) - (nodes_x > nodes_y);
    437 }
    438 
    439 STATIC int64_t
    440 solve_h48(
    441 	oriented_cube_t oc,
    442 	uint8_t minmoves,
    443 	uint8_t maxmoves,
    444 	uint8_t maxsolutions,
    445 	uint8_t optimal,
    446 	uint8_t threads,
    447 	uint64_t data_size,
    448 	const unsigned char *data,
    449 	size_t solutions_size,
    450 	char *solutions,
    451 	long long stats[static NISSY_SIZE_SOLVE_STATS],
    452 	int (*poll_status)(void *),
    453 	void *poll_status_data
    454 )
    455 {
    456 	int i, ntasks, eoesep_table_index;
    457 	bool td;
    458 	_Atomic int status, prev_status;
    459 	size_t lastused;
    460 	int8_t d;
    461 	dfsarg_solve_h48_t arg[THREADS];
    462 	solve_h48_task_t tasks[H48_STARTING_CUBES];
    463 	dfsarg_solve_h48_maketasks_t maketasks_arg;
    464 	long double fallback_rate, lookups_per_node;
    465 	uint64_t offset;
    466 	int64_t nodes_visited, table_lookups, table_fallbacks;
    467 	tableinfo_t info, fbinfo, fbinfo2;
    468 	const uint32_t *cocsepdata;
    469 	const unsigned char *fallback, *h48data;
    470 	const unsigned char *fallback2;
    471 	solution_moves_t solution_moves[THREADS];
    472 	solution_settings_t settings;
    473 	solution_list_t sollist;
    474 	pthread_t thread[THREADS];
    475 	pthread_mutex_t solutions_mutex;
    476 
    477 	if (!solution_list_init(&sollist, solutions_size, solutions))
    478 		goto solve_h48_error_solutions_buffer;
    479 
    480 	if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
    481 		goto solve_h48_error_data;
    482 
    483 	cocsepdata = (uint32_t *)(data + INFOSIZE);
    484 	h48data = data + COCSEP_FULLSIZE + INFOSIZE;
    485 
    486 	/* Read fallback table(s) */
    487 	fallback = NULL;
    488 	if (readtableinfo_n(data_size, data, 3, &fbinfo) != NISSY_OK)
    489 		goto solve_h48_error_data;
    490 	offset = info.next;
    491 	eoesep_table_index = 3;
    492 	if (info.bits == 2) {
    493 		/* We only support h0k4 as fallback table */
    494 		if (fbinfo.h48h != 0 || fbinfo.bits != 4)
    495 			goto solve_h48_error_data;
    496 		fallback = h48data + offset;
    497 		offset += fbinfo.next;
    498 		eoesep_table_index++;
    499 	}
    500 
    501 	if (readtableinfo_n(data_size, data, eoesep_table_index, &fbinfo2)
    502 	    != NISSY_OK)
    503 		goto solve_h48_error_data;
    504 
    505 	/* Some heuristic check to see that it is eoesep */
    506 	if (fbinfo2.bits != 4 || fbinfo2.type != TABLETYPE_SPECIAL)
    507 		goto solve_h48_error_data;
    508 	fallback2 = h48data + offset;
    509 
    510 	settings = (solution_settings_t) {
    511 		.tmask = symmetry_mask(oc.cube),
    512 		.unniss = true,
    513 		.maxmoves = maxmoves,
    514 		.maxsolutions = maxsolutions,
    515 		.optimal = optimal,
    516 		.orientation = oc.orientation,
    517 	};
    518 
    519 	for (i = 0; i < threads; i++) {
    520 		arg[i] = (dfsarg_solve_h48_t) {
    521 			.start_cube = oc.cube,
    522 			.cube = oc.cube,
    523 			.h = info.h48h,
    524 			.k = info.bits,
    525 			.base = info.base,
    526 			.cocsepdata = cocsepdata,
    527 			.h48data = h48data,
    528 			.h48data_fallback_h0k4 = fallback,
    529 			.h48data_fallback_eoesep = fallback2,
    530 			.solution_moves = &solution_moves[i],
    531 			.solution_settings = &settings,
    532 			.solution_list = &sollist,
    533 			.nodes_visited = 0,
    534 			.table_fallbacks = 0,
    535 			.table_lookups = 0,
    536 			.threads = threads,
    537 			.thread_id = i,
    538 			.solutions_mutex = &solutions_mutex,
    539 			.status = &status,
    540 		};
    541 
    542 	}
    543 
    544 	pthread_mutex_init(&solutions_mutex, NULL);
    545 
    546 	maketasks_arg = (dfsarg_solve_h48_maketasks_t) {
    547 		.cube = oc.cube,
    548 		.nmoves = 0,
    549 		.minmoves = minmoves,
    550 		.maxmoves = maxmoves,
    551 	};
    552 	ntasks = 0;
    553 	solve_h48_maketasks(&arg[0], &maketasks_arg, tasks, &ntasks);
    554 	if (ntasks < 0)
    555 		goto solve_h48_error_solutions_buffer;
    556 	if (solutions_done(&sollist, &settings,
    557 	    MAX(minmoves, H48_STARTING_MOVES)))
    558 		goto solve_h48_done;
    559 
    560 	for (i = 0; i < threads; i++) {
    561 		arg[i].ntasks = ntasks;
    562 		arg[i].tasks = tasks;
    563 	}
    564 
    565 	LOG("[H48 solve] Prepared %d tasks\n", ntasks);
    566 
    567 	solve_h48_log_solutions(&sollist, 0);
    568 	lastused = sollist.used;
    569 	status = poll_status == NULL ? NISSY_STATUS_RUN :
    570 	    poll_status(poll_status_data);
    571 	if (!NISSY_CANSLEEP) {
    572 		LOG("[solve h48] Pause / Stop / Resume functionality won't "
    573 		    "be available on this system (can't sleep()).\n");
    574 	}
    575 	for (
    576 	    d = MAX(minmoves, H48_STARTING_MOVES + 1);
    577 	    !(solutions_done(&sollist, &settings, d)) &&
    578 	        status != NISSY_STATUS_STOP;
    579 	    d++
    580 	) {
    581 		if (d >= H48_LOG_PROGRESS_MIN_DEPTH) {
    582 			LOG("[H48 solve] Found %" PRId64 " solutions, "
    583 			    "searching at depth %" PRId8 "\n",
    584 			    sollist.nsols, d);
    585 		}
    586 
    587 		if (d >= H48_SORT_TASKS_MIN_DEPTH)
    588 			qsort(tasks, ntasks, sizeof(solve_h48_task_t),
    589 			    solve_h48_compare_tasks);
    590 
    591 		for (i = 0; i < threads; i++) {
    592 			arg[i].target_depth = d;
    593 			arg[i].thread_done = false;
    594 			pthread_create(
    595 			    &thread[i], NULL, solve_h48_runthread, &arg[i]);
    596 		}
    597 
    598 		/* Log solutions and handle pause / stop / resume */
    599 		if (poll_status != NULL && d >= 15 && NISSY_CANSLEEP) {
    600 			td = false;
    601 			while (!td && status != NISSY_STATUS_STOP) {
    602 				msleep(BASE_SLEEP_TIME);
    603 
    604 				pthread_mutex_lock(&solutions_mutex);
    605 				solve_h48_log_solutions(&sollist, lastused);
    606 				lastused = sollist.used;
    607 				pthread_mutex_unlock(&solutions_mutex);
    608 
    609 				prev_status = status;
    610 				status = poll_status(poll_status_data);
    611 				if (status != prev_status) {
    612 					if (status == NISSY_STATUS_PAUSE)
    613 						LOG("[H48 solve] Paused\n");
    614 					if (status == NISSY_STATUS_RUN)
    615 						LOG("[H48 solve] Resumed\n");
    616 				}
    617 
    618 				for (td = true, i = 0; i < threads; i++)
    619 					td = td && arg[i].thread_done;
    620 			}
    621 		}
    622 
    623 		for (i = 0; i < threads; i++)
    624 			pthread_join(thread[i], NULL);
    625 
    626 		solve_h48_log_solutions(&sollist, lastused);
    627 		lastused = sollist.used;
    628 	}
    629 
    630 	if (status == NISSY_STATUS_STOP) {
    631 		LOG("[H48 solve] Received stop request, ending solution "
    632 		    "search early.\n");
    633 	}
    634 
    635 solve_h48_done:
    636 	nodes_visited = table_lookups = table_fallbacks = 0;
    637 	for (i = 0; i < threads; i++) {
    638 		nodes_visited += arg[i].nodes_visited;
    639 		table_fallbacks += arg[i].table_fallbacks;
    640 		table_lookups += arg[i].table_lookups;
    641 	}
    642 
    643 	stats[0] = nodes_visited;
    644 	stats[1] = table_lookups;
    645 	stats[2] = table_fallbacks;
    646 	lookups_per_node = table_lookups / (long double)nodes_visited;
    647 	fallback_rate = nodes_visited == 0 ? 0.0 :
    648 	    (table_fallbacks * 100) / (long double)table_lookups;
    649 	LOG("[H48 solve] Nodes visited: %" PRId64 "\n", nodes_visited);
    650 	LOG("[H48 solve] Lookups: %" PRId64 " (%.3Lf per node)\n",
    651 	    table_lookups, lookups_per_node);
    652 	LOG("[H48 solve] Table fallbacks: %" PRId64 " (%.3Lf%%)\n",
    653 	    table_fallbacks, fallback_rate);
    654 
    655 	return sollist.nsols;
    656 
    657 solve_h48_error_data:
    658 	LOG("[H48 solve] Error reading data table\n");
    659 	return NISSY_ERROR_DATA;
    660 
    661 solve_h48_error_solutions_buffer:
    662 	return NISSY_ERROR_BUFFER_SIZE;
    663 }