h48

A prototype for an optimal Rubik's cube solver, work in progress.
git clone https://git.tronto.net/h48
Download | Log | Files | Refs | README | LICENSE

expected_distributions.h (3017B)

      1 uint64_t expected_cocsep[21] = {
      2 	[0] = 1,
      3 	[1] = 6,
      4 	[2] = 63,
      5 	[3] = 468,
      6 	[4] = 3068,
      7 	[5] = 15438,
      8 	[6] = 53814,
      9 	[7] = 71352,
     10 	[8] = 8784,
     11 	[9] = 96
     12 };
     13 
     14 uint64_t expected_h48[12][9][21] = {
     15 	[0] = {
     16 		[2] = {
     17 			[0] = 5473562,
     18 			[1] = 34776317,
     19 			[2] = 68566704,
     20 			[3] = 8750867,
     21 		},
     22 		[4] = {
     23 			[0] = 1,
     24 			[1] = 1,
     25 			[2] = 4,
     26 			[3] = 34,
     27 			[4] = 331,
     28 			[5] = 3612,
     29 			[6] = 41605,
     30 			[7] = 474128,
     31 			[8] = 4953846,
     32 			[9] = 34776317,
     33 			[10] = 68566704,
     34 			[11] = 8749194,
     35 			[12] = 1673,
     36 		},
     37 	},
     38 	[1] = {
     39 		[2] = {
     40 			[0] = 6012079,
     41 			[1] = 45822302,
     42 			[2] = 142018732,
     43 			[3] = 41281787,
     44 		},
     45 	},
     46 	[2] = {
     47 		[2] = {
     48 			[0] = 6391286,
     49 			[1] = 55494785,
     50 			[2] = 252389935,
     51 			[3] = 155993794,
     52 		},
     53 	},
     54 	[3] = {
     55 		[2] = {
     56 			[0] = 6686828,
     57 			[1] = 63867852,
     58 			[2] = 392789689,
     59 			[3] = 477195231,
     60 		},
     61 
     62 	},
     63 	[4] = {
     64 		[2] = {
     65 			[0] = 77147213,
     66 			[1] = 543379415,
     67 			[2] = 1139570251,
     68 			[3] = 120982321,
     69 		},
     70 	},
     71 	[5] = {
     72 		[2] = {
     73 			[0] = 82471284,
     74 			[1] = 687850732,
     75 			[2] = 2345840746,
     76 			[3] = 645995638,
     77 		},
     78 	},
     79 	[6] = {
     80 		[2] = {
     81 			[0] = 85941099,
     82 			[1] = 804752968,
     83 			[2] = 4077248182,
     84 			[3] = 2556374551,
     85 		},
     86 	},
     87 	[7] = {
     88 		[2] = {
     89 			[0] = 88529761,
     90 			[1] = 897323475,
     91 			[2] = 6126260791,
     92 			[3] = 7936519573,
     93 		},
     94 	},
     95 	[8] = {
     96 		/* Unknown */
     97 		[2] = {0},
     98 	},
     99 	[9] = {
    100 		/* Unknown */
    101 		[2] = {0},
    102 	},
    103 	[10] = {
    104 		/* Unknown */
    105 		[2] = {0},
    106 	},
    107 	[11] = {
    108 		/* Unknown */
    109 		[2] = {0},
    110 	},
    111 };
    112 
    113 static bool
    114 distribution_equal(const uint64_t *expected, const uint64_t *actual, int n)
    115 {
    116 	bool equal;
    117 	int i;
    118 
    119 	for (i = 0, equal = true; i <= n; i++) {
    120 		if (expected[i] != actual[i]) {
    121 			equal = false;
    122 			printf("Wrong value for %d: expected %" PRIu64
    123 			    ", actual %" PRIu64 "\n",
    124 			    i, expected[i], actual[i]);
    125 		}
    126 	}
    127 
    128 	return equal;
    129 }
    130 
    131 static bool
    132 check_cocsep(uint64_t data_size, const void *data)
    133 {
    134 	tableinfo_t info;
    135 
    136 	readtableinfo(data_size, data, &info);
    137 	return distribution_equal(
    138 	    expected_cocsep, info.distribution, info.maxvalue);
    139 }
    140 
    141 static bool
    142 unknown_h48(uint8_t h, uint8_t k)
    143 {
    144 	if (k != 2 && k != 4)
    145 		return true;
    146 
    147 	if (k == 4 && h != 0)
    148 		return true;
    149 
    150 	return k == 2 && h > 7;
    151 }
    152 
    153 STATIC bool
    154 check_distribution(const char *solver, uint64_t data_size, const void *data)
    155 {
    156 	tableinfo_t info = {0};
    157 
    158 	if (!strncmp(solver, "h48", 3)) {
    159 		readtableinfo(data_size, data, &info);
    160 		if (!distribution_equal(
    161 		    expected_cocsep, info.distribution, info.maxvalue)) {
    162 			printf("ERROR! cocsep distribution is incorrect\n");
    163 			return false;
    164 		}
    165 		printf("cocsep distribution is correct\n");
    166 
    167 		readtableinfo_n(data_size, data, 2, &info);
    168 		if (unknown_h48(info.h48h, info.bits))
    169 			goto check_distribution_unknown;
    170 
    171 		if (!distribution_equal(expected_h48[info.h48h][info.bits],
    172 		    info.distribution, info.maxvalue)) {
    173 			printf("ERROR! h48 distribution is incorrect\n");
    174 			return false;
    175 		}
    176 
    177 		printf("h48 distribution is correct\n");
    178 		return true;
    179 	}
    180 
    181 check_distribution_unknown:
    182 	printf("Distribution unknown, not checked\n");
    183 	return true;
    184 }