Goldmine!

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Andrew Davie

From...Michael Folelman's Rush

Database Download
The database contains every "interesting" 6x6 Rush Hour puzzle with up to two walls. There are 2,577,412 puzzles in the database, covering 9,698,093,879 reachable states. Walls are lowercase x so you can easily grep them in or out as desired.

So, I can now select from 2.5 million levels!  And I don't need to spend mega-hours generating random ones :)

Bomberman94

Does the ,,databased" version still work offline - without PlusCart then?

Andrew Davie

Quote from: Bomberman94 on 16 Sep 2025, 06:47 PMDoes the ,,databased" version still work offline - without PlusCart then?

I would expect a few hundred selected levels in the offline version + an option to grab a random level from online.

Andrew Davie

#3
I've written a converter to take Michael's data format into C-structures for GridLock. Just two levels installed for this quick demo, but all working fine. I will next write a simple "grab n randomly selected levels from the 2.5 million data set" to generate fun binaries.

One new addition - I'd not realised this was a part of the game before now - there are now "walls" - a 1x1 un-moveable element placed on some boards. You have to manoeuvre cars around these. Obviously it makes it more difficult.

This binary demonstrates those walls, in the 2 levels it has installed. Image shows a "wall" at top right of the grid, and another in the left column.





Andrew Davie

#4
This version is now generated from Michael's 2.5 million level dataset. I choose a random 250 rooms, ordered by difficulty. There are also "walls" in this version, which do not move.

The move counter has CHANGED. It now counts moving a car as "1" regardless of how many squares you move that car in this part. If you move a different car and come back to this and move it, then we have +2 moves.

The nice thing having a huge dataset is now I just type "make puzzles" and I have a completely new 250 level set in about 1/2 second.  Also I'm not spending hours and hours (literally) hand-collating levels in order of difficulty from the (very very slow) random level generator -- which is now, by the way, redundant.

We can expect completely new 250 level sets in each version for the forseeable future - provided I remember to type "make puzzles" before releasing a new version.


Andrew Davie

The distribution of solution sizes in the 2.5M set is not even. That is, there are far more middle-difficulty puzzles than there are super-hard puzzles. If I choose randomly from the dataset, I don't get an evenly distributed random selection of puzzle sizes. Instead, I'm skewed.

The image from Michael's Solving Rush Hour, the Puzzle shows the distribution of solution-sizes to demonstrate the distribution.  So, what to do here?  I'm going to have to learn how to select evenly from this -- first thought is to bucket all the values into n buckets, and then choose one from each bucket randomly. That would work, but I might spend a little time thinking about a clean/efficient way to do this!


Andrew Davie

Note, the last version posted in this thread sorted levels by # cars (low to high), whereas I actually meant to sort by # car moves. The downloads section has an updated/correct version.

Andrew Davie

#7
The bucketing worked just fine, and although a bit slower it's still just 30 seconds or so to bin all 25000000 solutions into n buckets and then select one level from each bucket. Here's a 20-level bin which shows a nice distribution of difficulty.  Just start each level to see the # moves on the RHS for each level.

Actually -- save you the trouble -- it's the "D=" values in the puzzle pointer table below...

const puzzle_group puzzles[] = {
{puzzle151100,9}, // 0 D=7
{puzzle426320,11}, // 1 D=9
{puzzle821107,9}, // 2 D=10
{puzzle1533948,11}, // 3 D=13
{puzzle2045627,12}, // 4 D=16
{puzzle2238006,14}, // 5 D=18
{puzzle2333654,10}, // 6 D=19
{puzzle2490958,12}, // 7 D=22
{puzzle2524852,12}, // 8 D=24
{puzzle2548809,12}, // 9 D=26
{puzzle2568798,13}, // 10 D=30
{puzzle2571643,13}, // 11 D=32
{puzzle2573679,12}, // 12 D=33
{puzzle2575599,11}, // 13 D=36
{puzzle2576635,12}, // 14 D=38
{puzzle2576943,12}, // 15 D=40
{puzzle2577136,12}, // 16 D=42
{puzzle2577319,11}, // 17 D=45
{puzzle2577351,9}, // 18 D=47
{puzzle2577385,12}, // 19 D=49
{puzzle2577402,12}, // 20 D=53
{puzzle2577406,12}, // 21 D=54
{puzzle2577411,12}, // 22 D=60
};

Andrew Davie

#8
I re-thought the implementation of the bucketing. The new algorithm divides the total level pool (2.5M leels) into buckets; in fact there are at most 50 or so buckets because the maximum number of car-moves for any level is 60.  So, given (say) 50 buckets, how do we evenly choose n -- where n might be 100, or 250?  That is, more choices than buckets.  So we need to choose multiple items per bucket -- but on the other hand I want to get rid of that "normal" distribution so we get an even spread of difficulties.

And so... this is a complete hack, but it works. I first divide into n buckets (say *up to* 100 -- there may be less) according to number of car moves. Then I iterate:  find the bucket with the most entries. Remove a random one. Repeat until the total number of levels left is the required number of levels (i.e., 100).  This basically "flattens" that curve by removing stuff from the most-full bucket first.  It's an "ugly hack" I suppose, and takes about a minute. But it works really nicely. This tends to keep the rare/difficult levels while culling the common ones.

Here's a sample; look at the "D=" values for the difficulty spread...

const puzzle_group puzzles[] = {
    {puzzle10712, 6},    // 0 D=5
    {puzzle23462, 11},   // 1 D=6
    {puzzle97681, 11},   // 2 D=7
    {puzzle291168, 8},   // 3 D=8
    {puzzle352631, 11},  // 4 D=9
    {puzzle512948, 12},  // 5 D=9
    {puzzle756803, 10},  // 6 D=10
    {puzzle835391, 11},  // 7 D=10
    {puzzle934135, 12},  // 8 D=11
    {puzzle948579, 10},  // 9 D=11
    {puzzle1245134, 11}, // 10 D=12
    {puzzle1343567, 11}, // 11 D=12
    {puzzle1499207, 10}, // 12 D=13
    {puzzle1599055, 12}, // 13 D=13
    {puzzle1717792, 11}, // 14 D=14
    {puzzle1819599, 13}, // 15 D=14
    {puzzle1864504, 10}, // 16 D=15
    {puzzle1931839, 10}, // 17 D=15
    {puzzle2032864, 10}, // 18 D=16
    {puzzle2038342, 13}, // 19 D=16
    {puzzle2178660, 12}, // 20 D=17
    {puzzle2211876, 10}, // 21 D=17
    {puzzle2258818, 11}, // 22 D=18
    {puzzle2297061, 10}, // 23 D=18
    {puzzle2360970, 11}, // 24 D=19
    {puzzle2367090, 12}, // 25 D=19
    {puzzle2410805, 12}, // 26 D=20
    {puzzle2419301, 12}, // 27 D=20
    {puzzle2428447, 11}, // 28 D=21
    {puzzle2444166, 10}, // 29 D=21
    {puzzle2491406, 11}, // 30 D=22
    {puzzle2492000, 12}, // 31 D=22
    {puzzle2495105, 11}, // 32 D=23
    {puzzle2505579, 10}, // 33 D=23
    {puzzle2523827, 13}, // 34 D=24
    {puzzle2523879, 13}, // 35 D=24
    {puzzle2532579, 11}, // 36 D=25
    {puzzle2537152, 13}, // 37 D=25
    {puzzle2547938, 13}, // 38 D=26
    {puzzle2548170, 13}, // 39 D=26
    {puzzle2553858, 8},  // 40 D=27
    {puzzle2555658, 12}, // 41 D=27
    {puzzle2559901, 12}, // 42 D=28
    {puzzle2562977, 11}, // 43 D=28
    {puzzle2564010, 11}, // 44 D=29
    {puzzle2564302, 11}, // 45 D=29
    {puzzle2567355, 12}, // 46 D=30
    {puzzle2568269, 10}, // 47 D=30
    {puzzle2570228, 10}, // 48 D=31
    {puzzle2570477, 12}, // 49 D=31
    {puzzle2571722, 13}, // 50 D=32
    {puzzle2571994, 12}, // 51 D=32
    {puzzle2573646, 12}, // 52 D=33
    {puzzle2574000, 13}, // 53 D=33
    {puzzle2574488, 11}, // 54 D=34
    {puzzle2574861, 11}, // 55 D=34
    {puzzle2575071, 13}, // 56 D=35
    {puzzle2575315, 12}, // 57 D=35
    {puzzle2575595, 13}, // 58 D=36
    {puzzle2575857, 12}, // 59 D=36
    {puzzle2576098, 12}, // 60 D=37
    {puzzle2576163, 12}, // 61 D=37
    {puzzle2576446, 12}, // 62 D=38
    {puzzle2576485, 13}, // 63 D=38
    {puzzle2576718, 12}, // 64 D=39
    {puzzle2576814, 11}, // 65 D=39
    {puzzle2576902, 11}, // 66 D=40
    {puzzle2576941, 12}, // 67 D=40
    {puzzle2577058, 12}, // 68 D=41
    {puzzle2577085, 13}, // 69 D=41
    {puzzle2577115, 12}, // 70 D=42
    {puzzle2577134, 10}, // 71 D=42
    {puzzle2577184, 10}, // 72 D=43
    {puzzle2577238, 13}, // 73 D=43
    {puzzle2577254, 11}, // 74 D=44
    {puzzle2577276, 11}, // 75 D=44
    {puzzle2577316, 13}, // 76 D=45
    {puzzle2577325, 12}, // 77 D=45
    {puzzle2577331, 13}, // 78 D=46
    {puzzle2577343, 13}, // 79 D=46
    {puzzle2577350, 11}, // 80 D=47
    {puzzle2577358, 12}, // 81 D=47
    {puzzle2577367, 13}, // 82 D=48
    {puzzle2577371, 10}, // 83 D=48
    {puzzle2577381, 12}, // 84 D=49
    {puzzle2577385, 12}, // 85 D=49
    {puzzle2577391, 12}, // 86 D=50
    {puzzle2577396, 13}, // 87 D=50
    {puzzle2577397, 12}, // 88 D=51
    {puzzle2577398, 13}, // 89 D=51
    {puzzle2577399, 13}, // 90 D=52
    {puzzle2577400, 13}, // 91 D=52
    {puzzle2577401, 12}, // 92 D=53
    {puzzle2577402, 12}, // 93 D=53
    {puzzle2577404, 12}, // 94 D=54
    {puzzle2577407, 13}, // 95 D=54
    {puzzle2577408, 13}, // 96 D=55
    {puzzle2577409, 13}, // 97 D=55
    {puzzle2577410, 13}, // 98 D=58
    {puzzle2577411, 12}, // 99 D=60
};


Andrew Davie

Difficulty graduation is *chef's kiss*.
Here's a bit of a playthrough...