// allgames: generate all possible solvable Unblockme games. // Compile with: // cc -Wall -g -O -o allgames allgames.c // cc -Wall -g -O -o allgames -fopenmp allgames.c (omp support not yet integrated - work in progress) // All results (including trivial layouts) are logged to unblockme-games.txt in addition to // the more interesting problems (defined by length) being displayed on screen. Aborted runs // can be restarted using some extra information that is also recorded in that file. // While running, you can keep track of progress by issuing this in another window: // watch -n 4 "grep ^[1-9][0-9] unblockme-games.txt|sort -n|tail -33|tac" // This code is capable of enumerating all possible Unblockme layouts and // determining whether they are solvable, and if so, how many moves are // required. However an exhaustive list is not particularly valuable, and // there are settings below which can be used to reduce the number of // layouts which are output. For now the main reduction comes from not // looking at layouts which have very few blocks in them, because these // are always trivial to solve. We also eliminate layouts where the // target block can be immediately extracted without moving any other blocks. // The convention I have used for representing the board is that the target // block is represented as 'XX' or 'XXX' and all the other blocks as A through Y. // (even with 2-square blocks the most tiles that can be fitted are 3*6=18 so // that range of letters is guaranteed to be sufficient). // Y and Z are kept in reserve for use as two 1-square immovable blocking tiles. // This code does not use those as my Vectrex game does not implement that // extenstion to the basic game. Neither does my 3D-printed physical game. #include #include #include #include #ifdef _OPENMP // if compiling with -fopenmp #include #endif #ifndef TRUE #define TRUE (0==0) #define FALSE (0!=0) #endif #define MIN_STEPS 10 // Don't print problems that are too easy on the console. But log them to file anyway. #define REJECT_SUBSETS TRUE // Reject any solutions which contains blocks that never move. (not yet implemented) /* How this program came about: this was my second attempt at a problem generator - the first version tried to create random problems and although it worked, it only found a few medium-difficulty solutions and took days to do so. Until... One of my University lecturers, Rod Burstall, once told my class "If you can't think of an algorithm to solve a problem, try thinking of a harder problem and solve that instead.". This became known as "Rod Burstall's Insane Heuristic" and despite sounding crazy has indeed come in useful a few times over the years. It came in useful again today, while working on generating Unblockme problems. Since finding a few 'interesting' (i.e. many steps and therefore harder to solve) layouts at random was proving difficult, I tried applying Rod's heuristic and decided to find *all* possible unblockme layouts! It turns out that this is an easier problem, and once solved, it is trivial to modify the program to produce a single random layout of specified difficulty in a relatively short time. */ #define iround(x) ((int)(0.5+(x))) // avoids having to link with -lm. Only ever used for on-screen diags. //============================================================================ //=========== This block contains the code to evaluate a layout ============= #include // sleep() #include // isprint() #include #include #define UP 0 #define LEFT 0 #define DOWN 1 #define RIGHT 1 #define NUM_ROWS 6 #define NUM_COLS 6 /* The current state is represented by a 36-character string. Using bitmaps is no faster and space is not an issue. Keep it simple. Note that we store both the board layout *and* the solving solution in the same string within the solver. They are separated by a space when a solution is present, or the 36-character board is terminated by a '\0' is no solution is present. Programmers, be careful never to add a solution to a read-only parameter or to any array that is only declared as 6*6+1 bytes! When solving, a sequences of moves is recorded as so: * We generate only 1-space moves. More than one space will be recorded as multiple 1-space moves but will be counted as a single move when reporting moves used. * because each block can only move in one axis, the move is recorded as the upper case letter for a positive move and a lower case letter for a negative move. (Positive and negative being in relation to the coordinate system used - positive X is to the right and positive y is downwards.) * When breadth-first solving a problem, a history is kept and the new position is not added to the queue if it has been seen before. * the history of how we got to this state is always valid and back-tracking is done simply by removing the last character from the 'history' string. */ #define MAX_POSITIONS 65536 /* Use 32768 if 64K is too much RAM for your system */ #define MAX_MOVES 128 /* Probably 64 would be large enough but 128 is definitely safe. */ #define BOARD_SIZE (NUM_ROWS*NUM_COLS+1 + MAX_MOVES+1) // Room for 6x6 board and move history */ //------------------------------------------------------------------------------------ //--------------- Code to check if a state has been seen previously ------------------ // Originally I used a rather dumb but bullet-proof linear scan of an array // to store previously-seen states. However replacing that code with the // trie-based code below (which was rather tricky to get right!) speeded up // the runtime from several hours to just under one hour! (and that was on // a single core of a very old i686 - which means I should be able to get the // runtime down to about 15 minutes by using all 4 cores, or even 5 minutes if // I use my half dozen pi 4's and 5's :-) // Trie data structure: // 0 1 2 3 4 // a -> b -> c -> d -> e ---> Subsequent_Letters // | | // V | // x -> y -> z V // 5 6 7 Next_Alternative_Letter // Use indexes rather than pointers and a large fixed-size static blob for speed // (which is much faster than using the heap because we have no need for rapid reuse.) #define MAXTRIES (512*1024) // This was determined by trial and error! static char Letter[MAXTRIES]; static int Next_Letter[MAXTRIES]; static int Alternative_Letter[MAXTRIES]; static int LastTrie = -1; // Inclusive index. static inline void reset_seen_table(void) { LastTrie = -1; } // Probably a bit verbose but it worked so I'll stick with it. static int TrieMatch(int Trie, char *p) { if (*p <= ' ') return TRUE; // Matched up to end of string. All strings same length in this program. if (LastTrie < 0 || Trie < 0) return FALSE; if (Letter[Trie] == *p) return TrieMatch(Next_Letter[Trie], ++p); return TrieMatch(Alternative_Letter[Trie], p); } static int NewTrie(char *p) { int ThisTrie; if (*p <= ' ') return -1; LastTrie += 1; if (LastTrie == MAXTRIES) { fprintf(stderr, "ERR %d\n", __LINE__); exit(1); } ThisTrie = LastTrie; Alternative_Letter[ThisTrie] = -1; Letter[ThisTrie] = *p; Next_Letter[ThisTrie] = NewTrie(++p); return ThisTrie; } static void AddToTrie(int Trie, char *p) { if (*p <= ' ') return; // Fully added. for (;;) { // First character already in Trie: if (Letter[Trie] == *p) { if (Next_Letter[Trie] < 0) { Next_Letter[Trie] = NewTrie(++p); return; } else { AddToTrie(Next_Letter[Trie], ++p); return; } } // No more alternative letters remaining to be checked? if (Alternative_Letter[Trie] < 0) { Alternative_Letter[Trie] = NewTrie(p); return; } Trie = Alternative_Letter[Trie]; // Check next alternative letter. } } static int Seen(char *p) { // Combined check and add // For this program, all strings are expected to be the same length. if (*p <= ' ') { return FALSE; } else if (LastTrie < 0) { (void)NewTrie(p); // will return 0. return FALSE; } else if (TrieMatch(0, p)) { return TRUE; } else { AddToTrie(0, p); return FALSE; } } //----------- End of code to check if a state has been seen previously --------------- //------------------------------------------------------------------------------------ static int queue_put = 0, queue_get = MAX_POSITIONS-1; static char queue[MAX_POSITIONS][BOARD_SIZE]; static int One_Step(char *p, int c, int dir) { // Move one step int i, j, success; success = FALSE; if (c != '.') for (j = 0; j < 6; j++) { // top to bottom for (i = 0; i < 6; i++) { // left to right if (p[j*6+i] == c) { // first one it hits, topmost or leftmost if ((i < 4) && (p[j*6+i+2] == c)) { // left of horizontal triple if ((dir==LEFT) && (i > 0) && (p[j*6+i-1] == '.')) { // horizontal triple move left p[j*6+i-1] = c; p[j*6+i+2] = '.'; success = TRUE; } else if ((dir==RIGHT) && (i < 3) && (p[j*6+i+3] == '.')) { // horizontal triple move right p[j*6+i+3] = c; p[j*6+i] = '.'; success = TRUE; } } else if ((i < 5) && (p[j*6+i+1] == c)) { // left of horizontal pair if ((dir==LEFT) && (i > 0) && (p[j*6+i-1] == '.')) { // horizontal pair move left p[j*6+i-1] = c; p[j*6+i+1] = '.'; success = TRUE; } else if ((dir==RIGHT) && (i < 4) && (p[j*6+i+2] == '.')) { // horizontal pair move right p[j*6+i+2] = c; p[j*6+i] = '.'; success = TRUE; } } if ((j < 4) && (p[(j+2)*6+i] == c)) { // top of vertical triple if ((dir==UP) && (j > 0) && (p[(j-1)*6+i] == '.')) { // vertical triple move up p[(j-1)*6+i] = c; p[(j+2)*6+i] = '.'; success = TRUE; } else if ((dir==DOWN) && (j < 3) && (p[(j+3)*6+i] == '.')) { // vertical triple down p[(j+3)*6+i] = c; p[j*6+i] = '.'; success = TRUE; } } else if ((j < 5) && (p[(j+1)*6+i] == c)) { // top of vertical pair if ((dir==UP) && (j > 0) && (p[(j-1)*6+i] == '.')) { // vertical pair move up p[(j-1)*6+i] = c; p[(j+1)*6+i] = '.'; success = TRUE; } else if ((dir==DOWN) && (j < 4) && (p[(j+2)*6+i] == '.')) { // vertical pair down p[(j+2)*6+i] = c; p[j*6+i] = '.'; success = TRUE; } } return success; } } } return success; } static int longest_sequence = 0; static void enqueue(char *p, char code) { // put next state into breadth-first search queue int len; len = strlen(p); if (len > longest_sequence) longest_sequence = len; if (len >= NUM_ROWS*NUM_COLS + MAX_MOVES) { fprintf(stderr, "Too many moves to store in queued string: \"%s\" + '%c'\n\n", p, code); exit(EXIT_FAILURE); } strcpy(queue[queue_put], p); queue[queue_put][len] = code; len += 1; queue[queue_put][len] = '\0'; // Save the last move along with the updated board state queue_put = (queue_put+1) % MAX_POSITIONS; if (queue_put == queue_get) { fprintf(stderr, "Queue full! put/get = %d\n", queue_put); exit(EXIT_FAILURE); } } static int dequeue(char *p) { // get next state from breadth-first search queue queue_get = (queue_get+1) % MAX_POSITIONS; if (queue_get == queue_put) return FALSE; strcpy(p, queue[queue_get]); return TRUE; } static inline int solved(char *p) { return ((p[2*6+4] == 'X') && (p[2*6+5] == 'X')); } static int solve(char *p) { int block, code, dir; char saved[BOARD_SIZE]; strcpy(saved, p); if (One_Step(p, 'X', 0)) { if (solved(p)) { int len = strlen(p); p[len] = 'x'; len += 1; p[len] = '\0'; // Save the final move along with the updated board state return TRUE; } else if (!Seen(p)) { enqueue(p, 'x'); } } strcpy(p, saved); if (One_Step(p, 'X', 1)) { if (solved(p)) { int len = strlen(p); p[len] = 'X'; len += 1; p[len] = '\0'; // Save the final move along with the updated board state return TRUE; } else if (!Seen(p)) { enqueue(p, 'X'); } } for (dir = 0; dir <= 1; dir++) { // dir==0: UP,LEFT dir==1: DOWN,RIGHT for (block = 'A'; block <= 'X'; block++) { strcpy(p, saved); code = block; if (dir == 0) code = tolower(code); if (One_Step(p, block, dir)) { if (solved(p)) { int len = strlen(p); p[len] = code; len += 1; p[len] = '\0'; // Save the final move along with the updated board state return TRUE; } else if (!Seen(p)) { enqueue(p, code); } } } } return FALSE; } int count_canonical_steps(char *s) { // Consider two immediately-consecutive moves of a block as a single step int steps = 0, last = 0; while (*s != '\0') { if (*s != last) steps++; last = *s++; } return steps-1; // subtract X's at end of string in accounting for number of steps. } int solvable(char *p, int *steps) { // If p is solved, it should be updated with the final solution and the path to get there. reset_seen_table(); queue_put = 0; queue_get = MAX_POSITIONS-1; longest_sequence = 0; enqueue(p, ' '); while (dequeue(p)) { if (solve(p)) { *steps = count_canonical_steps(&p[NUM_ROWS*NUM_COLS+1]); return TRUE; } } return FALSE; } //========= End of block containing the code to evaluate a layout =========== //============================================================================ // When enumerating potential board positions, only a few options are possible // on each empty row, being constrained by the block length and game rules. // Allowed forms for columns, and all rows except exit row: /* (replace below with one of [01345] - there are 5 nested loops to replace...) Previously, we were looping as so: for (hoption = init_option; hoption < a; hoption++) { ... } In this rewrite, we do: for (shape = 0; shape < shape_count; shape++) { for (hoption = hshape01345_first[shape]; hoption < hshape01345_last[shape]; hoption++) { ... } } */ const int hshape01345_count = 6; const int hshape01345_first[6] = {0, 3, 6, 12, 16, 21}; // inclusive const int hshape01345_last[6] = {3, 6, 12, 16, 21, 22}; // exclusive const char *hoptions01345[] = { // shape pos idx "AAABB.", // 0: AAA BB 0 0 "AAA.BB", // 1 1 ".AAABB", // 2 2 "AABBB.", // 1: AA BBB 0 3 "AA.BBB", // 1 4 ".AABBB", // 2 5 "AABB..", // 2: AA BB 0 6 "AA.BB.", // 1 7 "AA..BB", // 2 8 ".AABB.", // 3 9 ".AA.BB", // 4 10 "..AABB", // 5 11 "AAA...", // 3: AAA 0 12 ".AAA..", // 1 13 "..AAA.", // 2 14 "...AAA", // 3 15 "AA....", // 4: AA 0 16 ".AA...", // 1 17 "..AA..", // 2 18 "...AA.", // 3 19 "....AA", // 4 20 "......", // 5: 0 21 }; const int vshape0123_count = 6; const int vshape0123_first[6] = {0, 3, 6, 12, 16, 21}; // inclusive const int vshape0123_last[6] = {3, 6, 12, 16, 21, 22}; // exclusive const char *voptions0123[] = { // shape pos idx "AAABB.", // 0: AAA BB 0 0 "AAA.BB", // 1 1 ".AAABB", // 2 2 "AABBB.", // 1: AA BBB 0 3 "AA.BBB", // 1 4 ".AABBB", // 2 5 "AABB..", // 2: AA BB 0 6 "AA.BB.", // 1 7 "AA..BB", // 2 8 ".AABB.", // 3 9 ".AA.BB", // 4 10 "..AABB", // 5 11 "AAA...", // 3: AAA 0 12 ".AAA..", // 1 13 "..AAA.", // 2 14 "...AAA", // 3 15 "AA....", // 4: AA 0 16 ".AA...", // 1 17 "..AA..", // 2 18 "...AA.", // 3 19 "....AA", // 4 20 "......", // 5: 0 21 }; // These are the only valid options for the 5th column that block the main block: const int vshape45_count = 4; const int vshape45_first[4] = {0, 3, 9, 13}; // inclusive const int vshape45_last[4] = {3, 9, 13, 18}; // exclusive const char *voptions45[] = { // shape pos idx "AABBB.", // 1: AA BBB 0 0 "AA.BBB", // 1 1 ".AABBB", // 2 2 "AABB..", // 2: AA BB 0 3 "AA.BB.", // 1 4 "AA..BB", // 2 5 ".AABB.", // 3 6 ".AA.BB", // 4 7 "..AABB", // 5 8 "AAA...", // 3: AAA 0 9 ".AAA..", // 1 10 "..AAA.", // 2 11 "...AAA", // 3 12 "AA....", // 4: AA 0 13 ".AA...", // 1 14 "..AA..", // 2 15 "...AA.", // 3 16 "....AA", // 4 17 }; // These initial positions in rows 4 or 5 would allow the main block to exit so must not be used. const int exit_vshape45_count = 5; const int exit_vshape45_first[5] = {0, 1, 3, 4, 7}; // inclusive const int exit_vshape45_last[5] = {1, 3, 4, 7, 8}; // exclusive const char *exit_voptions45[] = { // shape pos idx "AA.BBB", // 0: AAA BB 0 0 "AA.BB.", // 2: AA BB 0 1 "AA..BB", // 1 2 "...AAA", // 3: AAA 0 3 "AA....", // 4: AA 0 4 "...AA.", // 1 5 "....AA", // 2 6 "......", // 5: 0 7 }; // The exit row (3) is constrained. The block to be extracted cannot have any horizontal blocks to the right of it, // and it must have at least one column free to the right of it to be obstructed by a vertical block. const int shape2_count = 5; const int shape2_first[5] = {0, 1, 2, 5, 8}; const int shape2_last[5] = {1, 2, 5, 8, 12}; /* Previously, we were looping as so: for (hoption2 = init_option2; hoption2 < b; hoption2++) { In this rewrite, we do: for (shape2 = 0; shape2 < shape2_count; shape2++) { for (hoption2 = shape2_first[shape2]; hoption2 < shape2_last[shape2]; hoption2++) { */ const char *options2[] = { // shape pos idx "AAAXX.", // 6: AAA XX 0 0 "AAXXX.", // 7: AA XXX 0 1 "AAXX..", // 8: AA XX 0 2 "AA.XX.", // 1 3 ".AAXX.", // 2 4 "XXX...", // 9: XXX 0 5 ".XXX..", // 1 6 "..XXX.", // 2 7 "XX....", // 10: XX 0 8 ".XX...", // 1 9 "..XX..", // 2 10 "...XX.", // 3 11 }; /* // Not using this yet but I think it may be useful later... const chat *solutions2[] = { "AAA.XX", ".AAAXX", "AA.XXX", ".AAXXX", "AA..XX", ".AA.XX", "..AAXX", "...XXX", "....XX", }; // With an X in row 2 column 4 and 5, the options for the shapes of columns 4 and 5 are limited. // If the target is 3 units long (XXX) then this is also forced in column 3. // shape pos idx "AA.BBB", // 0: AAA BB 1 4 "AA.BB.", // 2: AA BB 1 7 "AA..BB", // 2 8 "...AAA", // 3: AAA 3 15 "AA....", // 4: AA 0 16 "...AA.", // 3 19 "....AA", // 4 20 "......", // 5: 0 21 */ /* Duplicate initial states can be removed by filling the board, and then eliminating any board positions where any block can be moved left or up, as compatible layouts will already have been generated. When the board is finally output any tiles which can be moved right or down may or may be not moved at random: they make no difference to the gameplay for that layout. The removal of redundant states can be done on the fly for columns while the boards are being generated, but to check rows once the columns have been added requires an extra pass (which is not yet being done - this is why the output file of all possible layouts is currently 28691701 entries!). */ int assign_horizontal_row(const char *row, char *dest, const int base_letter) { int pos, c, letters_placed = 0, blocks_placed = 0; for (pos = 0; pos < 6; pos++) { c = row[pos]; if (c == '.') { // } else if (c != 'X') { c = c -'A' + base_letter; blocks_placed += 1; } dest[pos] = c; // assign empties as well as blocks } // 0 if (blocks_placed != 0) letters_placed = 1; // 1 if (blocks_placed > 3) letters_placed += 1; // 2 return letters_placed; } int assign_vertical_column(const char *col, char *dest, const int base_letter) { int pos, c, letters_placed = 0, blocks_placed = 0, destpos = 0; for (pos = 0; pos < 6; pos++) { c = col[pos]; if (c != '.') { // No 'X' to worry about vertically... // and we don't need to check the destination as it was already validated by 'vertically_compatible()'. // Only assign blocks, not empty spaces. dest[destpos] = c -'A' + base_letter; blocks_placed += 1; } destpos += 6; } // 0 if (blocks_placed != 0) letters_placed = 1; // 1 if (blocks_placed > 3) letters_placed += 1; // 2 return letters_placed; } int vertically_compatible(const char *col, char *dest) { int pos, destpos = 0; for (pos = 0; pos < 6; pos++) { if (col[pos] != '.') { if (dest[destpos] != '.') return FALSE; // cannot place a block here - position already used! if (destpos >= 6 && (col[pos-1] != col[pos]) && dest[destpos-6] == '.') return FALSE; // a redundant position - could have been placed above } destpos += 6; } return TRUE; } static volatile FILE *results = NULL; // Declared as global to reduce cost of passing another parameter around. // and as 'volatile' so that the variable is sure to be up to date when // accessed from the atexit() handler which can be invoked from typing a ^C. #define a ( sizeof(hoptions01345)/sizeof(hoptions01345[0]) ) // number of options to fill a regular row or a column #define b ( sizeof(options2) /sizeof(options2[0]) ) // number of options allowed in the exit row. // These define the state of the generator, containing the current choice of tiles for each row and column at any time. // They are printed in the log file and can be used to resume an abandoned run (which is a feature that was added because // currently a run can take a few hours). 'volatile', so that the data is up to date when saving on a trapped ^C. // (Note that for efficiency we actually restart an abandoned run using the last row positions only - the column // positions are refilled from scratch.) static volatile int rowshape0, rowshape1, rowshape2, rowshape3, rowshape4, rowshape5; // rows 0:5 static volatile int colshape0, colshape1, colshape2, colshape3, colshape4, colshape5; // rows 0:5 static volatile int voption0, voption1, voption2, voption3, voption4, voption5; // state of filling columns static volatile int hoption0, hoption1, hoption2, hoption3, hoption4, hoption5; // state of filling rows // By the way, each layout can be identified by a single number which is the arithmetic encoding of the options above - // this could be very useful for minimising the storage in the next version of my Vectrex unblockme game which is // implemented in a 32K eprom. Even just using 4 bit fields for most of the rows and 3 bits for the exit row will // give a pretty dense representation: 4 * 6 + 5 * 6 + 3 bits, i.e. 57 bits or 8 bytes - a "long long int"!. // So 1000 games can be stored in 8K - a lot better than the 117 games in the current version! // The only reason I made these global (and volatile) was to be able to safely print intermediate // stats on aborting with ^C. Later I might trap ^\ to just print the stats and keep running. Or use SIGUSR1. static volatile int forced_exit = FALSE; // truly huge number of board positions possible exceeds 31 bits. // Maybe we can get away with unsigned long? Not sure of the actual number yet. static volatile long long int total_boards = 0LL; void CtrlC(int dummy) { forced_exit = TRUE; exit(EXIT_FAILURE); } void cleanup(void) { if (forced_exit) { fprintf(stderr, "\n\n%lld game layouts generated so far.\n\n\n%d/%d %d/%d %d/%d %d/%d %d/%d %d/%d\n\n", total_boards, hoption0,a, hoption1,a, hoption2,b, hoption3,a, hoption4,a, hoption5,a); } fclose((FILE *)/*discard volatile*/results); results = NULL; } int main(int argc, char **argv) { // Generate every possible unique layout! static char layout[BOARD_SIZE]; //int init_option0=0, init_option1=0, init_option2=0, init_option3=0, init_option4=0, init_option5=0; // Add omp stuff soon, but only in thread-safe contexts... //#ifdef _OPENMP // To do. Needs thread-safe code which I haven't yet written. // #pragma omp parallel for //#endif atexit(cleanup); signal(SIGINT, CtrlC); //if (argc == 7) { // quick have to resume from an aborted run. // e.g.: ./allgames 4 20 10 16 19 19 //init_option0 = (int)atol(argv[1]); //init_option1 = (int)atol(argv[2]); //init_option2 = (int)atol(argv[3]); //init_option3 = (int)atol(argv[4]); //init_option4 = (int)atol(argv[5]); //init_option5 = (int)atol(argv[6]); //results = fopen("unblockme-games.txt", "a"); //} else { results = fopen("unblockme-games.txt.new", "w"); // ".new" to avoid potentially overwriting the results of a large run by accident! //} // This is an 'embarrasingly parallel' algorithm, so it should be easy to modify to use all // available cores on a single machine, whether by using threads or with forking. Even OpenMP // would work. Or move to multi-system parallelism with Open MPI for even bigger wins. I do // have half a dozen 4-core pi4's and pi5's that I could use for this just to see how quickly // I could make it run, but I should optimise the single system/single core option first. // Aborted runs can be resumed from roughly where they left off, by saving options1..6 from // the atexit() handler, and reloading them before entering the loop below. // To find a single randomly-chosen solution, the loops below would instead start from a random position // within the range allowed and wrap around back to the starting position before the end of the loops. // This would use the same mechanism as restarting an abandoned run, with the addition of '% a' and '% b' // to the "option++" statements (e.g. "option0 = (option0+1)%a") // The 'shape' of a row is defined by the number, length, and order of tiles in that row. // We want the shortest solution for any *shape*. Shapes are unique. An option is a shape plus a position, // By only generating one board per unique shape, we never generate any redundant boards. The only problem // lies in chosing which option for each shape is the best starting position, i.e. the one which takes the // most moves to solve. for (rowshape0 = 0; rowshape0 < hshape01345_count; rowshape0++) { for (rowshape1 = 0; rowshape1 < hshape01345_count; rowshape1++) { for (rowshape2 = 0; rowshape2 < hshape01345_count; rowshape2++) { for (rowshape3 = 0; rowshape3 < hshape01345_count; rowshape3++) { for (rowshape4 = 0; rowshape4 < hshape01345_count; rowshape4++) { for (rowshape5 = 0; rowshape5 < hshape01345_count; rowshape5++) { for (colshape0 = 0; colshape0 < hshape01345_count; colshape0++) { for (colshape1 = 0; colshape1 < hshape01345_count; colshape1++) { for (colshape2 = 0; colshape2 < hshape01345_count; colshape2++) { for (colshape3 = 0; colshape3 < hshape01345_count; colshape3++) { for (colshape4 = 0; colshape4 < hshape01345_count; colshape4++) { for (colshape5 = 0; colshape5 < hshape01345_count; colshape5++) { // The loop overhead of getting to this point is just 6 seconds! if (0) fprintf(stderr, "# Next shape: \"%s\" \"%s\" \"%s\" \"%s\" \"%s\" \"%s\" " "VState=%d %d %d %d %d %d " " \"%s\" \"%s\" \"%s\" \"%s\" \"%s\" \"%s\" " "HState=%d %d %d %d %d %d\n", voptions0123[vshape0123_first[colshape0]], voptions0123[vshape0123_first[colshape1]], voptions0123[vshape0123_first[colshape2]], voptions0123[vshape0123_first[colshape3]], voptions0123[vshape45_first[colshape4]], voptions0123[vshape45_first[colshape5]], colshape0, colshape1, colshape2, colshape3, colshape4, colshape5, hoptions01345[hshape01345_first[rowshape0]], hoptions01345[hshape01345_first[rowshape1]], options2[hshape01345_first[rowshape2]], hoptions01345[hshape01345_first[rowshape3]], hoptions01345[hshape01345_first[rowshape4]], hoptions01345[hshape01345_first[rowshape5]], rowshape0, rowshape1, rowshape2, rowshape3, rowshape4, rowshape5 ); // At this point we know the shape of the layout, i.e. whether each row has 1, 2, or 3 tiles, // and whether each of the tiles are 2 or 3 units long. We do not yet know the absolute // positions of those tiles in their rows and columns. Those are determined by the next sets // of loops. // We only want one solution per layout shape. Currently the code to evaluate which // layout is the best starting position is unnecessarily expensive but with this restructuring // I can merge all the following loops into a single graph (a modification of the breadth-first // search code) and efficiently determine which path is farthest from a goal position. int next_letter_h0 = 'A', next_letter_h1, next_letter_h2, next_letter_h3, next_letter_h4, next_letter_h5, next_letter_v0, next_letter_v1, next_letter_v2, next_letter_v3, next_letter_v4, next_letter_v5, last_horiz_letter, last_vert_letter; // before finding the best layout for a given shape, it would be nice to find out if there were *any* solution for this shape, // and if so, skip the big loops below. Unfortunately the only way to know that no solution is possible is to actually try every // possible layout option for this shape, which kind of defeats the point of avoiding the loop. Especially since if it *does* // find a solution, it still has to look at all possibilities to find the best one. So running the entire loop will have to // be done, win or lose. //fprintf(stderr, "A board can be fitted with these options.\n"); // TO DO: the BFS code can be moved here to optimise the searching of multiple layouts with the same shape. // One way of tackling this would be to scan through all the options for this shape, and find the ones where // the main block is free to exit, and then BFS backwards from there using the alternatives to find the farthest one. // NOTE: these procedures which write to global state (eg 'next_letter') preclude using OpenMP // unless they're rewritten to be thread safe, or protected by a critical region pragma. int found_one; char hsave0[6*6+1]; char hsave1[6*6+1]; char hsave2[6*6+1]; char hsave3[6*6+1]; char hsave4[6*6+1]; //char hsave5[6*6+1]; char vsave0[6*6+1]; char vsave1[6*6+1]; char vsave2[6*6+1]; char vsave3[6*6+1]; char vsave4[6*6+1]; char vsave5[6*6+1]; found_one = FALSE; for (hoption0 = hshape01345_first[rowshape0]; hoption0 < hshape01345_last[rowshape0]; hoption0++) { strcpy(layout, "...................................."); next_letter_h1 = next_letter_h0+assign_horizontal_row(hoptions01345[hoption0], &layout[ 0], next_letter_h0); strncpy(hsave0, layout, 6*6); for (hoption1 = hshape01345_first[rowshape1]; hoption1 < hshape01345_last[rowshape1]; hoption1++) { strncpy(layout, hsave0, 6*6); next_letter_h2 = next_letter_h1+assign_horizontal_row(hoptions01345[hoption1], &layout[ 6], next_letter_h1); strncpy(hsave1, layout, 6*6); for (hoption2 = shape2_first[rowshape2]; hoption2 < shape2_last[rowshape2]; hoption2++) { strncpy(layout, hsave1, 6*6); next_letter_h3 = next_letter_h2+assign_horizontal_row(options2 [hoption2], &layout[12], next_letter_h2); strncpy(hsave2, layout, 6*6); for (hoption3 = hshape01345_first[rowshape3]; hoption3 < hshape01345_last[rowshape3]; hoption3++) { strncpy(layout, hsave2, 6*6); next_letter_h4 = next_letter_h3+assign_horizontal_row(hoptions01345[hoption3], &layout[18], next_letter_h3); strncpy(hsave3, layout, 6*6); for (hoption4 = hshape01345_first[rowshape4]; hoption4 < hshape01345_last[rowshape4]; hoption4++) { strncpy(layout, hsave3, 6*6); next_letter_h5 = next_letter_h4+assign_horizontal_row(hoptions01345[hoption4], &layout[24], next_letter_h4); strncpy(hsave4, layout, 6*6); for (hoption5 = hshape01345_first[rowshape5]; hoption5 < hshape01345_last[rowshape5]; hoption5++) { strncpy(layout, hsave4, 6*6); next_letter_v0 = next_letter_h5+assign_horizontal_row(hoptions01345[hoption5], &layout[30], next_letter_h5); strncpy(vsave0, layout, 6*6); last_horiz_letter = next_letter_v0; for (voption0 = vshape0123_first[colshape0]; voption0 < vshape0123_last[colshape0]; voption0++) { strncpy(layout, vsave0, 6*6); if (!vertically_compatible(voptions0123[voption0], &layout[0])) continue; next_letter_v1 = next_letter_v0+assign_vertical_column(voptions0123[voption0], &layout[0], next_letter_v0); // <--- these may be the problem strncpy(vsave1, layout, 6*6); for (voption1 = vshape0123_first[colshape1]; voption1 < vshape0123_last[colshape1]; voption1++) { strncpy(layout, vsave1, 6*6); if (!vertically_compatible(voptions0123[voption1], &layout[1])) continue; next_letter_v2 = next_letter_v1+assign_vertical_column(voptions0123[voption1], &layout[1], next_letter_v1); strncpy(vsave2, layout, 6*6); for (voption2 = vshape0123_first[colshape2]; voption2 < vshape0123_last[colshape2]; voption2++) { strncpy(layout, vsave2, 6*6); if (!vertically_compatible(voptions0123[voption2], &layout[2])) continue; next_letter_v3 = next_letter_v2+assign_vertical_column(voptions0123[voption2], &layout[2], next_letter_v2); strncpy(vsave3, layout, 6*6); for (voption3 = vshape0123_first[colshape3]; voption3 < vshape0123_last[colshape3]; voption3++) { strncpy(layout, vsave3, 6*6); if (!vertically_compatible(voptions0123[voption3], &layout[3])) continue; next_letter_v4 = next_letter_v3+assign_vertical_column(voptions0123[voption3], &layout[3], next_letter_v3); strncpy(vsave4, layout, 6*6); for (voption4 = vshape45_first[colshape4]; voption4 < vshape45_last[colshape4]; voption4++) { strncpy(layout, vsave4, 6*6); if (!vertically_compatible(voptions45[voption4], &layout[4])) continue; next_letter_v5 = next_letter_v4+assign_vertical_column(voptions45[voption4], &layout[4], next_letter_v4); strncpy(vsave5, layout, 6*6); for (voption5 = vshape45_first[colshape5]; voption5 < vshape45_last[colshape5]; voption5++) { strncpy(layout, vsave5, 6*6); if (!vertically_compatible(voptions45[voption5], &layout[5])) continue; last_vert_letter = next_letter_v5+assign_vertical_column(voptions45[voption5], &layout[5], next_letter_v5); if (last_horiz_letter == last_vert_letter) { fprintf(stderr, "Eliminated because no vertical blocks placed!\n"); continue; } last_vert_letter -= 1; layout[6*6] = '\0'; // 0 1 2 3 4 5 // 6 7 8 9 10 11 // 12 13 14 15 16 17 <-- exit // 18 19 20 21 22 23 // 24 25 26 27 28 29 // 30 31 32 33 34 35 if (layout[17] == '.') { if (layout[16] == 'X') { fprintf(stderr, "Eliminated %.6s\n", &layout[12]); continue; } if (layout[16] == '.') { if (layout[15] == 'X') { fprintf(stderr, "Eliminated %.6s\n", &layout[12]); continue; } if (layout[15] == '.') { if (layout[14] == 'X') { fprintf(stderr, "Eliminated %.6s\n", &layout[12]); continue; } if (layout[14] == '.') { if (layout[13] == 'X') { fprintf(stderr, "Eliminated %.6s\n", &layout[12]); continue; } } } } } found_one = TRUE; //goto GOT_ONE; //continue; // At this point we now have a completed layout to be tested and a note of the last letter placed which may come in useful later. { char p[BOARD_SIZE]; // extra room added to also store the sequence of moves needed to escape. int steps; strcpy(p, layout); total_boards += 1LL; // TO DO: PREFER TO COUNT VALID BOARDS if (solvable(p, &steps)) { // Solvable does a breadth-first search on just this one placement. The code can be optimised // considerably by *NOT* deleting the information that is saved for each position in the solution. // In fact we don't even need to do the breadth-first solution search - we can simply construct a // graph of all the different instances of this shape and the placements that they link to when // applying a single move. // Even better, we don't need to mess around moving tiles... we already know all the shape options // that a move can take - for example ".AA..." *MUST* link to either "AA...." or "..AA..". So take // advantage of this, and compute the links far more efficiently! // TO DO: I could modify 'solvable()' to reject any solutions in which some of the blocks present were never moved. // This can be done relatively cheaply by examining the solving solution (i.e. &p[6*6+1]) and seeing // if any of the blocks which are present in the layout are not included in the solution. (It would have // been helpful if the solution string had also included an indication of the highest letter used. It doesn't, // so that has to be determined by a scan of the board. Or added later.) // After some thought, I've decided I should indeed do this because if you remove the unmovable blocks // you are left with a puzzle which could have the same solution. On the other hand with the blocking // blocks removed, the remaining puzzle might even have a shorter solution taking advantage of the extra // empty spaces, so maybe it's not equivalent after all. // I'm not sure if a layout which is solvable in 0 steps (i.e. by immediately extracting the target block) // is worth optimising as a special case (which can be detected by checking board[row:3][col:6] back to the 'X'...) // but boards where the master piece can be extracted immediately are really of no interest. // Previously I was including them in the output file (below) but I've now decided to trivially reject them by // simply testing for 'steps != 0' below: // If it is a valid layout, log it to file. if (steps != 0) { fprintf((FILE *)/*discard volatile*/results, "%d \"%s\" " "# %s %d%% done. " "VState=%d/%d %d/%d %d/%d %d/%d %d/%d %d/%d " "HState=%d/%d %d/%d %d/%d %d/%d %d/%d %d/%d\n\n", steps, layout, &p[6*6+1], iround(hoption0*100.0/(1.0*a)), voption0,a, voption1,a, voption2,b, voption3,a, voption4,a, voption5,a, // NEED UPDATING voptions45 etc hoption0,a, hoption1,a, hoption2,b, hoption3,a, hoption4,a, hoption5,a ); // fewer layouts are worth reporting to the screen: if (MIN_STEPS >= 10 && steps >= MIN_STEPS) { // don't print to screen if this will generate millions of results! fprintf(stderr, "Solved in %d moves: ./solve \"%s\" " "# %s %d%% done. " "VState=%d/%d %d/%d %d/%d %d/%d %d/%d %d/%d " "HState=%d/%d %d/%d %d/%d %d/%d %d/%d %d/%d\n\n", steps, layout, &p[6*6+1], iround(hoption0*100.0/(1.0*a)), voption0,a, voption1,a, voption2,b, voption3,a, voption4,a, voption5,a, // NEED UPDATING voptions45 etc hoption0,a, hoption1,a, hoption2,b, hoption3,a, hoption4,a, hoption5,a); } } } } // end if (solvable()) ... } } } } } } // end of for voption0 } } } } } } // end of for hoption0 //GOT_ONE: // TO DO: the code below outputs erroneous boards whenever the board consists of // only horizontal blocks, no vertical blocks. As a side effect of the lack of // vertical blocks, the XX block is always exposed to the exit. FIX IT! /* Still getting some boards accepted that should not be due to XXX being exposed: Board: .AAABB .CCCDD ..XXX. .EEEFF ....GH ....GH */ if (found_one) { fprintf(stderr, "\nBoard:\n%.6s\n", &layout[0]); fprintf(stderr, "%.6s\n", &layout[6]); fprintf(stderr, "%.6s\n", &layout[12]); fprintf(stderr, "%.6s\n", &layout[18]); fprintf(stderr, "%.6s\n", &layout[24]); fprintf(stderr, "%.6s\n\n", &layout[30]); } else { fprintf(stderr, "No board. H %d %d %d %d %d %d V %d %d %d %d %d %d \r", hoption0, hoption1, hoption2, hoption3, hoption4, hoption5, voption0, voption1, voption2, voption3, voption4, voption5 ); } } } } } } } // end of for colshape0 } } } } } } // end of for rowshape0 fprintf(stderr, "\n%lld game layouts generated!\n\n", total_boards); /* To do: use clock() to keep track of cpu time used. Also gettimeofday() for wall clock elapsed time. Print estimates of expected total time, time left, number generated, expected numbers at end. (This becomes less important as the code is speeded up.) */ exit(EXIT_SUCCESS); return EXIT_FAILURE; }