/**************************************************************************** PURPOSE : Try to solve the 70^2 puzzle using backtacking. AUTHORS : Th. Wolf (TW) LANGUAGE: ANSI C ---------------------------------------------------------------------------- HISTORY : 08-May-1996 TW Created. Uses primitive brute-force. 17-Jul-1996 TW Added CORNER, TOUCH, and TABLE heuristics, added more command line options, added corridor computation. 18-Jul-1996 TW Improved accuracy of corridor computation: speedup of > 50%! Thrown out CORNER and TOUCH heuristics. Corrected table for the corners of the boundary (reducing the number of positions to try by ~15%). 19-Jul-1996 TW Improved table again: we only have to try positions with the 24*24 square along one edge or in a triangle in the NW quadrant. Also added handling of SIGINT in order to have a way of finding out what the program is up to even during long runs. Also allowing skipping more than one square, provided they're all smaller than the 7*7 one! 22-Jul-1996 TW If we want to place a square, and we find that position [x][y] is occupied by square #size, we can immediately increase the y-coordinate by 'size'. Yields another 20 to 50% speedup. Also added save/restore options plus autosave feature. 23-Jul-1996 TW Autosave only every five minutes (instead of every 500 positions. Also added handling of symmetric solutions. Also added EDGE heuristic: placing squares first along the edges of the 70*70 square. 24-Jul-1996 TW Corrected EDGE heuristic: we have to fill edges in the order left-top-right-bottom instead of bottom-left-top- right (because of the layout of the table). Also, the symmetry conditions in the 'edge_?' functions were not exactly right. Also changed state: we store size and position always. 'try' ignores the size, while 'edge_?' ignores the position. Minor change in "local optimality" in 'try': replace "unusable < min_unusable" by "<=". Otherwise corrected EDGE heuristic misses solutions... Unfortunately, this about doubles the number of positions to try - anihilat- ing most of the speed gain achieved in the last few days. ---------------------------------------------------------------------------- COMMENTS: The 70^2 puzzle is given as follows: "Since 1^2 + 2^2 + 3^2 + ... + 24^2 = 70^2, is it possible to dissect a 70 x 70 square into 24 smaller squares of sizes 1x1, 2x2, ... 24x24?" I know there's a solution using all but the 7x7 square, covering 4851 units. Therefore, we restrict the search for sequences that skip at most one square, except when skipping squares smaller than that 7*7 square. Once the program has found a solution, it'll only pursue branches in the search tree that might yield an even better solution. Simple case: if we have a solution where we skipped the 10*10 square, we'll never again try solutions that would involve skipping a larger square. Corridor computa- tion also is used to cut dead branches. The CORNER heuristic only places squares in some corner. The TOUCH heu- ristic requires that a new square touch another one or be placed at the edge of the 70*70 square. The TABLE heuristic sets up a table telling us where not to place a square. For instance, large squares should be placed either at the edge or quite far away from it! It also exploits some basic symmetry relations. The best solution found with the CORNER heuristic (which is guaranteed not to find the 4851 solution) is a 4800 covering, omitting the 10x10 square. This position is found after having tried exactly 366'099 posi- tions. It is as yet unknown whether there's an even better solution that can be found by that heuristic. The TOUCH heuristic, which also won't find the 4851 solution, already generates far too many possibilities to be useful. To discard poor solutions, we look for "corridors", i.e. for areas where we can only place 3*3, 2*2, or 1*1 squares. These places essentially are lost, so they decerease the possible maximum that is still attainable. The TABLE heuristic tries to avoid bad placements of large squares. For instance, it doesn't make sense to place the 24*24 square near an edge of the board, such that a corridor occurs: ************************************* *xx+-----------------------+ *xx| | *xx| | *xx| | *xx| | *xx| | *xx| | <-- Bad placement of 24*24 square *xx| | *xx| | *xx| | *xx| | *xx| | *xx+-----------------------+ * For the 24*24 square, it'll also exploit symmetry relations: we'll place it only in very specific places in the NW quadrant of the board. The program prints a '.' (or a '?' if in interactive mode) every 500 positions to indicate progress. If the user interrupts the program (sends it a SIGINT, usually by typing Ctrl-C), s/he's presented with a menu. This has several purposes: - It catches unintended program terminations - It provides an easy, asynchronous way of changing modes (interactive/non-interactive) - It provides an easy way to inspect the program's state during long runs. Note: the program seems to slow down the more positions it tries. That effect is imaginary: in reality, the program just discards more and more possible placements as not promising enough. And since we only count placements that actually are followed by trying to place a smaller square, the impression that the program slows down occurs. Also note: the TABLE heuristic isn't really a heuristic - it determines some places on the board where it cannot be good to place a certain square. No guesswork involved! So, if you want to improve on this, find a real heuristic that cuts down the number of branches significantly and still doesn't miss good solutions. Then, use that heuristic in addition to the TABLE algorithm already used. Time. Oh, yes. Time after time. All right, our problem is NP-complete. So, this program may run quite a while until it has tried all possible and sensible combinations. An optimistic guess is about 1 year to try all possibilities. A pessimistic guess is based on the formula: (70-24)^2 * (70-23)^2 * ... * (70-2)^2 = 1.82 * 10^50 giving an upper limit of possible arrangements. Let's assume that's 1E50 possibilities. Let's assume we have only 140 unique (non-symmetric) placements of the 24*24 square: 1E48. Let's assume that only 10% of that really are unique: 1E46. Let's assume that we grossly overestimated the number of possibilities (most of them are impossible because squares would overlap): 1E23. Let's assume we can check 1E9 positions per second. That gives us 1E14 seconds. Which still is about 3'000'000 years. Although none of the heuristics have yet discovered the 4851 solution, they're basically able to find it. If restarted from the test files .test_4851_edge or.test_4851_normal, which describe positions short of that solution, they do find the cover. ---------------------------------------------------------------------------- CREDITS: Frans J. Faase (faase@cs.utwnte.nl) http://www.cs.utwente.nl/~faase/ Proposed the CORNER heuristic (not contained anymore in these sources). The EDGE heuristic also is based on a proposal of him. James Irl Waldby (j-waldby@uiuc.edu) http://biobio.cs.uiuc.edu/~j-waldby/james.html Proposed the TABLE method in a posting to comp.programming.contests. Thomas Wolf (t_wolf@tiscalinet.ch) http://home.tiscalinet.ch/t_wolf/ Implementation, fiddling around with table settings, corridor computation, etc. ---------------------------------------------------------------------------- COPYRIGHT: This program is distributed under the GNU Public License. (See any GNU distribution mirror for the details.) You're most welcome to make im- provements to this code, provided this header remains intact, you describe clearly what you did, maintain the change log above and the statistics below, and - if your improvement really did improve the program's ability to find good solutions - you send me [wolf@di.epfl.ch] a copy of your modified version. Thanks :-) ---------------------------------------------------------------------------- STATISTICS 18-Jul-1996 TW cover positions time (Sun Sparc 10) 4611 15'941 18 sec (skipped 17) 4644 252'592 6 min (skipped 16) 4675 256'829 7 min (skipped 15) 4704 379'344 11 min (skipped 14) 4731 393'000 12 min (skipped 13) 4756 516'805 17 min (skipped 12) 4779 721'862 25 min (skipped 11) 4800 723'066 25 min (skipped 10) 4819 879'526 34 min (skipped 9) 4836 927'309 37 min (skipped 8) 19-Jul-1996 TW 4819 879'526 35 min (skipped 9) 4839 927'289 37 min (skipped 6, 5) 4848 1'635'875 1:16 hours (skipped 6, 4) 22-Jul-1996 TW -a.autosave After the 4848 cover, no better cover is found for at least 40'000'000 positions (some 40+ hours). 4611 15'941 9 sec (skipped 17) 4644 252'592 3 min (skipped 16) 4675 256'829 3 min (skipped 15) 4704 379'344 6 min (skipped 14) 4731 393'000 7 min (skipped 13) 4756 516'805 10 min (skipped 12) 4779 721'862 15 min (skipped 11) 4800 723'066 15 min (skipped 10) 4819 879'526 20 min (skipped 9) 4839 927'289 21 min (skipped 6, 5) 4848 1'635'875 53 min (skipped 6, 4) 23-Jul-1996 TW -a.edge_autosave -hedge (EDGE heuristic) 4539 166 1 sec (skipped 19) 4611 2'303 3 sec (skipped 17) 4704 105'370 2 min (skipped 14) 4756 346'947 5 min (skipped 12) 4800 16'136'829 9:31 hours (skipped 10) 24-Jul-1996 TW -a.edge_autosave -hedge (EDGE heuristic) Just like the 4644 cover in the run below, note the 4756 and the 4800 cover... (The speedup is due to the program's running now on a lightly loaded machine.) After the 4800 cover, no better solution is found for at least 82'000'000 positions (34+ hours). 4539 918 1 sec (skipped 19) 4576 3'048 2 sec (skipped 18) 4611 8'307 7 sec (skipped 17) 4704 106'148 2 min (skipped 14) 4731 108'531 2 min (skipped 13) 4756 328'847 6 min (skipped 12) 4800 16'047'660 5:36 hours (skipped 10) 24-Jul-1996 TW -a.autosave Note the 4644 cover here: it's found in less tries than in the version from 22-Jul-1996, even though this version has about twice as many positions to check! This clearly indicates that the former version might have missed solutions - which might be important beyond the 4819 cover... though from the 4756 cover, both versions find exactly the same solutions. 4611 18'107 17 sec (skipped 17) 4644 237'876 5 min (skipped 16) 4675 289'836 7 min (skipped 15) 4704 465'576 12 min (skipped 14) 4731 481'885 13 min (skipped 13) 4756 630'495 19 min (skipped 12) 4779 1'086'536 29 min (skipped 11) 4800 1'087'776 29 min (skipped 10) 4819 1'265'088 37 min (skipped 9) 4839 1'316'182 39 min (skipped 6, 5) 4848 2'079'664 1:21 hours (skipped 6, 4) ****************************************************************************/ #include #include #include #include #include #include /****************************************************************************/ #define SIZE 70 #define LIMIT 24 #define TRUE 1 #define FALSE 0 /****************************************************************************/ void try_none (void); void try_edge (void); typedef void (*Fill_The_Board)(void); typedef struct { char *name; Fill_The_Board do_it; } Heuristic; Heuristic heuristics[] = { {"none", try_none}, {"edge", try_edge} }; int h_index; #define NOF_HEURISTICS (sizeof (heuristics) / sizeof (Heuristic)) /****************************************************************************/ /**** Note: our board has a border around it! Indices 1 to SIZE are the actual board, indices 0 and SIZE+1 are used as sentinels. */ int board [SIZE+2][SIZE+2]; /* The board where we place our squares */ int backup[SIZE+2][SIZE+2]; /* Where we save the "background" when placing a square. This is necessary to restore corridors correctly when removing a square. */ int table [SIZE+2][SIZE+2]; /* The table telling us where not to place large squares. */ /**** The sentinels have value LIMIT+1. Areas occupied by a square contain the (positive) size of that square. Negative numbers indicate a corridor found when placing the square of size (-number). 0 indicates an unoccupied unit not in a corridor. */ /**** Some variables for storing command line options etc. */ int verbose = FALSE; int interactive = FALSE; int ask = TRUE; int count, dots, solutions; int n_verbose; unsigned long positions_tried; /****************************************************************************/ int max_covered = 0; /* Largest covering found so far. */ int min_skipped = LIMIT; /* Smallest square skipped so far. (We do not allow skipping the 24*24 square.) */ /**** 'max_covered' can be set with the '-m' command line option. */ /****************************************************************************/ /**** Saving and restoring the state. */ #define INTERVAL 5 /* Autosave interval in minutes */ typedef struct State { int x, y, size; } State; State state[2*(LIMIT+2)]; int last_state = 0; int saved_state = 0; int loading = FALSE; char *auto_save = NULL; time_t last_saved; /****************************************************************************/ time_t start_time; void print_time (FILE *f, char *s) { time_t now = time (NULL); fprintf (f, "%s%s\n", s, ctime (&now)); } /* end print_time */ /****************************************************************************/ /**** Signal handling */ volatile sig_atomic_t aborted = FALSE; jmp_buf environment; /****************************************************************************/ void received_ctrl_c (int sig) /**** This is our signal handler for ctrl-c */ { if (sig == SIGINT) { /**** Ignore the signal from now on... we'll re-install the signal handler once we've presented the menu to the user. */ signal (sig, SIG_IGN); aborted = TRUE; } /* end if */ } /* end received_ctrl_c */ /****************************************************************************/ void really_quit (void); /****************************************************************************/ void print_board (FILE *f, int solution, int skipped, int real_one, int possible, int estimate) /**** If 'solution' = TRUE, skipped tells us which square was skipped (0, if none) and 'possible' gives the corridor estimate of what could be achieved (always >= the area covered). 'real_one' usually is TRUE. Only when we print the table, it is FALSE. */ { int x, y, val, covered, ch; if (solution) covered = possible; else covered = 0; if ((covered <= max_covered) && !verbose) return; if (covered > max_covered) max_covered = covered; /**** Only set 'min_skipped' if we only skipped one square. Otherwise, we might miss solutions. Consider a case where 5 & 6 are skipped: we'd set 'min_skipped' to 6 (*not* to 5!!). But then, we'd miss any solution only skipping 6 alone! or even any solution skipping 6 and a square smaller than 5! */ if (covered && SIZE*SIZE-skipped*skipped == covered) min_skipped = skipped; if (solution) print_time (f, "\nSolution found at "); fprintf (f, "\n----------- %d, %lu positions, skipped: %d\n", covered, positions_tried, skipped); for (x = 0; x < SIZE+2; x++) { for (y = 0; y < SIZE+2; y++) { val = (real_one ? board[x][y] : table[x][y]); if (val > LIMIT) putc ('*', f); /* Border */ else if (val < 0) putc ('a' - val - 1, f); /* Corridor */ else putc (val ? 'A' + val - 1 : ' ', f); /* Square || Nothing */ } putc ('\n', f); } putc ('\n', f); fprintf (f, "Possible max: %d\n", possible); fprintf (f, "Estimate : %d\n", estimate); fflush (f); dots = 0; if (aborted) really_quit (); else if (ask) { if (verbose || interactive) ch = getchar (); if (interactive) { if (ch != EOF && ch != '\n') (void) getchar (); if (ch == '+' || ch == '-') verbose = (ch == '+'); } /* end if */ } /* end if */ } /* end print_board */ /****************************************************************************/ int read_line (char *buf, size_t length, FILE *f) /**** Safely read a line of input from file 'f'. */ { int l = 0; if (fgets (buf, length, f)) { l = strlen (buf); if (buf[l-1] == '\n') buf[--l] = '\0'; else { fscanf (f, "%*[^\n]"); (void) fgetc (f); } /* end if */ } /* end if */ return l; } /* end read_line */ /****************************************************************************/ /**** Saving and restoring the state... */ void save (char *name) { FILE *f = fopen (name, "w"); int i; if (!f) { fprintf (stderr, "Can't write file \"%s\"\n", name); } else { fprintf (f, "%d\n", last_state+1); for (i = 0; i <= last_state; i++) { fprintf (f, "%d %d %d\n", state[i].x, state[i].y, state[i].size); } /* end for */ fprintf (f, "%d\n", max_covered); fprintf (f, "%lu\n", positions_tried); fprintf (f, "%d\n", solutions); fprintf (f, "%d\n", h_index); fclose (f); } /* end if */ if (name != auto_save) fprintf (stderr, "State saved\n"); else last_saved = time (NULL); } /* end save */ /****************************************************************************/ void reload (char *name) { FILE *f = fopen (name, "r"); int i; if (!f) { fprintf (stderr, "Can't read file \"%s\"\n", name); } else { fscanf (f, "%d", &saved_state); for (i = 0; i < saved_state; i++) { fscanf (f, "%d %d %d",&state[i].x, &state[i].y, &state[i].size); } /* end for */ fscanf (f, "%d", &max_covered); fscanf (f, "%lu", &positions_tried); fscanf (f, "%d", &solutions); fscanf (f, "%d", &h_index); fclose (f); loading = TRUE; positions_tried -= saved_state; } /* end if */ } /* end reload */ /****************************************************************************/ void really_quit (void) /**** Use 'stderr' for output to see the results even if 'stdout' is redirected. This function is called after we have received a SIGINT signal (usually when the user typed Ctrl-C). We present a menu, giving the user various possibilities to examine the program's state, resume it, or really abort it. Note that we flush 'stderr' even though it isn't fully buffered: it might be line buffered! (See ISO/IEC 9899:1990(E), 7.9.3) */ { int ch, old_verbose; int do_menu = TRUE; aborted = FALSE; fprintf (stderr, "\nReceived signal SIGINT (Ctrl-C).\n\n"); for (;;) { if (do_menu) { fprintf (stderr, "Choose one of the following:\n"); fprintf (stderr, " 1 - Abort the program\n"); fprintf (stderr, " 2 - Resume\n"); fprintf (stderr, " 3 - Show board\n"); fprintf (stderr, " 4 - Show max covering so far\n"); fprintf (stderr, " 5 - Show number of positions tried so far\n"); fprintf (stderr, " 6 - Enter verbose-interactive mode\n"); fprintf (stderr, " 7 - Leave verbose-interactive mode\n"); fprintf (stderr, " 8 - Print timing information\n"); fprintf (stderr, " 9 - Save state\n"); putc ('\n', stderr); do_menu = FALSE; } /* end if */ fprintf (stderr, "Your choice (default=2): "); fflush (stderr); ch = getchar (); if (ch != EOF && ch != '\n') (void) getchar (); switch (ch) { case '1' : longjmp (environment, 1); return; case EOF : case '\n': case '2' : fprintf (stderr, "Resumed\n"); if (signal (SIGINT, received_ctrl_c) == SIG_ERR) { fprintf (stderr, "Failed to re-install signal handler!\n"); if (signal (SIGINT, SIG_DFL) == SIG_ERR) { fprintf (stderr, "Can't re-install default signal handling, aborted!\n"); fflush (stderr); longjmp (environment, 2); } /* end if */ } /* end if */ fflush (stderr); return; case '3' : old_verbose = verbose; verbose = TRUE; ask = FALSE; print_board (stderr, FALSE, 0, TRUE, 0, 0); verbose = old_verbose; ask = TRUE; do_menu = TRUE; break; case '4' : fprintf (stderr, "Max covering found so far: %d\n", max_covered); fflush (stderr); break; case '5' : fprintf (stderr, "Positions tried so far: %lu\n", positions_tried); fflush (stderr); break; case '6' : verbose = interactive = TRUE; fprintf (stderr, "Interactive mode is ON.\n"); fflush (stderr); break; case '7' : verbose = interactive = FALSE; fprintf (stderr, "Interactive mode is OFF.\n"); fflush (stderr); break; case '8' : fprintf (stderr, "Program was started at %s", ctime (&start_time)); print_time (stderr, "It is now "); fflush (stderr); break; case '9' : { char file_name[64]; fprintf (stderr, "Filename: "); fflush (stderr); if (read_line (file_name, sizeof (file_name), stdin)) save (file_name); } break; default : fprintf (stderr, "Enter a number between 1 and 9 or , please!\n"); fflush (stderr); } /* end switch */ } /* end for */ } /* end really_quit */ /****************************************************************************/ /**** Corridor logic. A corridor is a small unoccupied strip on the board which we cannot completely fill with the remaining small squares: +----------+oo+--------------+ | |oo| | | |xo| | | |xx| | | |xx| | | |xx| | +----------+xx| | | | +--------------+ All the spaces marked by "x" are wasted. Those marked by 'o' aren't, they account for the possible placement of the 2*2 and 1*1 square in the corridor. It's not that easy to exactly compute space wasted due to corridors, but a fairly good approximation is feasible. Note that this approxi- mation always will result in a "wasted space" <= the true wasted space, so inaccuracies in this computation will not cause us to not find a solution. */ typedef struct { int size, square, used_by; } Corridor; Corridor corridor[] = { {14, 196, 0}, {13, 169, 0}, {12, 144, 0}, {11, 121, 0}, {10, 100, 0}, { 9, 81, 0}, { 8, 64, 0}, { 7, 49, 0}, { 6, 36, 0}, { 5, 25, 0}, { 4, 16, 0}, { 3, 9, 0}, { 2, 4, 0}, { 1, 1, 0} }; #define MAX_CORRIDOR (sizeof (corridor) / sizeof (corridor[0])) /**** Remember: greater zero means occupied! */ #define ABOVE(x, y) (board[x][y-1] > 0) #define BELOW(x, y) (board[x][y+1] > 0) #define LEFT(x, y) (board[x-1][y] > 0) #define RIGHT(x, y) (board[x+1][y] > 0) int check_x_corridor (int x0, int y0, int y1, int i, int size) { int x, y, wasted = 0, max, X, Y, j, k; if (x0 < 1 || y0 < 1 || y1 < 1) return 0; max = SIZE + 1 - corridor[i].size; if (x0 > max || y0 > max || y1 > max) return 0; X = x0 + corridor[i].size - 1; x = x0; for (y = y0; y <= y1; y++) { Y = y + corridor[i].size - 1; if (board[x][Y] || board[X][Y]) y = Y; else if (board[x][y] || board[X][y]) continue; else if ((ABOVE (x, y) && ABOVE (X, y) && BELOW (x, Y) && BELOW (X, Y)) || (LEFT (x, y) && LEFT (x, Y) && RIGHT (X, y) && RIGHT (X, Y))) { for (j = x; j <= X; j++) for (k = y; k <= Y; k++) board[j][k] = -size; wasted += corridor[i].square; } } return wasted; } /* end check_x_corridor */ int check_y_corridor (int x0, int y0, int x1, int i, int size) { int x, y, wasted = 0, max, X, Y, j, k; if (x0 < 1 || y0 < 1 || x1 < 1) return 0; max = SIZE + 1 - corridor[i].size; if (x0 > max || y0 > max || x1 > max) return 0; Y = y0 + corridor[i].size - 1; y = y0; for (x = x0; x <= x1; x++) { X = x + corridor[i].size - 1; if (board[X][y] || board[X][Y]) x = X; else if (board[x][y] || board[x][Y]) continue; else if ((ABOVE (x, y) && ABOVE (X, y) && BELOW (x, Y) && BELOW (X, Y)) || (LEFT (x, y) && LEFT (x, Y) && RIGHT (X, y) && RIGHT (X, Y))) { for (j = x; j <= X; j++) for (k = y; k <= Y; k++) board[j][k] = -size; wasted += corridor[i].square; } } return wasted; } /* end check_y_corridor */ int used (int i, int size, int waste) { int sum; sum = 0; while (i < MAX_CORRIDOR && sum < waste) { if (!corridor[i].used_by) { sum += corridor[i].square; corridor[i].used_by = size; } i++; } /* end while */ return sum; } /* end used */ int find_new_corridors (int x, int y, int X, int Y, int size) /**** New corridors can only be created along the edges of a newly placed square. */ { int i, wasted, curr; wasted = 0; for (i = 0; i < MAX_CORRIDOR; i++) { if (corridor[i].size >= size) continue; curr = check_x_corridor (x-corridor[i].size, y, Y+1-corridor[i].size, i, size); curr += check_x_corridor (X+1, y, Y+1 - corridor[i].size, i, size); curr += check_y_corridor (x, y - corridor[i].size, X+1 - corridor[i].size, i, size); curr += check_y_corridor (x, Y+1, X+1 - corridor[i].size, i, size); curr -= used (i, size, curr); if (curr > 0) wasted += curr; } /* end for */ return wasted; } /* end find_new_corridors */ void undo_x_corridor (int x0, int y0, int y1, int sq, int size) { int x, y; for (y = y0; y <= y1; y++) { for (x = x0; x < x0 + sq; x++) { if (x >= 1 && x <= SIZE && y >= 1 && y <= SIZE && board[x][y] == -size) board[x][y] = 0; } } } /* end undo_x_corridor */ void undo_y_corridor (int x0, int y0, int x1, int sq, int size) { int x, y; for (x = x0; x <= x1; x++) { for (y = y0; y < y0 + sq; y++) { if (x >= 1 && x <= SIZE && y >= 1 && y <= SIZE && board[x][y] == -size) board[x][y] = 0; } } } /* end undo_y_corridor */ void remove_corridors (int x, int y, int X, int Y, int size) { int square = corridor[0].size, i; undo_x_corridor (x - square, y, Y, square, size); undo_x_corridor (X+1 , y, Y, square, size); undo_y_corridor (x, y - square, X, square, size); undo_y_corridor (x, Y+1 , X, square, size); for (i = 0; i < MAX_CORRIDOR; i++) { if (corridor[i].used_by == size) corridor[i].used_by = 0; } } /* end remove_corridors */ /****************************************************************************/ int init[] = { LIMIT+1, 2, 3, 5, 9, 12, 18, 22 }; #define MAX_INIT (sizeof (init) / sizeof (init[0])) void init_table (void) { int x, y, min; for (x = 0; x < SIZE+2; x++) { for (y = 0; y < SIZE+2; y++) { if (x <= 1 || y <= 1 || x >= SIZE || y >= SIZE) { /**** We're somewhere on the boundary */ if (x == 1 && y <= SIZE/2 && y >= MAX_INIT) table[x][y] = LIMIT+1; else if ((x == 1 || x == SIZE) && (y >= 1 && y <= SIZE)) { min = y-1; if (SIZE - y < min) min = SIZE - y; table[x][y] = ((!min || min >= MAX_INIT) ? LIMIT : init[min]); } else if ((y == 1 || y == SIZE) && (x >= 1 && x <= SIZE)) { min = x-1; if (SIZE - x < min) min = SIZE -x; table[x][y] = ((!min || min >= MAX_INIT) ? LIMIT : init[min]); } else table[x][y] = LIMIT+1; /* end if */ } else { min = x-1; if (y-1 < min) min = y-1; if (SIZE - x < min) min = SIZE - x; if (SIZE - y < min) min = SIZE - y; if (min >= MAX_INIT) table[x][y] = LIMIT + (x >= y && x <= (SIZE-LIMIT)/2); else table[x][y] = init[min]; } /* end if */ } /* end for */ } /* end for */ table[1][1] = LIMIT+1; print_board (stdout, FALSE, 0, FALSE, 0, 0); } /* end init_table */ int placement_allowed (int x, int y, int X, int Y, int size) /**** The corner nearest to a corner of the 70*70 square determines whether or not we may place the square. */ { int a, b, c, min; min = x*x + y*y; a = x; b = y; if ((c = x*x + ((SIZE+1)-Y)*((SIZE+1)-Y)) < min) { min = c; a = x; b = Y; } if ((c = ((SIZE+1)-X)*((SIZE+1)-X) + y*y) < min) { min = c; a = X; b = y; } if ((c = ((SIZE+1)-X)*((SIZE+1)-X) + ((SIZE+1)-Y)*((SIZE+1)-Y)) < min) { min = c; a = X; b = Y; } return table[a][b] > size; } /* end placement_allowed */ /****************************************************************************/ typedef struct { int x, y, X, Y; } RECT; RECT square_stack[LIMIT+1]; int s_top; /****************************************************************************/ void remove_square (int x, int y, int size) { register int i, j; remove_corridors (x, y, x + size - 1, y + size - 1, size); for (i = x; i < x + size; i++) { for (j = y; j < y + size; j++) { board[i][j] = backup[i][j]; } } s_top--; } /* end remove_square */ /****************************************************************************/ int overlap (int x, int y, int X, int Y) { int i; for (i = 0; i < s_top; i++) { if (x <= square_stack[i].X && X >= square_stack[i].x && y <= square_stack[i].Y && Y >= square_stack[i].y) return TRUE; } /* end for */ return FALSE; } /* end overlap */ /****************************************************************************/ int put_square (int x, int y, int size, int possible_max, int *unusable) { register int i, j, X, Y, wasted, min, ch; X = x + size - 1; Y = y + size - 1; if ((X > SIZE) || (Y > SIZE)) return FALSE; #if 0 /**** To check whether the space if free, it suffices to check the four corners. Because we place squares in descending order, it's im- possible that there is a smaller square in this area. */ if (board[x][Y] > 0 || board[X][y] > 0 || board[X][Y] > 0) /**** Note: 'board[x][y]' already has been checked! */ return FALSE; /**** NOTE: above is correct only for heuristic "none"! Therefore, we use 'overlap' to detect overlaps now! */ #endif if (overlap (x, y, X, Y) || !placement_allowed (x, y, X, Y, size)) return FALSE; /**** It's ok! */ for (i = x; i <= X; i++) { for (j = y; j <= Y; j++) { backup[i][j] = board[i][j]; board[i][j] = size; } /* end for */ } /* end for */ square_stack[s_top].x = x; square_stack[s_top].y = y; square_stack[s_top].X = X; square_stack[s_top].Y = Y; s_top++; /**** Calculate wasted space */ wasted = find_new_corridors (x, y, X, Y, size); if ((possible_max - wasted) <= max_covered) { remove_square (x, y, size); return FALSE; } /* end if */ *unusable = wasted; /**** Ok, still possible */ positions_tried++; if (n_verbose && positions_tried == n_verbose) verbose = interactive = TRUE; if (++count % 500 == 0) { if (auto_save && difftime (time (NULL), last_saved) > INTERVAL * 60) save (auto_save); if (aborted) really_quit (); if (interactive) { putc ('?', stdout); fflush (stdout); ch = getchar (); if (ch != EOF && ch != '\n') (void) getchar (); verbose = (ch == '+'); } else { putc ('.', stdout); if (++dots % 80 == 0) { putc ('\n', stdout); dots = 0; } /* end if */ count = 0; fflush (stdout); } /* end if */ } /* end if */ return TRUE; } /* end put_square */ /****************************************************************************/ typedef enum { FREE = 0, USED = 1, SKIPPED = 2 } Placement; Placement squares[LIMIT+1]; State square_24; #define SZ_MIN 7 void try (int size, int possible_max, int estimate, int skipped) /**** 'possible_max' gives the maximum coverage that is obtainable. It is SIZE*SIZE initially and is decreased every time we decide to skip a square. 'estimate' is the maximum possible coverage according to our corridor computation. */ { register int x, y, x_org, y_org; int unusable, min_unusable = -1; if (verbose) print_board (stdout, FALSE, skipped, TRUE, possible_max, estimate); if (size == 0) { /**** We have a solution! */ solutions++; print_board (stdout, TRUE, skipped, TRUE, possible_max, estimate); if (auto_save) save (auto_save); } else { last_state++; if (last_state < saved_state && loading) { x_org = state[last_state].x; y_org = state[last_state].y; } else { x_org = y_org = 1; loading = FALSE; } /* end if */ while (size && squares[size] != FREE) size--; if (!size) { /**** Solution! */ solutions++; print_board (stdout, TRUE, skipped, TRUE, possible_max, estimate); if (auto_save) save (auto_save); return; } /* end if */ state[last_state].size = size; for (x = x_org; x <= SIZE+1-size; x++) { y = y_org; while (y <= SIZE+1-size) { state[last_state].x = x; state[last_state].y = y; if (size == LIMIT) { square_24.x = x; square_24.y = y; } /* end if */ if (board[x][y] > 0) y += board[x][y]; else { /**** The terms involving 'square_24' are symmetry conditions. */ if (!(size == LIMIT-1 && (square_24.x == square_24.y && y < x || square_24.y == (SIZE-LIMIT)/2 + 1 && y <= (SIZE-LIMIT)/2)) && put_square (x, y, size, estimate, &unusable)) { #if 1 /**** Note: the condition below actually is a heuristic: we assume that locally worse solutions won't lead to globally better ones... I don't particularly like this, but it works quite well, and without it, there are just too many possibilities to try. (TW). */ if (min_unusable < 0 || unusable <= min_unusable) { if (unusable) min_unusable = unusable; #endif squares[size] = USED; try (size-1, possible_max, estimate - unusable, skipped); squares[size] = FREE; #if 1 } /* end if */ #endif remove_square (x, y, size); if (possible_max <= max_covered || estimate <= max_covered) { last_state--; return; } /* end if */ } /* end if */ y++; } /* end if */ } /* end while */ } /* end for */ possible_max -= size * size; /**** The term 'skipped < 7' allows multiple skips for small squares. 7 was chosen because we know there's a solution skipping only that 7*7 square. */ if ((!skipped || skipped < 7) && (size < min_skipped) && (possible_max > max_covered) && (estimate > max_covered)) { state[last_state].x = x; state[last_state].y = y; squares[size] = SKIPPED; try (size-1, possible_max, estimate, !skipped ? size : skipped); squares[size] = FREE; } /* end if */ last_state--; } /* end if */ } /* end try */ /****************************************************************************/ /**** EDGE heuristic: place squares first along the edge of the 70*70 square. Uses standard 'try' to try to fill the remaining space. */ void edge_b (int possible_max, int estimate) { int x, sz, unusable, sz_org; if (verbose) print_board (stdout, FALSE, 0, TRUE, possible_max, estimate); /**** Find first free square on edge */ last_state++; if (last_state < saved_state && loading) sz_org = state[last_state].size; else { sz_org = LIMIT-1; loading = FALSE; } /* end if */ x = SIZE; while (x >= 1 && board[x][1] > 0) x -= board[x][1]; state[last_state].y = 1; if (x <= 0) { state[last_state].size = sz_org; state[last_state].x = x; try (LIMIT, possible_max, estimate, 0); } /* end if */ /**** Symmetry considerations */ if (sz_org == LIMIT-1) { if (square_24.x == square_24.y || square_24.y == (SIZE-LIMIT) / 2 + 1) sz_org--; } /* end if */ for (sz = sz_org; sz >= SZ_MIN; sz--) { state[last_state].size = sz; if (x+1-sz <= 0) continue; if (squares[sz] == FREE && put_square (x+1-sz, 1, sz, estimate, &unusable)) { squares[sz] = USED; state[last_state].x = x+1-sz; edge_b (possible_max, estimate - unusable); remove_square (x+1-sz, 1, sz); squares[sz] = FREE; if (possible_max <= max_covered || estimate <= max_covered) break; } /* end if */ } /* end for */ last_state--; } /* end edge_b */ void edge_r (int possible_max, int estimate) { int y, sz, unusable, sz_org; if (verbose) print_board (stdout, FALSE, 0, TRUE, possible_max, estimate); /**** Find first free square on edge */ last_state++; if (last_state < saved_state && loading) sz_org = state[last_state].size; else { sz_org = LIMIT-1; loading = FALSE; } /* end if */ y = SIZE; while (y >= 1 && board[SIZE][y] > 0) y -= board[SIZE][y]; if (y <= 0) { state[last_state].size = sz_org; state[last_state].x = 0; state[last_state].y = 0; edge_b (possible_max, estimate); } /* end if */ /**** Symmetry considerations */ if (sz_org == LIMIT-1) { if (square_24.x == square_24.y || square_24.y == (SIZE-LIMIT) / 2 + 1 && y-LIMIT < (SIZE-LIMIT) / 2 + 1) sz_org--; } /* end if */ for (sz = sz_org; sz >= SZ_MIN; sz--) { state[last_state].size = sz; if (y+1-sz <= 0) continue; if (squares[sz] == FREE && put_square (SIZE+1-sz, y+1-sz, sz, estimate, &unusable)) { squares[sz] = USED; state[last_state].x = SIZE+1-sz; state[last_state].y = y+1-sz; edge_r (possible_max, estimate - unusable); remove_square (SIZE+1-sz, y+1-sz, sz); squares[sz] = FREE; if (possible_max <= max_covered || estimate <= max_covered) break; } /* end if */ } /* end for */ last_state--; } /* end edge_r */ void edge_t (int possible_max, int estimate) { int x, sz, unusable, sz_org; if (verbose) print_board (stdout, FALSE, 0, TRUE, possible_max, estimate); /**** Find first free square on edge */ last_state++; if (last_state < saved_state && loading) sz_org = state[last_state].size; else { sz_org = LIMIT-1; loading = FALSE; } /* end if */ x = 1; while (x <= SIZE && board[x][SIZE] > 0) x += board[x][SIZE]; state[last_state].x = x; if (x > SIZE) { state[last_state].size = sz_org; state[last_state].y = 0; edge_r (possible_max, estimate); } /* end if */ for (sz = sz_org; sz >= SZ_MIN; sz--) { state[last_state].size = sz; if (x+sz-1 > SIZE) continue; if (squares[sz] == FREE && put_square (x, SIZE+1-sz, sz, estimate, &unusable)) { squares[sz] = USED; state[last_state].y = SIZE+1-sz; edge_t (possible_max, estimate - unusable); remove_square (x, SIZE+1-sz, sz); squares[sz] = FREE; if (possible_max <= max_covered || estimate <= max_covered) break; } /* end if */ } /* end for */ last_state--; } /* end edge_t */ void edge_l (int possible_max, int estimate) { int y, sz, unusable, sz_org; if (verbose) print_board (stdout, FALSE, 0, TRUE, possible_max, estimate); /**** Find first free square on edge */ last_state++; if (last_state < saved_state && loading) sz_org = state[last_state].size; else { sz_org = LIMIT; loading = FALSE; } /* end if */ y = 1; while (y <= SIZE && board[1][y] > 0) y += board[1][y]; state[last_state].x = 1; state[last_state].y = y; if (y > SIZE) { state[last_state].size = sz_org; edge_t (possible_max, estimate); } /* end if */ for (sz = sz_org; sz >= SZ_MIN; sz--) { state[last_state].size = sz; if (y+sz-1 > SIZE) continue; if (squares[sz] == FREE && put_square (1, y, sz, estimate, &unusable)) { squares[sz] = USED; if (sz == LIMIT) { square_24.x = 1; square_24.y = y; } /* end if */ edge_l (possible_max, estimate - unusable); remove_square (1, y, sz); squares[sz] = FREE; if (possible_max <= max_covered || estimate <= max_covered) break; } /* end if */ } /* end for */ last_state--; } /* end edge_l */ /****************************************************************************/ void try_none (void) { try (LIMIT, SIZE*SIZE, SIZE*SIZE, 0); } /* end try_none */ void try_edge (void) { edge_l (SIZE*SIZE, SIZE*SIZE); } /* end try_edge */ /****************************************************************************/ void bail_out (char *prog, char *msg, char *opt) { if (!prog) prog = "square_70"; fprintf (stderr, "%s: ERROR: %s", prog, msg); if (opt) fprintf (stderr, ": %s", opt); fputc ('\n', stderr); exit (EXIT_FAILURE); } /* end bail_out */ /****************************************************************************/ char opts[UCHAR_MAX+1]; int err_code; /* return value of 'set_jmp' */ int main (int argc, char *argv[]) { char *in_name = NULL; int i, x, y; for (i = 1; i < argc; i++) { char *opt = argv[i]; if (*opt != '-') bail_out (argv[0], "Option should start with '-'", opt); if (opts[(unsigned char)opt[1]]) bail_out (argv[0], "Option appears more than once", opt); switch (opt[1]) { case 'v': /**** -v: print the board whenever a square is placed */ verbose = TRUE; break; case 'i': /**** -i: interactive mode. Allows the user to enter ('+') or leave ('-') verbose mode whenever we prompt: after having printed the board and when a '?' is printed. */ interactive = TRUE; break; case 'n': /**** -n####: break into interactive mode after #### positions */ n_verbose = atoi (opt+2); break; case 'm': /**** -m####: tell the program that a solution covering #### units exists. We'll only try to find better solutions. */ max_covered = atoi (opt+2); break; case 'r': /**** -rname: reload a saved program state from file 'name'. */ reload (opt+2); break; case 'a': /**** -aname: switch on autosaving, save to file 'name'. */ auto_save = opt+2; break; case 'h': /**** -hname: choose the heuristic to use. */ if (loading) bail_out (argv[0], "Heuristic already determined by -r option", opt); { int i = 0; while (i < NOF_HEURISTICS && strcmp (opt+2, heuristics[i].name)) i++; if (i >= NOF_HEURISTICS) bail_out (argv[0], "Unknown heuristic", opt+2); h_index = i; printf ("Using heuristic \"%s\"\n", heuristics[i].name); } break; default: bail_out (argv[0], "Unknown option", opt); } opts[(unsigned char)opt[1]] = TRUE; } /**** Set the signal handler */ if (signal (SIGINT, received_ctrl_c) == SIG_ERR) bail_out (argv[0], "Can't catch Ctrl-C, aborted", NULL); /**** Now use setjmp/longjmp to really terminate the application if that's what the user wants. */ if ((err_code = setjmp (environment)) == 0) { /**** Initialize border of board */ for (x = 0; x < SIZE+2; x++) { board[x][0] = LIMIT+1; board[x][SIZE+1] = LIMIT+1; } /* end for */ for (y = 0; y < SIZE+2; y++) { board[0][y] = LIMIT+1; board[SIZE+1][y] = LIMIT+1; } /* end for */ init_table (); start_time = last_saved = time (NULL); printf ("Program started at %s\n", ctime (&start_time)); heuristics[h_index].do_it (); } else { /**** We get here only through a 'longjmp' after a Ctrl-C */ print_time (stdout, "\nProgram aborted at "); printf ("Reason: %s\n", (err_code == 1 ? "User abort" : "Signal failed")); } /* end if */; printf ("\n%d solutions found for the 70^2 problem.\n", solutions); return EXIT_SUCCESS; } /* end main */ /****************************************************************************/ /* end square_70.c */