| 1 | /* |
| 2 | * towers.c: the puzzle also known as 'Skyscrapers'. |
| 3 | * |
| 4 | * Possible future work: |
| 5 | * |
| 6 | * - Relax the upper bound on grid size at 9? |
| 7 | * + I'd need TOCHAR and FROMCHAR macros a bit like group's, to |
| 8 | * be used wherever this code has +'0' or -'0' |
| 9 | * + the pencil marks in the drawstate would need a separate |
| 10 | * word to live in |
| 11 | * + the clues outside the grid would have to cope with being |
| 12 | * multi-digit, meaning in particular that the text formatting |
| 13 | * would become more unpleasant |
| 14 | * + most importantly, though, the solver just isn't fast |
| 15 | * enough. Even at size 9 it can't really do the solver_hard |
| 16 | * factorial-time enumeration at a sensible rate. Easy puzzles |
| 17 | * higher than that would be possible, but more latin-squarey |
| 18 | * than skyscrapery, as it were. |
| 19 | * |
| 20 | * - UI work? |
| 21 | * + Allow the user to mark a clue as 'spent' in some way once |
| 22 | * it's no longer interesting (typically because no |
| 23 | * arrangement of the remaining possibilities _can_ violate |
| 24 | * it)? |
| 25 | */ |
| 26 | |
| 27 | #include <stdio.h> |
| 28 | #include <stdlib.h> |
| 29 | #include <string.h> |
| 30 | #include <assert.h> |
| 31 | #include <ctype.h> |
| 32 | #include <math.h> |
| 33 | |
| 34 | #include "puzzles.h" |
| 35 | #include "latin.h" |
| 36 | |
| 37 | /* |
| 38 | * Difficulty levels. I do some macro ickery here to ensure that my |
| 39 | * enum and the various forms of my name list always match up. |
| 40 | */ |
| 41 | #define DIFFLIST(A) \ |
| 42 | A(EASY,Easy,solver_easy,e) \ |
| 43 | A(HARD,Hard,solver_hard,h) \ |
| 44 | A(EXTREME,Extreme,NULL,x) \ |
| 45 | A(UNREASONABLE,Unreasonable,NULL,u) |
| 46 | #define ENUM(upper,title,func,lower) DIFF_ ## upper, |
| 47 | #define TITLE(upper,title,func,lower) #title, |
| 48 | #define ENCODE(upper,title,func,lower) #lower |
| 49 | #define CONFIG(upper,title,func,lower) ":" #title |
| 50 | enum { DIFFLIST(ENUM) DIFFCOUNT }; |
| 51 | static char const *const towers_diffnames[] = { DIFFLIST(TITLE) }; |
| 52 | static char const towers_diffchars[] = DIFFLIST(ENCODE); |
| 53 | #define DIFFCONFIG DIFFLIST(CONFIG) |
| 54 | |
| 55 | enum { |
| 56 | COL_BACKGROUND, |
| 57 | COL_GRID, |
| 58 | COL_USER, |
| 59 | COL_HIGHLIGHT, |
| 60 | COL_ERROR, |
| 61 | COL_PENCIL, |
| 62 | NCOLOURS |
| 63 | }; |
| 64 | |
| 65 | struct game_params { |
| 66 | int w, diff; |
| 67 | }; |
| 68 | |
| 69 | struct clues { |
| 70 | int refcount; |
| 71 | int w; |
| 72 | /* |
| 73 | * An array of 4w integers, of which: |
| 74 | * - the first w run across the top |
| 75 | * - the next w across the bottom |
| 76 | * - the third w down the left |
| 77 | * - the last w down the right. |
| 78 | */ |
| 79 | int *clues; |
| 80 | |
| 81 | /* |
| 82 | * An array of w*w digits. |
| 83 | */ |
| 84 | digit *immutable; |
| 85 | }; |
| 86 | |
| 87 | /* |
| 88 | * Macros to compute clue indices and coordinates. |
| 89 | */ |
| 90 | #define STARTSTEP(start, step, index, w) do { \ |
| 91 | if (index < w) \ |
| 92 | start = index, step = w; \ |
| 93 | else if (index < 2*w) \ |
| 94 | start = (w-1)*w+(index-w), step = -w; \ |
| 95 | else if (index < 3*w) \ |
| 96 | start = w*(index-2*w), step = 1; \ |
| 97 | else \ |
| 98 | start = w*(index-3*w)+(w-1), step = -1; \ |
| 99 | } while (0) |
| 100 | #define CSTARTSTEP(start, step, index, w) \ |
| 101 | STARTSTEP(start, step, (((index)+2*w)%(4*w)), w) |
| 102 | #define CLUEPOS(x, y, index, w) do { \ |
| 103 | if (index < w) \ |
| 104 | x = index, y = -1; \ |
| 105 | else if (index < 2*w) \ |
| 106 | x = index-w, y = w; \ |
| 107 | else if (index < 3*w) \ |
| 108 | x = -1, y = index-2*w; \ |
| 109 | else \ |
| 110 | x = w, y = index-3*w; \ |
| 111 | } while (0) |
| 112 | |
| 113 | #ifdef STANDALONE_SOLVER |
| 114 | static const char *const cluepos[] = { |
| 115 | "above column", "below column", "left of row", "right of row" |
| 116 | }; |
| 117 | #endif |
| 118 | |
| 119 | struct game_state { |
| 120 | game_params par; |
| 121 | struct clues *clues; |
| 122 | digit *grid; |
| 123 | int *pencil; /* bitmaps using bits 1<<1..1<<n */ |
| 124 | int completed, cheated; |
| 125 | }; |
| 126 | |
| 127 | static game_params *default_params(void) |
| 128 | { |
| 129 | game_params *ret = snew(game_params); |
| 130 | |
| 131 | ret->w = 5; |
| 132 | ret->diff = DIFF_EASY; |
| 133 | |
| 134 | return ret; |
| 135 | } |
| 136 | |
| 137 | const static struct game_params towers_presets[] = { |
| 138 | { 4, DIFF_EASY }, |
| 139 | { 5, DIFF_EASY }, |
| 140 | { 5, DIFF_HARD }, |
| 141 | { 6, DIFF_EASY }, |
| 142 | { 6, DIFF_HARD }, |
| 143 | { 6, DIFF_EXTREME }, |
| 144 | { 6, DIFF_UNREASONABLE }, |
| 145 | }; |
| 146 | |
| 147 | static int game_fetch_preset(int i, char **name, game_params **params) |
| 148 | { |
| 149 | game_params *ret; |
| 150 | char buf[80]; |
| 151 | |
| 152 | if (i < 0 || i >= lenof(towers_presets)) |
| 153 | return FALSE; |
| 154 | |
| 155 | ret = snew(game_params); |
| 156 | *ret = towers_presets[i]; /* structure copy */ |
| 157 | |
| 158 | sprintf(buf, "%dx%d %s", ret->w, ret->w, towers_diffnames[ret->diff]); |
| 159 | |
| 160 | *name = dupstr(buf); |
| 161 | *params = ret; |
| 162 | return TRUE; |
| 163 | } |
| 164 | |
| 165 | static void free_params(game_params *params) |
| 166 | { |
| 167 | sfree(params); |
| 168 | } |
| 169 | |
| 170 | static game_params *dup_params(game_params *params) |
| 171 | { |
| 172 | game_params *ret = snew(game_params); |
| 173 | *ret = *params; /* structure copy */ |
| 174 | return ret; |
| 175 | } |
| 176 | |
| 177 | static void decode_params(game_params *params, char const *string) |
| 178 | { |
| 179 | char const *p = string; |
| 180 | |
| 181 | params->w = atoi(p); |
| 182 | while (*p && isdigit((unsigned char)*p)) p++; |
| 183 | |
| 184 | if (*p == 'd') { |
| 185 | int i; |
| 186 | p++; |
| 187 | params->diff = DIFFCOUNT+1; /* ...which is invalid */ |
| 188 | if (*p) { |
| 189 | for (i = 0; i < DIFFCOUNT; i++) { |
| 190 | if (*p == towers_diffchars[i]) |
| 191 | params->diff = i; |
| 192 | } |
| 193 | p++; |
| 194 | } |
| 195 | } |
| 196 | } |
| 197 | |
| 198 | static char *encode_params(game_params *params, int full) |
| 199 | { |
| 200 | char ret[80]; |
| 201 | |
| 202 | sprintf(ret, "%d", params->w); |
| 203 | if (full) |
| 204 | sprintf(ret + strlen(ret), "d%c", towers_diffchars[params->diff]); |
| 205 | |
| 206 | return dupstr(ret); |
| 207 | } |
| 208 | |
| 209 | static config_item *game_configure(game_params *params) |
| 210 | { |
| 211 | config_item *ret; |
| 212 | char buf[80]; |
| 213 | |
| 214 | ret = snewn(3, config_item); |
| 215 | |
| 216 | ret[0].name = "Grid size"; |
| 217 | ret[0].type = C_STRING; |
| 218 | sprintf(buf, "%d", params->w); |
| 219 | ret[0].sval = dupstr(buf); |
| 220 | ret[0].ival = 0; |
| 221 | |
| 222 | ret[1].name = "Difficulty"; |
| 223 | ret[1].type = C_CHOICES; |
| 224 | ret[1].sval = DIFFCONFIG; |
| 225 | ret[1].ival = params->diff; |
| 226 | |
| 227 | ret[2].name = NULL; |
| 228 | ret[2].type = C_END; |
| 229 | ret[2].sval = NULL; |
| 230 | ret[2].ival = 0; |
| 231 | |
| 232 | return ret; |
| 233 | } |
| 234 | |
| 235 | static game_params *custom_params(config_item *cfg) |
| 236 | { |
| 237 | game_params *ret = snew(game_params); |
| 238 | |
| 239 | ret->w = atoi(cfg[0].sval); |
| 240 | ret->diff = cfg[1].ival; |
| 241 | |
| 242 | return ret; |
| 243 | } |
| 244 | |
| 245 | static char *validate_params(game_params *params, int full) |
| 246 | { |
| 247 | if (params->w < 3 || params->w > 9) |
| 248 | return "Grid size must be between 3 and 9"; |
| 249 | if (params->diff >= DIFFCOUNT) |
| 250 | return "Unknown difficulty rating"; |
| 251 | return NULL; |
| 252 | } |
| 253 | |
| 254 | /* ---------------------------------------------------------------------- |
| 255 | * Solver. |
| 256 | */ |
| 257 | |
| 258 | struct solver_ctx { |
| 259 | int w, diff; |
| 260 | int started; |
| 261 | int *clues; |
| 262 | long *iscratch; |
| 263 | int *dscratch; |
| 264 | }; |
| 265 | |
| 266 | static int solver_easy(struct latin_solver *solver, void *vctx) |
| 267 | { |
| 268 | struct solver_ctx *ctx = (struct solver_ctx *)vctx; |
| 269 | int w = ctx->w; |
| 270 | int c, i, j, n, m, furthest; |
| 271 | int start, step, cstart, cstep, clue, pos, cpos; |
| 272 | int ret = 0; |
| 273 | #ifdef STANDALONE_SOLVER |
| 274 | char prefix[256]; |
| 275 | #endif |
| 276 | |
| 277 | if (!ctx->started) { |
| 278 | ctx->started = TRUE; |
| 279 | /* |
| 280 | * One-off loop to help get started: when a pair of facing |
| 281 | * clues sum to w+1, it must mean that the row consists of |
| 282 | * two increasing sequences back to back, so we can |
| 283 | * immediately place the highest digit by knowing the |
| 284 | * lengths of those two sequences. |
| 285 | */ |
| 286 | for (c = 0; c < 3*w; c = (c == w-1 ? 2*w : c+1)) { |
| 287 | int c2 = c + w; |
| 288 | |
| 289 | if (ctx->clues[c] && ctx->clues[c2] && |
| 290 | ctx->clues[c] + ctx->clues[c2] == w+1) { |
| 291 | STARTSTEP(start, step, c, w); |
| 292 | CSTARTSTEP(cstart, cstep, c, w); |
| 293 | pos = start + (ctx->clues[c]-1)*step; |
| 294 | cpos = cstart + (ctx->clues[c]-1)*cstep; |
| 295 | if (solver->cube[cpos*w+w-1]) { |
| 296 | #ifdef STANDALONE_SOLVER |
| 297 | if (solver_show_working) { |
| 298 | printf("%*sfacing clues on %s %d are maximal:\n", |
| 299 | solver_recurse_depth*4, "", |
| 300 | c>=2*w ? "row" : "column", c % w + 1); |
| 301 | printf("%*s placing %d at (%d,%d)\n", |
| 302 | solver_recurse_depth*4, "", |
| 303 | w, pos%w+1, pos/w+1); |
| 304 | } |
| 305 | #endif |
| 306 | latin_solver_place(solver, pos%w, pos/w, w); |
| 307 | ret = 1; |
| 308 | } else { |
| 309 | ret = -1; |
| 310 | } |
| 311 | } |
| 312 | } |
| 313 | |
| 314 | if (ret) |
| 315 | return ret; |
| 316 | } |
| 317 | |
| 318 | /* |
| 319 | * Go over every clue doing reasonably simple heuristic |
| 320 | * deductions. |
| 321 | */ |
| 322 | for (c = 0; c < 4*w; c++) { |
| 323 | clue = ctx->clues[c]; |
| 324 | if (!clue) |
| 325 | continue; |
| 326 | STARTSTEP(start, step, c, w); |
| 327 | CSTARTSTEP(cstart, cstep, c, w); |
| 328 | |
| 329 | /* Find the location of each number in the row. */ |
| 330 | for (i = 0; i < w; i++) |
| 331 | ctx->dscratch[i] = w; |
| 332 | for (i = 0; i < w; i++) |
| 333 | if (solver->grid[start+i*step]) |
| 334 | ctx->dscratch[solver->grid[start+i*step]-1] = i; |
| 335 | |
| 336 | n = m = 0; |
| 337 | furthest = w; |
| 338 | for (i = w; i >= 1; i--) { |
| 339 | if (ctx->dscratch[i-1] == w) { |
| 340 | break; |
| 341 | } else if (ctx->dscratch[i-1] < furthest) { |
| 342 | furthest = ctx->dscratch[i-1]; |
| 343 | m = i; |
| 344 | n++; |
| 345 | } |
| 346 | } |
| 347 | if (clue == n+1 && furthest > 1) { |
| 348 | #ifdef STANDALONE_SOLVER |
| 349 | if (solver_show_working) |
| 350 | sprintf(prefix, "%*sclue %s %d is nearly filled:\n", |
| 351 | solver_recurse_depth*4, "", |
| 352 | cluepos[c/w], c%w+1); |
| 353 | else |
| 354 | prefix[0] = '\0'; /* placate optimiser */ |
| 355 | #endif |
| 356 | /* |
| 357 | * We can already see an increasing sequence of the very |
| 358 | * highest numbers, of length one less than that |
| 359 | * specified in the clue. All of those numbers _must_ be |
| 360 | * part of the clue sequence, so the number right next |
| 361 | * to the clue must be the final one - i.e. it must be |
| 362 | * bigger than any of the numbers between it and m. This |
| 363 | * allows us to rule out small numbers in that square. |
| 364 | * |
| 365 | * (This is a generalisation of the obvious deduction |
| 366 | * that when you see a clue saying 1, it must be right |
| 367 | * next to the largest possible number; and similarly, |
| 368 | * when you see a clue saying 2 opposite that, it must |
| 369 | * be right next to the second-largest.) |
| 370 | */ |
| 371 | j = furthest-1; /* number of small numbers we can rule out */ |
| 372 | for (i = 1; i <= w && j > 0; i++) { |
| 373 | if (ctx->dscratch[i-1] < w && ctx->dscratch[i-1] >= furthest) |
| 374 | continue; /* skip this number, it's elsewhere */ |
| 375 | j--; |
| 376 | if (solver->cube[cstart*w+i-1]) { |
| 377 | #ifdef STANDALONE_SOLVER |
| 378 | if (solver_show_working) { |
| 379 | printf("%s%*s ruling out %d at (%d,%d)\n", |
| 380 | prefix, solver_recurse_depth*4, "", |
| 381 | i, start%w+1, start/w+1); |
| 382 | prefix[0] = '\0'; |
| 383 | } |
| 384 | #endif |
| 385 | solver->cube[cstart*w+i-1] = 0; |
| 386 | ret = 1; |
| 387 | } |
| 388 | } |
| 389 | } |
| 390 | |
| 391 | if (ret) |
| 392 | return ret; |
| 393 | |
| 394 | #ifdef STANDALONE_SOLVER |
| 395 | if (solver_show_working) |
| 396 | sprintf(prefix, "%*slower bounds for clue %s %d:\n", |
| 397 | solver_recurse_depth*4, "", |
| 398 | cluepos[c/w], c%w+1); |
| 399 | else |
| 400 | prefix[0] = '\0'; /* placate optimiser */ |
| 401 | #endif |
| 402 | |
| 403 | i = 0; |
| 404 | for (n = w; n > 0; n--) { |
| 405 | /* |
| 406 | * The largest number cannot occur in the first (clue-1) |
| 407 | * squares of the row, or else there wouldn't be space |
| 408 | * for a sufficiently long increasing sequence which it |
| 409 | * terminated. The second-largest number (not counting |
| 410 | * any that are known to be on the far side of a larger |
| 411 | * number and hence excluded from this sequence) cannot |
| 412 | * occur in the first (clue-2) squares, similarly, and |
| 413 | * so on. |
| 414 | */ |
| 415 | |
| 416 | if (ctx->dscratch[n-1] < w) { |
| 417 | for (m = n+1; m < w; m++) |
| 418 | if (ctx->dscratch[m] < ctx->dscratch[n-1]) |
| 419 | break; |
| 420 | if (m < w) |
| 421 | continue; /* this number doesn't count */ |
| 422 | } |
| 423 | |
| 424 | for (j = 0; j < clue - i - 1; j++) |
| 425 | if (solver->cube[(cstart + j*cstep)*w+n-1]) { |
| 426 | #ifdef STANDALONE_SOLVER |
| 427 | if (solver_show_working) { |
| 428 | int pos = start+j*step; |
| 429 | printf("%s%*s ruling out %d at (%d,%d)\n", |
| 430 | prefix, solver_recurse_depth*4, "", |
| 431 | n, pos%w+1, pos/w+1); |
| 432 | prefix[0] = '\0'; |
| 433 | } |
| 434 | #endif |
| 435 | solver->cube[(cstart + j*cstep)*w+n-1] = 0; |
| 436 | ret = 1; |
| 437 | } |
| 438 | i++; |
| 439 | } |
| 440 | } |
| 441 | |
| 442 | if (ret) |
| 443 | return ret; |
| 444 | |
| 445 | return 0; |
| 446 | } |
| 447 | |
| 448 | static int solver_hard(struct latin_solver *solver, void *vctx) |
| 449 | { |
| 450 | struct solver_ctx *ctx = (struct solver_ctx *)vctx; |
| 451 | int w = ctx->w; |
| 452 | int c, i, j, n, best, clue, start, step, ret; |
| 453 | long bitmap; |
| 454 | #ifdef STANDALONE_SOLVER |
| 455 | char prefix[256]; |
| 456 | #endif |
| 457 | |
| 458 | /* |
| 459 | * Go over every clue analysing all possibilities. |
| 460 | */ |
| 461 | for (c = 0; c < 4*w; c++) { |
| 462 | clue = ctx->clues[c]; |
| 463 | if (!clue) |
| 464 | continue; |
| 465 | CSTARTSTEP(start, step, c, w); |
| 466 | |
| 467 | for (i = 0; i < w; i++) |
| 468 | ctx->iscratch[i] = 0; |
| 469 | |
| 470 | /* |
| 471 | * Instead of a tedious physical recursion, I iterate in the |
| 472 | * scratch array through all possibilities. At any given |
| 473 | * moment, i indexes the element of the box that will next |
| 474 | * be incremented. |
| 475 | */ |
| 476 | i = 0; |
| 477 | ctx->dscratch[i] = 0; |
| 478 | best = n = 0; |
| 479 | bitmap = 0; |
| 480 | |
| 481 | while (1) { |
| 482 | if (i < w) { |
| 483 | /* |
| 484 | * Find the next valid value for cell i. |
| 485 | */ |
| 486 | int limit = (n == clue ? best : w); |
| 487 | int pos = start + step * i; |
| 488 | for (j = ctx->dscratch[i] + 1; j <= limit; j++) { |
| 489 | if (bitmap & (1L << j)) |
| 490 | continue; /* used this one already */ |
| 491 | if (!solver->cube[pos*w+j-1]) |
| 492 | continue; /* ruled out already */ |
| 493 | |
| 494 | /* Found one. */ |
| 495 | break; |
| 496 | } |
| 497 | |
| 498 | if (j > limit) { |
| 499 | /* No valid values left; drop back. */ |
| 500 | i--; |
| 501 | if (i < 0) |
| 502 | break; /* overall iteration is finished */ |
| 503 | bitmap &= ~(1L << ctx->dscratch[i]); |
| 504 | if (ctx->dscratch[i] == best) { |
| 505 | n--; |
| 506 | best = 0; |
| 507 | for (j = 0; j < i; j++) |
| 508 | if (best < ctx->dscratch[j]) |
| 509 | best = ctx->dscratch[j]; |
| 510 | } |
| 511 | } else { |
| 512 | /* Got a valid value; store it and move on. */ |
| 513 | bitmap |= 1L << j; |
| 514 | ctx->dscratch[i++] = j; |
| 515 | if (j > best) { |
| 516 | best = j; |
| 517 | n++; |
| 518 | } |
| 519 | ctx->dscratch[i] = 0; |
| 520 | } |
| 521 | } else { |
| 522 | if (n == clue) { |
| 523 | for (j = 0; j < w; j++) |
| 524 | ctx->iscratch[j] |= 1L << ctx->dscratch[j]; |
| 525 | } |
| 526 | i--; |
| 527 | bitmap &= ~(1L << ctx->dscratch[i]); |
| 528 | if (ctx->dscratch[i] == best) { |
| 529 | n--; |
| 530 | best = 0; |
| 531 | for (j = 0; j < i; j++) |
| 532 | if (best < ctx->dscratch[j]) |
| 533 | best = ctx->dscratch[j]; |
| 534 | } |
| 535 | } |
| 536 | } |
| 537 | |
| 538 | #ifdef STANDALONE_SOLVER |
| 539 | if (solver_show_working) |
| 540 | sprintf(prefix, "%*sexhaustive analysis of clue %s %d:\n", |
| 541 | solver_recurse_depth*4, "", |
| 542 | cluepos[c/w], c%w+1); |
| 543 | else |
| 544 | prefix[0] = '\0'; /* placate optimiser */ |
| 545 | #endif |
| 546 | |
| 547 | ret = 0; |
| 548 | |
| 549 | for (i = 0; i < w; i++) { |
| 550 | int pos = start + step * i; |
| 551 | for (j = 1; j <= w; j++) { |
| 552 | if (solver->cube[pos*w+j-1] && |
| 553 | !(ctx->iscratch[i] & (1L << j))) { |
| 554 | #ifdef STANDALONE_SOLVER |
| 555 | if (solver_show_working) { |
| 556 | printf("%s%*s ruling out %d at (%d,%d)\n", |
| 557 | prefix, solver_recurse_depth*4, "", |
| 558 | j, pos/w+1, pos%w+1); |
| 559 | prefix[0] = '\0'; |
| 560 | } |
| 561 | #endif |
| 562 | solver->cube[pos*w+j-1] = 0; |
| 563 | ret = 1; |
| 564 | } |
| 565 | } |
| 566 | |
| 567 | /* |
| 568 | * Once we find one clue we can do something with in |
| 569 | * this way, revert to trying easier deductions, so as |
| 570 | * not to generate solver diagnostics that make the |
| 571 | * problem look harder than it is. |
| 572 | */ |
| 573 | if (ret) |
| 574 | return ret; |
| 575 | } |
| 576 | } |
| 577 | |
| 578 | return 0; |
| 579 | } |
| 580 | |
| 581 | #define SOLVER(upper,title,func,lower) func, |
| 582 | static usersolver_t const towers_solvers[] = { DIFFLIST(SOLVER) }; |
| 583 | |
| 584 | static int solver(int w, int *clues, digit *soln, int maxdiff) |
| 585 | { |
| 586 | int ret; |
| 587 | struct solver_ctx ctx; |
| 588 | |
| 589 | ctx.w = w; |
| 590 | ctx.diff = maxdiff; |
| 591 | ctx.clues = clues; |
| 592 | ctx.started = FALSE; |
| 593 | ctx.iscratch = snewn(w, long); |
| 594 | ctx.dscratch = snewn(w+1, int); |
| 595 | |
| 596 | ret = latin_solver(soln, w, maxdiff, |
| 597 | DIFF_EASY, DIFF_HARD, DIFF_EXTREME, |
| 598 | DIFF_EXTREME, DIFF_UNREASONABLE, |
| 599 | towers_solvers, &ctx, NULL, NULL); |
| 600 | |
| 601 | sfree(ctx.iscratch); |
| 602 | sfree(ctx.dscratch); |
| 603 | |
| 604 | return ret; |
| 605 | } |
| 606 | |
| 607 | /* ---------------------------------------------------------------------- |
| 608 | * Grid generation. |
| 609 | */ |
| 610 | |
| 611 | static char *new_game_desc(game_params *params, random_state *rs, |
| 612 | char **aux, int interactive) |
| 613 | { |
| 614 | int w = params->w, a = w*w; |
| 615 | digit *grid, *soln, *soln2; |
| 616 | int *clues, *order; |
| 617 | int i, ret; |
| 618 | int diff = params->diff; |
| 619 | char *desc, *p; |
| 620 | |
| 621 | /* |
| 622 | * Difficulty exceptions: some combinations of size and |
| 623 | * difficulty cannot be satisfied, because all puzzles of at |
| 624 | * most that difficulty are actually even easier. |
| 625 | * |
| 626 | * Remember to re-test this whenever a change is made to the |
| 627 | * solver logic! |
| 628 | * |
| 629 | * I tested it using the following shell command: |
| 630 | |
| 631 | for d in e h x u; do |
| 632 | for i in {3..9}; do |
| 633 | echo -n "./towers --generate 1 ${i}d${d}: " |
| 634 | perl -e 'alarm 30; exec @ARGV' ./towers --generate 1 ${i}d${d} >/dev/null \ |
| 635 | && echo ok |
| 636 | done |
| 637 | done |
| 638 | |
| 639 | * Of course, it's better to do that after taking the exceptions |
| 640 | * _out_, so as to detect exceptions that should be removed as |
| 641 | * well as those which should be added. |
| 642 | */ |
| 643 | if (diff > DIFF_HARD && w <= 3) |
| 644 | diff = DIFF_HARD; |
| 645 | |
| 646 | grid = NULL; |
| 647 | clues = snewn(4*w, int); |
| 648 | soln = snewn(a, digit); |
| 649 | soln2 = snewn(a, digit); |
| 650 | order = snewn(max(4*w,a), int); |
| 651 | |
| 652 | while (1) { |
| 653 | /* |
| 654 | * Construct a latin square to be the solution. |
| 655 | */ |
| 656 | sfree(grid); |
| 657 | grid = latin_generate(w, rs); |
| 658 | |
| 659 | /* |
| 660 | * Fill in the clues. |
| 661 | */ |
| 662 | for (i = 0; i < 4*w; i++) { |
| 663 | int start, step, j, k, best; |
| 664 | STARTSTEP(start, step, i, w); |
| 665 | k = best = 0; |
| 666 | for (j = 0; j < w; j++) { |
| 667 | if (grid[start+j*step] > best) { |
| 668 | best = grid[start+j*step]; |
| 669 | k++; |
| 670 | } |
| 671 | } |
| 672 | clues[i] = k; |
| 673 | } |
| 674 | |
| 675 | /* |
| 676 | * Remove the grid numbers and then the clues, one by one, |
| 677 | * for as long as the game remains soluble at the given |
| 678 | * difficulty. |
| 679 | */ |
| 680 | memcpy(soln, grid, a); |
| 681 | |
| 682 | if (diff == DIFF_EASY && w <= 5) { |
| 683 | /* |
| 684 | * Special case: for Easy-mode grids that are small |
| 685 | * enough, it's nice to be able to find completely empty |
| 686 | * grids. |
| 687 | */ |
| 688 | memset(soln2, 0, a); |
| 689 | ret = solver(w, clues, soln2, diff); |
| 690 | if (ret > diff) |
| 691 | continue; |
| 692 | } |
| 693 | |
| 694 | for (i = 0; i < a; i++) |
| 695 | order[i] = i; |
| 696 | shuffle(order, a, sizeof(*order), rs); |
| 697 | for (i = 0; i < a; i++) { |
| 698 | int j = order[i]; |
| 699 | |
| 700 | memcpy(soln2, grid, a); |
| 701 | soln2[j] = 0; |
| 702 | ret = solver(w, clues, soln2, diff); |
| 703 | if (ret <= diff) |
| 704 | grid[j] = 0; |
| 705 | } |
| 706 | |
| 707 | if (diff > DIFF_EASY) { /* leave all clues on Easy mode */ |
| 708 | for (i = 0; i < 4*w; i++) |
| 709 | order[i] = i; |
| 710 | shuffle(order, 4*w, sizeof(*order), rs); |
| 711 | for (i = 0; i < 4*w; i++) { |
| 712 | int j = order[i]; |
| 713 | int clue = clues[j]; |
| 714 | |
| 715 | memcpy(soln2, grid, a); |
| 716 | clues[j] = 0; |
| 717 | ret = solver(w, clues, soln2, diff); |
| 718 | if (ret > diff) |
| 719 | clues[j] = clue; |
| 720 | } |
| 721 | } |
| 722 | |
| 723 | /* |
| 724 | * See if the game can be solved at the specified difficulty |
| 725 | * level, but not at the one below. |
| 726 | */ |
| 727 | memcpy(soln2, grid, a); |
| 728 | ret = solver(w, clues, soln2, diff); |
| 729 | if (ret != diff) |
| 730 | continue; /* go round again */ |
| 731 | |
| 732 | /* |
| 733 | * We've got a usable puzzle! |
| 734 | */ |
| 735 | break; |
| 736 | } |
| 737 | |
| 738 | /* |
| 739 | * Encode the puzzle description. |
| 740 | */ |
| 741 | desc = snewn(40*a, char); |
| 742 | p = desc; |
| 743 | for (i = 0; i < 4*w; i++) { |
| 744 | p += sprintf(p, "%s%.0d", i?"/":"", clues[i]); |
| 745 | } |
| 746 | for (i = 0; i < a; i++) |
| 747 | if (grid[i]) |
| 748 | break; |
| 749 | if (i < a) { |
| 750 | int run = 0; |
| 751 | |
| 752 | *p++ = ','; |
| 753 | |
| 754 | for (i = 0; i <= a; i++) { |
| 755 | int n = (i < a ? grid[i] : -1); |
| 756 | |
| 757 | if (!n) |
| 758 | run++; |
| 759 | else { |
| 760 | if (run) { |
| 761 | while (run > 0) { |
| 762 | int thisrun = min(run, 26); |
| 763 | *p++ = thisrun - 1 + 'a'; |
| 764 | run -= thisrun; |
| 765 | } |
| 766 | } else { |
| 767 | /* |
| 768 | * If there's a number in the very top left or |
| 769 | * bottom right, there's no point putting an |
| 770 | * unnecessary _ before or after it. |
| 771 | */ |
| 772 | if (i > 0 && n > 0) |
| 773 | *p++ = '_'; |
| 774 | } |
| 775 | if (n > 0) |
| 776 | p += sprintf(p, "%d", n); |
| 777 | run = 0; |
| 778 | } |
| 779 | } |
| 780 | } |
| 781 | *p++ = '\0'; |
| 782 | desc = sresize(desc, p - desc, char); |
| 783 | |
| 784 | /* |
| 785 | * Encode the solution. |
| 786 | */ |
| 787 | *aux = snewn(a+2, char); |
| 788 | (*aux)[0] = 'S'; |
| 789 | for (i = 0; i < a; i++) |
| 790 | (*aux)[i+1] = '0' + soln[i]; |
| 791 | (*aux)[a+1] = '\0'; |
| 792 | |
| 793 | sfree(grid); |
| 794 | sfree(clues); |
| 795 | sfree(soln); |
| 796 | sfree(soln2); |
| 797 | sfree(order); |
| 798 | |
| 799 | return desc; |
| 800 | } |
| 801 | |
| 802 | /* ---------------------------------------------------------------------- |
| 803 | * Gameplay. |
| 804 | */ |
| 805 | |
| 806 | static char *validate_desc(game_params *params, char *desc) |
| 807 | { |
| 808 | int w = params->w, a = w*w; |
| 809 | const char *p = desc; |
| 810 | int i, clue; |
| 811 | |
| 812 | /* |
| 813 | * Verify that the right number of clues are given, and that |
| 814 | * they're in range. |
| 815 | */ |
| 816 | for (i = 0; i < 4*w; i++) { |
| 817 | if (!*p) |
| 818 | return "Too few clues for grid size"; |
| 819 | |
| 820 | if (i > 0) { |
| 821 | if (*p != '/') |
| 822 | return "Expected commas between clues"; |
| 823 | p++; |
| 824 | } |
| 825 | |
| 826 | if (isdigit((unsigned char)*p)) { |
| 827 | clue = atoi(p); |
| 828 | while (*p && isdigit((unsigned char)*p)) p++; |
| 829 | |
| 830 | if (clue <= 0 || clue > w) |
| 831 | return "Clue number out of range"; |
| 832 | } |
| 833 | } |
| 834 | if (*p == '/') |
| 835 | return "Too many clues for grid size"; |
| 836 | |
| 837 | if (*p == ',') { |
| 838 | /* |
| 839 | * Verify that the right amount of grid data is given, and |
| 840 | * that any grid elements provided are in range. |
| 841 | */ |
| 842 | int squares = 0; |
| 843 | |
| 844 | p++; |
| 845 | while (*p) { |
| 846 | int c = *p++; |
| 847 | if (c >= 'a' && c <= 'z') { |
| 848 | squares += c - 'a' + 1; |
| 849 | } else if (c == '_') { |
| 850 | /* do nothing */; |
| 851 | } else if (c > '0' && c <= '9') { |
| 852 | int val = atoi(p-1); |
| 853 | if (val < 1 || val > w) |
| 854 | return "Out-of-range number in grid description"; |
| 855 | squares++; |
| 856 | while (*p && isdigit((unsigned char)*p)) p++; |
| 857 | } else |
| 858 | return "Invalid character in game description"; |
| 859 | } |
| 860 | |
| 861 | if (squares < a) |
| 862 | return "Not enough data to fill grid"; |
| 863 | |
| 864 | if (squares > a) |
| 865 | return "Too much data to fit in grid"; |
| 866 | } |
| 867 | |
| 868 | return NULL; |
| 869 | } |
| 870 | |
| 871 | static game_state *new_game(midend *me, game_params *params, char *desc) |
| 872 | { |
| 873 | int w = params->w, a = w*w; |
| 874 | game_state *state = snew(game_state); |
| 875 | const char *p = desc; |
| 876 | int i; |
| 877 | |
| 878 | state->par = *params; /* structure copy */ |
| 879 | state->clues = snew(struct clues); |
| 880 | state->clues->refcount = 1; |
| 881 | state->clues->w = w; |
| 882 | state->clues->clues = snewn(4*w, int); |
| 883 | state->clues->immutable = snewn(a, digit); |
| 884 | state->grid = snewn(a, digit); |
| 885 | state->pencil = snewn(a, int); |
| 886 | |
| 887 | for (i = 0; i < a; i++) { |
| 888 | state->grid[i] = 0; |
| 889 | state->pencil[i] = 0; |
| 890 | } |
| 891 | |
| 892 | memset(state->clues->immutable, 0, a); |
| 893 | |
| 894 | for (i = 0; i < 4*w; i++) { |
| 895 | if (i > 0) { |
| 896 | assert(*p == '/'); |
| 897 | p++; |
| 898 | } |
| 899 | if (*p && isdigit((unsigned char)*p)) { |
| 900 | state->clues->clues[i] = atoi(p); |
| 901 | while (*p && isdigit((unsigned char)*p)) p++; |
| 902 | } else |
| 903 | state->clues->clues[i] = 0; |
| 904 | } |
| 905 | |
| 906 | if (*p == ',') { |
| 907 | int pos = 0; |
| 908 | p++; |
| 909 | while (*p) { |
| 910 | int c = *p++; |
| 911 | if (c >= 'a' && c <= 'z') { |
| 912 | pos += c - 'a' + 1; |
| 913 | } else if (c == '_') { |
| 914 | /* do nothing */; |
| 915 | } else if (c > '0' && c <= '9') { |
| 916 | int val = atoi(p-1); |
| 917 | assert(val >= 1 && val <= w); |
| 918 | assert(pos < a); |
| 919 | state->grid[pos] = state->clues->immutable[pos] = val; |
| 920 | pos++; |
| 921 | while (*p && isdigit((unsigned char)*p)) p++; |
| 922 | } else |
| 923 | assert(!"Corrupt game description"); |
| 924 | } |
| 925 | assert(pos == a); |
| 926 | } |
| 927 | assert(!*p); |
| 928 | |
| 929 | state->completed = state->cheated = FALSE; |
| 930 | |
| 931 | return state; |
| 932 | } |
| 933 | |
| 934 | static game_state *dup_game(game_state *state) |
| 935 | { |
| 936 | int w = state->par.w, a = w*w; |
| 937 | game_state *ret = snew(game_state); |
| 938 | |
| 939 | ret->par = state->par; /* structure copy */ |
| 940 | |
| 941 | ret->clues = state->clues; |
| 942 | ret->clues->refcount++; |
| 943 | |
| 944 | ret->grid = snewn(a, digit); |
| 945 | ret->pencil = snewn(a, int); |
| 946 | memcpy(ret->grid, state->grid, a*sizeof(digit)); |
| 947 | memcpy(ret->pencil, state->pencil, a*sizeof(int)); |
| 948 | |
| 949 | ret->completed = state->completed; |
| 950 | ret->cheated = state->cheated; |
| 951 | |
| 952 | return ret; |
| 953 | } |
| 954 | |
| 955 | static void free_game(game_state *state) |
| 956 | { |
| 957 | sfree(state->grid); |
| 958 | sfree(state->pencil); |
| 959 | if (--state->clues->refcount <= 0) { |
| 960 | sfree(state->clues->immutable); |
| 961 | sfree(state->clues->clues); |
| 962 | sfree(state->clues); |
| 963 | } |
| 964 | sfree(state); |
| 965 | } |
| 966 | |
| 967 | static char *solve_game(game_state *state, game_state *currstate, |
| 968 | char *aux, char **error) |
| 969 | { |
| 970 | int w = state->par.w, a = w*w; |
| 971 | int i, ret; |
| 972 | digit *soln; |
| 973 | char *out; |
| 974 | |
| 975 | if (aux) |
| 976 | return dupstr(aux); |
| 977 | |
| 978 | soln = snewn(a, digit); |
| 979 | memcpy(soln, state->clues->immutable, a); |
| 980 | |
| 981 | ret = solver(w, state->clues->clues, soln, DIFFCOUNT-1); |
| 982 | |
| 983 | if (ret == diff_impossible) { |
| 984 | *error = "No solution exists for this puzzle"; |
| 985 | out = NULL; |
| 986 | } else if (ret == diff_ambiguous) { |
| 987 | *error = "Multiple solutions exist for this puzzle"; |
| 988 | out = NULL; |
| 989 | } else { |
| 990 | out = snewn(a+2, char); |
| 991 | out[0] = 'S'; |
| 992 | for (i = 0; i < a; i++) |
| 993 | out[i+1] = '0' + soln[i]; |
| 994 | out[a+1] = '\0'; |
| 995 | } |
| 996 | |
| 997 | sfree(soln); |
| 998 | return out; |
| 999 | } |
| 1000 | |
| 1001 | static int game_can_format_as_text_now(game_params *params) |
| 1002 | { |
| 1003 | return TRUE; |
| 1004 | } |
| 1005 | |
| 1006 | static char *game_text_format(game_state *state) |
| 1007 | { |
| 1008 | int w = state->par.w /* , a = w*w */; |
| 1009 | char *ret; |
| 1010 | char *p; |
| 1011 | int x, y; |
| 1012 | int total; |
| 1013 | |
| 1014 | /* |
| 1015 | * We have: |
| 1016 | * - a top clue row, consisting of three spaces, then w clue |
| 1017 | * digits with spaces between (total 2*w+3 chars including |
| 1018 | * newline) |
| 1019 | * - a blank line (one newline) |
| 1020 | * - w main rows, consisting of a left clue digit, two spaces, |
| 1021 | * w grid digits with spaces between, two spaces and a right |
| 1022 | * clue digit (total 2*w+6 chars each including newline) |
| 1023 | * - a blank line (one newline) |
| 1024 | * - a bottom clue row (same as top clue row) |
| 1025 | * - terminating NUL. |
| 1026 | * |
| 1027 | * Total size is therefore 2*(2*w+3) + 2 + w*(2*w+6) + 1 |
| 1028 | * = 2w^2+10w+9. |
| 1029 | */ |
| 1030 | total = 2*w*w + 10*w + 9; |
| 1031 | ret = snewn(total, char); |
| 1032 | p = ret; |
| 1033 | |
| 1034 | /* Top clue row. */ |
| 1035 | *p++ = ' '; *p++ = ' '; |
| 1036 | for (x = 0; x < w; x++) { |
| 1037 | *p++ = ' '; |
| 1038 | *p++ = (state->clues->clues[x] ? '0' + state->clues->clues[x] : ' '); |
| 1039 | } |
| 1040 | *p++ = '\n'; |
| 1041 | |
| 1042 | /* Blank line. */ |
| 1043 | *p++ = '\n'; |
| 1044 | |
| 1045 | /* Main grid. */ |
| 1046 | for (y = 0; y < w; y++) { |
| 1047 | *p++ = (state->clues->clues[y+2*w] ? '0' + state->clues->clues[y+2*w] : |
| 1048 | ' '); |
| 1049 | *p++ = ' '; |
| 1050 | for (x = 0; x < w; x++) { |
| 1051 | *p++ = ' '; |
| 1052 | *p++ = (state->grid[y*w+x] ? '0' + state->grid[y*w+x] : ' '); |
| 1053 | } |
| 1054 | *p++ = ' '; *p++ = ' '; |
| 1055 | *p++ = (state->clues->clues[y+3*w] ? '0' + state->clues->clues[y+3*w] : |
| 1056 | ' '); |
| 1057 | *p++ = '\n'; |
| 1058 | } |
| 1059 | |
| 1060 | /* Blank line. */ |
| 1061 | *p++ = '\n'; |
| 1062 | |
| 1063 | /* Bottom clue row. */ |
| 1064 | *p++ = ' '; *p++ = ' '; |
| 1065 | for (x = 0; x < w; x++) { |
| 1066 | *p++ = ' '; |
| 1067 | *p++ = (state->clues->clues[x+w] ? '0' + state->clues->clues[x+w] : |
| 1068 | ' '); |
| 1069 | } |
| 1070 | *p++ = '\n'; |
| 1071 | |
| 1072 | *p++ = '\0'; |
| 1073 | assert(p == ret + total); |
| 1074 | |
| 1075 | return ret; |
| 1076 | } |
| 1077 | |
| 1078 | struct game_ui { |
| 1079 | /* |
| 1080 | * These are the coordinates of the currently highlighted |
| 1081 | * square on the grid, if hshow = 1. |
| 1082 | */ |
| 1083 | int hx, hy; |
| 1084 | /* |
| 1085 | * This indicates whether the current highlight is a |
| 1086 | * pencil-mark one or a real one. |
| 1087 | */ |
| 1088 | int hpencil; |
| 1089 | /* |
| 1090 | * This indicates whether or not we're showing the highlight |
| 1091 | * (used to be hx = hy = -1); important so that when we're |
| 1092 | * using the cursor keys it doesn't keep coming back at a |
| 1093 | * fixed position. When hshow = 1, pressing a valid number |
| 1094 | * or letter key or Space will enter that number or letter in the grid. |
| 1095 | */ |
| 1096 | int hshow; |
| 1097 | /* |
| 1098 | * This indicates whether we're using the highlight as a cursor; |
| 1099 | * it means that it doesn't vanish on a keypress, and that it is |
| 1100 | * allowed on immutable squares. |
| 1101 | */ |
| 1102 | int hcursor; |
| 1103 | }; |
| 1104 | |
| 1105 | static game_ui *new_ui(game_state *state) |
| 1106 | { |
| 1107 | game_ui *ui = snew(game_ui); |
| 1108 | |
| 1109 | ui->hx = ui->hy = 0; |
| 1110 | ui->hpencil = ui->hshow = ui->hcursor = 0; |
| 1111 | |
| 1112 | return ui; |
| 1113 | } |
| 1114 | |
| 1115 | static void free_ui(game_ui *ui) |
| 1116 | { |
| 1117 | sfree(ui); |
| 1118 | } |
| 1119 | |
| 1120 | static char *encode_ui(game_ui *ui) |
| 1121 | { |
| 1122 | return NULL; |
| 1123 | } |
| 1124 | |
| 1125 | static void decode_ui(game_ui *ui, char *encoding) |
| 1126 | { |
| 1127 | } |
| 1128 | |
| 1129 | static void game_changed_state(game_ui *ui, game_state *oldstate, |
| 1130 | game_state *newstate) |
| 1131 | { |
| 1132 | int w = newstate->par.w; |
| 1133 | /* |
| 1134 | * We prevent pencil-mode highlighting of a filled square, unless |
| 1135 | * we're using the cursor keys. So if the user has just filled in |
| 1136 | * a square which we had a pencil-mode highlight in (by Undo, or |
| 1137 | * by Redo, or by Solve), then we cancel the highlight. |
| 1138 | */ |
| 1139 | if (ui->hshow && ui->hpencil && !ui->hcursor && |
| 1140 | newstate->grid[ui->hy * w + ui->hx] != 0) { |
| 1141 | ui->hshow = 0; |
| 1142 | } |
| 1143 | } |
| 1144 | |
| 1145 | #define PREFERRED_TILESIZE 48 |
| 1146 | #define TILESIZE (ds->tilesize) |
| 1147 | #define BORDER (TILESIZE * 9 / 8) |
| 1148 | #define COORD(x) ((x)*TILESIZE + BORDER) |
| 1149 | #define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1) |
| 1150 | |
| 1151 | /* These always return positive values, though y offsets are actually -ve */ |
| 1152 | #define X_3D_DISP(height, w) ((height) * TILESIZE / (8 * (w))) |
| 1153 | #define Y_3D_DISP(height, w) ((height) * TILESIZE / (4 * (w))) |
| 1154 | |
| 1155 | #define FLASH_TIME 0.4F |
| 1156 | |
| 1157 | #define DF_PENCIL_SHIFT 16 |
| 1158 | #define DF_ERROR 0x8000 |
| 1159 | #define DF_HIGHLIGHT 0x4000 |
| 1160 | #define DF_HIGHLIGHT_PENCIL 0x2000 |
| 1161 | #define DF_IMMUTABLE 0x1000 |
| 1162 | #define DF_PLAYAREA 0x0800 |
| 1163 | #define DF_DIGIT_MASK 0x00FF |
| 1164 | |
| 1165 | struct game_drawstate { |
| 1166 | int tilesize; |
| 1167 | int three_d; /* default 3D graphics are user-disableable */ |
| 1168 | int started; |
| 1169 | long *tiles; /* (w+2)*(w+2) temp space */ |
| 1170 | long *drawn; /* (w+2)*(w+2)*4: current drawn data */ |
| 1171 | int *errtmp; |
| 1172 | }; |
| 1173 | |
| 1174 | static int check_errors(game_state *state, int *errors) |
| 1175 | { |
| 1176 | int w = state->par.w /*, a = w*w */; |
| 1177 | int W = w+2, A = W*W; /* the errors array is (w+2) square */ |
| 1178 | int *clues = state->clues->clues; |
| 1179 | digit *grid = state->grid; |
| 1180 | int i, x, y, errs = FALSE; |
| 1181 | int tmp[32]; |
| 1182 | |
| 1183 | assert(w < lenof(tmp)); |
| 1184 | |
| 1185 | if (errors) |
| 1186 | for (i = 0; i < A; i++) |
| 1187 | errors[i] = 0; |
| 1188 | |
| 1189 | for (y = 0; y < w; y++) { |
| 1190 | unsigned long mask = 0, errmask = 0; |
| 1191 | for (x = 0; x < w; x++) { |
| 1192 | unsigned long bit = 1UL << grid[y*w+x]; |
| 1193 | errmask |= (mask & bit); |
| 1194 | mask |= bit; |
| 1195 | } |
| 1196 | |
| 1197 | if (mask != (1L << (w+1)) - (1L << 1)) { |
| 1198 | errs = TRUE; |
| 1199 | errmask &= ~1UL; |
| 1200 | if (errors) { |
| 1201 | for (x = 0; x < w; x++) |
| 1202 | if (errmask & (1UL << grid[y*w+x])) |
| 1203 | errors[(y+1)*W+(x+1)] = TRUE; |
| 1204 | } |
| 1205 | } |
| 1206 | } |
| 1207 | |
| 1208 | for (x = 0; x < w; x++) { |
| 1209 | unsigned long mask = 0, errmask = 0; |
| 1210 | for (y = 0; y < w; y++) { |
| 1211 | unsigned long bit = 1UL << grid[y*w+x]; |
| 1212 | errmask |= (mask & bit); |
| 1213 | mask |= bit; |
| 1214 | } |
| 1215 | |
| 1216 | if (mask != (1 << (w+1)) - (1 << 1)) { |
| 1217 | errs = TRUE; |
| 1218 | errmask &= ~1UL; |
| 1219 | if (errors) { |
| 1220 | for (y = 0; y < w; y++) |
| 1221 | if (errmask & (1UL << grid[y*w+x])) |
| 1222 | errors[(y+1)*W+(x+1)] = TRUE; |
| 1223 | } |
| 1224 | } |
| 1225 | } |
| 1226 | |
| 1227 | for (i = 0; i < 4*w; i++) { |
| 1228 | int start, step, j, k, n, best; |
| 1229 | STARTSTEP(start, step, i, w); |
| 1230 | |
| 1231 | if (!clues[i]) |
| 1232 | continue; |
| 1233 | |
| 1234 | best = n = 0; |
| 1235 | k = 0; |
| 1236 | for (j = 0; j < w; j++) { |
| 1237 | int number = grid[start+j*step]; |
| 1238 | if (!number) |
| 1239 | break; /* can't tell what happens next */ |
| 1240 | if (number > best) { |
| 1241 | best = number; |
| 1242 | n++; |
| 1243 | } |
| 1244 | } |
| 1245 | |
| 1246 | if (n > clues[i] || (j == w && n < clues[i])) { |
| 1247 | if (errors) { |
| 1248 | int x, y; |
| 1249 | CLUEPOS(x, y, i, w); |
| 1250 | errors[(y+1)*W+(x+1)] = TRUE; |
| 1251 | } |
| 1252 | errs = TRUE; |
| 1253 | } |
| 1254 | } |
| 1255 | |
| 1256 | return errs; |
| 1257 | } |
| 1258 | |
| 1259 | static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, |
| 1260 | int x, int y, int button) |
| 1261 | { |
| 1262 | int w = state->par.w; |
| 1263 | int tx, ty; |
| 1264 | char buf[80]; |
| 1265 | |
| 1266 | button &= ~MOD_MASK; |
| 1267 | |
| 1268 | tx = FROMCOORD(x); |
| 1269 | ty = FROMCOORD(y); |
| 1270 | |
| 1271 | if (ds->three_d) { |
| 1272 | /* |
| 1273 | * In 3D mode, just locating the mouse click in the natural |
| 1274 | * square grid may not be sufficient to tell which tower the |
| 1275 | * user clicked on. Investigate the _tops_ of the nearby |
| 1276 | * towers to see if a click on one grid square was actually |
| 1277 | * a click on a tower protruding into that region from |
| 1278 | * another. |
| 1279 | */ |
| 1280 | int dx, dy; |
| 1281 | for (dy = 0; dy <= 1; dy++) |
| 1282 | for (dx = 0; dx >= -1; dx--) { |
| 1283 | int cx = tx + dx, cy = ty + dy; |
| 1284 | if (cx >= 0 && cx < w && cy >= 0 && cy < w) { |
| 1285 | int height = state->grid[cy*w+cx]; |
| 1286 | int bx = COORD(cx), by = COORD(cy); |
| 1287 | int ox = bx + X_3D_DISP(height, w); |
| 1288 | int oy = by - Y_3D_DISP(height, w); |
| 1289 | if (/* on top face? */ |
| 1290 | (x - ox >= 0 && x - ox < TILESIZE && |
| 1291 | y - oy >= 0 && y - oy < TILESIZE) || |
| 1292 | /* in triangle between top-left corners? */ |
| 1293 | (ox > bx && x >= bx && x <= ox && y <= by && |
| 1294 | (by-y) * (ox-bx) <= (by-oy) * (x-bx)) || |
| 1295 | /* in triangle between bottom-right corners? */ |
| 1296 | (ox > bx && x >= bx+TILESIZE && x <= ox+TILESIZE && |
| 1297 | y >= oy+TILESIZE && |
| 1298 | (by-y+TILESIZE)*(ox-bx) >= (by-oy)*(x-bx-TILESIZE))) { |
| 1299 | tx = cx; |
| 1300 | ty = cy; |
| 1301 | } |
| 1302 | } |
| 1303 | } |
| 1304 | } |
| 1305 | |
| 1306 | if (tx >= 0 && tx < w && ty >= 0 && ty < w) { |
| 1307 | if (button == LEFT_BUTTON) { |
| 1308 | if (tx == ui->hx && ty == ui->hy && |
| 1309 | ui->hshow && ui->hpencil == 0) { |
| 1310 | ui->hshow = 0; |
| 1311 | } else { |
| 1312 | ui->hx = tx; |
| 1313 | ui->hy = ty; |
| 1314 | ui->hshow = !state->clues->immutable[ty*w+tx]; |
| 1315 | ui->hpencil = 0; |
| 1316 | } |
| 1317 | ui->hcursor = 0; |
| 1318 | return ""; /* UI activity occurred */ |
| 1319 | } |
| 1320 | if (button == RIGHT_BUTTON) { |
| 1321 | /* |
| 1322 | * Pencil-mode highlighting for non filled squares. |
| 1323 | */ |
| 1324 | if (state->grid[ty*w+tx] == 0) { |
| 1325 | if (tx == ui->hx && ty == ui->hy && |
| 1326 | ui->hshow && ui->hpencil) { |
| 1327 | ui->hshow = 0; |
| 1328 | } else { |
| 1329 | ui->hpencil = 1; |
| 1330 | ui->hx = tx; |
| 1331 | ui->hy = ty; |
| 1332 | ui->hshow = 1; |
| 1333 | } |
| 1334 | } else { |
| 1335 | ui->hshow = 0; |
| 1336 | } |
| 1337 | ui->hcursor = 0; |
| 1338 | return ""; /* UI activity occurred */ |
| 1339 | } |
| 1340 | } |
| 1341 | if (IS_CURSOR_MOVE(button)) { |
| 1342 | move_cursor(button, &ui->hx, &ui->hy, w, w, 0); |
| 1343 | ui->hshow = ui->hcursor = 1; |
| 1344 | return ""; |
| 1345 | } |
| 1346 | if (ui->hshow && |
| 1347 | (button == CURSOR_SELECT)) { |
| 1348 | ui->hpencil = 1 - ui->hpencil; |
| 1349 | ui->hcursor = 1; |
| 1350 | return ""; |
| 1351 | } |
| 1352 | |
| 1353 | if (ui->hshow && |
| 1354 | ((button >= '0' && button <= '9' && button - '0' <= w) || |
| 1355 | button == CURSOR_SELECT2 || button == '\b')) { |
| 1356 | int n = button - '0'; |
| 1357 | if (button == CURSOR_SELECT2 || button == '\b') |
| 1358 | n = 0; |
| 1359 | |
| 1360 | /* |
| 1361 | * Can't make pencil marks in a filled square. This can only |
| 1362 | * become highlighted if we're using cursor keys. |
| 1363 | */ |
| 1364 | if (ui->hpencil && state->grid[ui->hy*w+ui->hx]) |
| 1365 | return NULL; |
| 1366 | |
| 1367 | /* |
| 1368 | * Can't do anything to an immutable square. |
| 1369 | */ |
| 1370 | if (state->clues->immutable[ui->hy*w+ui->hx]) |
| 1371 | return NULL; |
| 1372 | |
| 1373 | sprintf(buf, "%c%d,%d,%d", |
| 1374 | (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n); |
| 1375 | |
| 1376 | if (!ui->hcursor) ui->hshow = 0; |
| 1377 | |
| 1378 | return dupstr(buf); |
| 1379 | } |
| 1380 | |
| 1381 | if (button == 'M' || button == 'm') |
| 1382 | return dupstr("M"); |
| 1383 | |
| 1384 | return NULL; |
| 1385 | } |
| 1386 | |
| 1387 | static game_state *execute_move(game_state *from, char *move) |
| 1388 | { |
| 1389 | int w = from->par.w, a = w*w; |
| 1390 | game_state *ret; |
| 1391 | int x, y, i, n; |
| 1392 | |
| 1393 | if (move[0] == 'S') { |
| 1394 | ret = dup_game(from); |
| 1395 | ret->completed = ret->cheated = TRUE; |
| 1396 | |
| 1397 | for (i = 0; i < a; i++) { |
| 1398 | if (move[i+1] < '1' || move[i+1] > '0'+w) { |
| 1399 | free_game(ret); |
| 1400 | return NULL; |
| 1401 | } |
| 1402 | ret->grid[i] = move[i+1] - '0'; |
| 1403 | ret->pencil[i] = 0; |
| 1404 | } |
| 1405 | |
| 1406 | if (move[a+1] != '\0') { |
| 1407 | free_game(ret); |
| 1408 | return NULL; |
| 1409 | } |
| 1410 | |
| 1411 | return ret; |
| 1412 | } else if ((move[0] == 'P' || move[0] == 'R') && |
| 1413 | sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 && |
| 1414 | x >= 0 && x < w && y >= 0 && y < w && n >= 0 && n <= w) { |
| 1415 | if (from->clues->immutable[y*w+x]) |
| 1416 | return NULL; |
| 1417 | |
| 1418 | ret = dup_game(from); |
| 1419 | if (move[0] == 'P' && n > 0) { |
| 1420 | ret->pencil[y*w+x] ^= 1L << n; |
| 1421 | } else { |
| 1422 | ret->grid[y*w+x] = n; |
| 1423 | ret->pencil[y*w+x] = 0; |
| 1424 | |
| 1425 | if (!ret->completed && !check_errors(ret, NULL)) |
| 1426 | ret->completed = TRUE; |
| 1427 | } |
| 1428 | return ret; |
| 1429 | } else if (move[0] == 'M') { |
| 1430 | /* |
| 1431 | * Fill in absolutely all pencil marks everywhere. (I |
| 1432 | * wouldn't use this for actual play, but it's a handy |
| 1433 | * starting point when following through a set of |
| 1434 | * diagnostics output by the standalone solver.) |
| 1435 | */ |
| 1436 | ret = dup_game(from); |
| 1437 | for (i = 0; i < a; i++) { |
| 1438 | if (!ret->grid[i]) |
| 1439 | ret->pencil[i] = (1L << (w+1)) - (1L << 1); |
| 1440 | } |
| 1441 | return ret; |
| 1442 | } else |
| 1443 | return NULL; /* couldn't parse move string */ |
| 1444 | } |
| 1445 | |
| 1446 | /* ---------------------------------------------------------------------- |
| 1447 | * Drawing routines. |
| 1448 | */ |
| 1449 | |
| 1450 | #define SIZE(w) ((w) * TILESIZE + 2*BORDER) |
| 1451 | |
| 1452 | static void game_compute_size(game_params *params, int tilesize, |
| 1453 | int *x, int *y) |
| 1454 | { |
| 1455 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ |
| 1456 | struct { int tilesize; } ads, *ds = &ads; |
| 1457 | ads.tilesize = tilesize; |
| 1458 | |
| 1459 | *x = *y = SIZE(params->w); |
| 1460 | } |
| 1461 | |
| 1462 | static void game_set_size(drawing *dr, game_drawstate *ds, |
| 1463 | game_params *params, int tilesize) |
| 1464 | { |
| 1465 | ds->tilesize = tilesize; |
| 1466 | } |
| 1467 | |
| 1468 | static float *game_colours(frontend *fe, int *ncolours) |
| 1469 | { |
| 1470 | float *ret = snewn(3 * NCOLOURS, float); |
| 1471 | |
| 1472 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); |
| 1473 | |
| 1474 | ret[COL_GRID * 3 + 0] = 0.0F; |
| 1475 | ret[COL_GRID * 3 + 1] = 0.0F; |
| 1476 | ret[COL_GRID * 3 + 2] = 0.0F; |
| 1477 | |
| 1478 | ret[COL_USER * 3 + 0] = 0.0F; |
| 1479 | ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1]; |
| 1480 | ret[COL_USER * 3 + 2] = 0.0F; |
| 1481 | |
| 1482 | ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0]; |
| 1483 | ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1]; |
| 1484 | ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2]; |
| 1485 | |
| 1486 | ret[COL_ERROR * 3 + 0] = 1.0F; |
| 1487 | ret[COL_ERROR * 3 + 1] = 0.0F; |
| 1488 | ret[COL_ERROR * 3 + 2] = 0.0F; |
| 1489 | |
| 1490 | ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; |
| 1491 | ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; |
| 1492 | ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2]; |
| 1493 | |
| 1494 | *ncolours = NCOLOURS; |
| 1495 | return ret; |
| 1496 | } |
| 1497 | |
| 1498 | static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) |
| 1499 | { |
| 1500 | int w = state->par.w /*, a = w*w */; |
| 1501 | struct game_drawstate *ds = snew(struct game_drawstate); |
| 1502 | int i; |
| 1503 | |
| 1504 | ds->tilesize = 0; |
| 1505 | ds->three_d = !getenv("TOWERS_2D"); |
| 1506 | ds->started = FALSE; |
| 1507 | ds->tiles = snewn((w+2)*(w+2), long); |
| 1508 | ds->drawn = snewn((w+2)*(w+2)*4, long); |
| 1509 | for (i = 0; i < (w+2)*(w+2)*4; i++) |
| 1510 | ds->drawn[i] = -1; |
| 1511 | ds->errtmp = snewn((w+2)*(w+2), int); |
| 1512 | |
| 1513 | return ds; |
| 1514 | } |
| 1515 | |
| 1516 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) |
| 1517 | { |
| 1518 | sfree(ds->errtmp); |
| 1519 | sfree(ds->tiles); |
| 1520 | sfree(ds->drawn); |
| 1521 | sfree(ds); |
| 1522 | } |
| 1523 | |
| 1524 | static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, |
| 1525 | int x, int y, long tile) |
| 1526 | { |
| 1527 | int w = clues->w /* , a = w*w */; |
| 1528 | int tx, ty, bg; |
| 1529 | char str[64]; |
| 1530 | |
| 1531 | tx = COORD(x); |
| 1532 | ty = COORD(y); |
| 1533 | |
| 1534 | bg = (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND; |
| 1535 | |
| 1536 | /* draw tower */ |
| 1537 | if (ds->three_d && (tile & DF_PLAYAREA) && (tile & DF_DIGIT_MASK)) { |
| 1538 | int coords[8]; |
| 1539 | int xoff = X_3D_DISP(tile & DF_DIGIT_MASK, w); |
| 1540 | int yoff = Y_3D_DISP(tile & DF_DIGIT_MASK, w); |
| 1541 | |
| 1542 | /* left face of tower */ |
| 1543 | coords[0] = tx; |
| 1544 | coords[1] = ty - 1; |
| 1545 | coords[2] = tx; |
| 1546 | coords[3] = ty + TILESIZE - 1; |
| 1547 | coords[4] = coords[2] + xoff; |
| 1548 | coords[5] = coords[3] - yoff; |
| 1549 | coords[6] = coords[0] + xoff; |
| 1550 | coords[7] = coords[1] - yoff; |
| 1551 | draw_polygon(dr, coords, 4, bg, COL_GRID); |
| 1552 | |
| 1553 | /* bottom face of tower */ |
| 1554 | coords[0] = tx + TILESIZE; |
| 1555 | coords[1] = ty + TILESIZE - 1; |
| 1556 | coords[2] = tx; |
| 1557 | coords[3] = ty + TILESIZE - 1; |
| 1558 | coords[4] = coords[2] + xoff; |
| 1559 | coords[5] = coords[3] - yoff; |
| 1560 | coords[6] = coords[0] + xoff; |
| 1561 | coords[7] = coords[1] - yoff; |
| 1562 | draw_polygon(dr, coords, 4, bg, COL_GRID); |
| 1563 | |
| 1564 | /* now offset all subsequent drawing to the top of the tower */ |
| 1565 | tx += xoff; |
| 1566 | ty -= yoff; |
| 1567 | } |
| 1568 | |
| 1569 | /* erase background */ |
| 1570 | draw_rect(dr, tx, ty, TILESIZE, TILESIZE, bg); |
| 1571 | |
| 1572 | /* pencil-mode highlight */ |
| 1573 | if (tile & DF_HIGHLIGHT_PENCIL) { |
| 1574 | int coords[6]; |
| 1575 | coords[0] = tx; |
| 1576 | coords[1] = ty; |
| 1577 | coords[2] = tx+TILESIZE/2; |
| 1578 | coords[3] = ty; |
| 1579 | coords[4] = tx; |
| 1580 | coords[5] = ty+TILESIZE/2; |
| 1581 | draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); |
| 1582 | } |
| 1583 | |
| 1584 | /* draw box outline */ |
| 1585 | if (tile & DF_PLAYAREA) { |
| 1586 | int coords[8]; |
| 1587 | coords[0] = tx; |
| 1588 | coords[1] = ty - 1; |
| 1589 | coords[2] = tx + TILESIZE; |
| 1590 | coords[3] = ty - 1; |
| 1591 | coords[4] = tx + TILESIZE; |
| 1592 | coords[5] = ty + TILESIZE - 1; |
| 1593 | coords[6] = tx; |
| 1594 | coords[7] = ty + TILESIZE - 1; |
| 1595 | draw_polygon(dr, coords, 4, -1, COL_GRID); |
| 1596 | } |
| 1597 | |
| 1598 | /* new number needs drawing? */ |
| 1599 | if (tile & DF_DIGIT_MASK) { |
| 1600 | str[1] = '\0'; |
| 1601 | str[0] = (tile & DF_DIGIT_MASK) + '0'; |
| 1602 | draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2, FONT_VARIABLE, |
| 1603 | (tile & DF_PLAYAREA ? TILESIZE/2 : TILESIZE*2/5), |
| 1604 | ALIGN_VCENTRE | ALIGN_HCENTRE, |
| 1605 | (tile & DF_ERROR) ? COL_ERROR : |
| 1606 | (x < 0 || y < 0 || x >= w || y >= w) ? COL_GRID : |
| 1607 | (tile & DF_IMMUTABLE) ? COL_GRID : COL_USER, str); |
| 1608 | } else { |
| 1609 | int i, j, npencil; |
| 1610 | int pl, pr, pt, pb; |
| 1611 | float bestsize; |
| 1612 | int pw, ph, minph, pbest, fontsize; |
| 1613 | |
| 1614 | /* Count the pencil marks required. */ |
| 1615 | for (i = 1, npencil = 0; i <= w; i++) |
| 1616 | if (tile & (1L << (i + DF_PENCIL_SHIFT))) |
| 1617 | npencil++; |
| 1618 | if (npencil) { |
| 1619 | |
| 1620 | minph = 2; |
| 1621 | |
| 1622 | /* |
| 1623 | * Determine the bounding rectangle within which we're going |
| 1624 | * to put the pencil marks. |
| 1625 | */ |
| 1626 | /* Start with the whole square, minus space for impinging towers */ |
| 1627 | pl = tx + (ds->three_d ? X_3D_DISP(w,w) : 0); |
| 1628 | pr = tx + TILESIZE; |
| 1629 | pt = ty; |
| 1630 | pb = ty + TILESIZE - (ds->three_d ? Y_3D_DISP(w,w) : 0); |
| 1631 | |
| 1632 | /* |
| 1633 | * We arrange our pencil marks in a grid layout, with |
| 1634 | * the number of rows and columns adjusted to allow the |
| 1635 | * maximum font size. |
| 1636 | * |
| 1637 | * So now we work out what the grid size ought to be. |
| 1638 | */ |
| 1639 | bestsize = 0.0; |
| 1640 | pbest = 0; |
| 1641 | /* Minimum */ |
| 1642 | for (pw = 3; pw < max(npencil,4); pw++) { |
| 1643 | float fw, fh, fs; |
| 1644 | |
| 1645 | ph = (npencil + pw - 1) / pw; |
| 1646 | ph = max(ph, minph); |
| 1647 | fw = (pr - pl) / (float)pw; |
| 1648 | fh = (pb - pt) / (float)ph; |
| 1649 | fs = min(fw, fh); |
| 1650 | if (fs > bestsize) { |
| 1651 | bestsize = fs; |
| 1652 | pbest = pw; |
| 1653 | } |
| 1654 | } |
| 1655 | assert(pbest > 0); |
| 1656 | pw = pbest; |
| 1657 | ph = (npencil + pw - 1) / pw; |
| 1658 | ph = max(ph, minph); |
| 1659 | |
| 1660 | /* |
| 1661 | * Now we've got our grid dimensions, work out the pixel |
| 1662 | * size of a grid element, and round it to the nearest |
| 1663 | * pixel. (We don't want rounding errors to make the |
| 1664 | * grid look uneven at low pixel sizes.) |
| 1665 | */ |
| 1666 | fontsize = min((pr - pl) / pw, (pb - pt) / ph); |
| 1667 | |
| 1668 | /* |
| 1669 | * Centre the resulting figure in the square. |
| 1670 | */ |
| 1671 | pl = pl + (pr - pl - fontsize * pw) / 2; |
| 1672 | pt = pt + (pb - pt - fontsize * ph) / 2; |
| 1673 | |
| 1674 | /* |
| 1675 | * Now actually draw the pencil marks. |
| 1676 | */ |
| 1677 | for (i = 1, j = 0; i <= w; i++) |
| 1678 | if (tile & (1L << (i + DF_PENCIL_SHIFT))) { |
| 1679 | int dx = j % pw, dy = j / pw; |
| 1680 | |
| 1681 | str[1] = '\0'; |
| 1682 | str[0] = i + '0'; |
| 1683 | draw_text(dr, pl + fontsize * (2*dx+1) / 2, |
| 1684 | pt + fontsize * (2*dy+1) / 2, |
| 1685 | FONT_VARIABLE, fontsize, |
| 1686 | ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str); |
| 1687 | j++; |
| 1688 | } |
| 1689 | } |
| 1690 | } |
| 1691 | } |
| 1692 | |
| 1693 | static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, |
| 1694 | game_state *state, int dir, game_ui *ui, |
| 1695 | float animtime, float flashtime) |
| 1696 | { |
| 1697 | int w = state->par.w /*, a = w*w */; |
| 1698 | int i, x, y; |
| 1699 | |
| 1700 | if (!ds->started) { |
| 1701 | /* |
| 1702 | * The initial contents of the window are not guaranteed and |
| 1703 | * can vary with front ends. To be on the safe side, all |
| 1704 | * games should start by drawing a big background-colour |
| 1705 | * rectangle covering the whole window. |
| 1706 | */ |
| 1707 | draw_rect(dr, 0, 0, SIZE(w), SIZE(w), COL_BACKGROUND); |
| 1708 | |
| 1709 | draw_update(dr, 0, 0, SIZE(w), SIZE(w)); |
| 1710 | |
| 1711 | ds->started = TRUE; |
| 1712 | } |
| 1713 | |
| 1714 | check_errors(state, ds->errtmp); |
| 1715 | |
| 1716 | /* |
| 1717 | * Work out what data each tile should contain. |
| 1718 | */ |
| 1719 | for (i = 0; i < (w+2)*(w+2); i++) |
| 1720 | ds->tiles[i] = 0; /* completely blank square */ |
| 1721 | /* The clue squares... */ |
| 1722 | for (i = 0; i < 4*w; i++) { |
| 1723 | long tile = state->clues->clues[i]; |
| 1724 | |
| 1725 | CLUEPOS(x, y, i, w); |
| 1726 | |
| 1727 | if (ds->errtmp[(y+1)*(w+2)+(x+1)]) |
| 1728 | tile |= DF_ERROR; |
| 1729 | |
| 1730 | ds->tiles[(y+1)*(w+2)+(x+1)] = tile; |
| 1731 | } |
| 1732 | /* ... and the main grid. */ |
| 1733 | for (y = 0; y < w; y++) { |
| 1734 | for (x = 0; x < w; x++) { |
| 1735 | long tile = DF_PLAYAREA; |
| 1736 | |
| 1737 | if (state->grid[y*w+x]) |
| 1738 | tile |= state->grid[y*w+x]; |
| 1739 | else |
| 1740 | tile |= (long)state->pencil[y*w+x] << DF_PENCIL_SHIFT; |
| 1741 | |
| 1742 | if (ui->hshow && ui->hx == x && ui->hy == y) |
| 1743 | tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT); |
| 1744 | |
| 1745 | if (state->clues->immutable[y*w+x]) |
| 1746 | tile |= DF_IMMUTABLE; |
| 1747 | |
| 1748 | if (flashtime > 0 && |
| 1749 | (flashtime <= FLASH_TIME/3 || |
| 1750 | flashtime >= FLASH_TIME*2/3)) |
| 1751 | tile |= DF_HIGHLIGHT; /* completion flash */ |
| 1752 | |
| 1753 | if (ds->errtmp[(y+1)*(w+2)+(x+1)]) |
| 1754 | tile |= DF_ERROR; |
| 1755 | |
| 1756 | ds->tiles[(y+1)*(w+2)+(x+1)] = tile; |
| 1757 | } |
| 1758 | } |
| 1759 | |
| 1760 | /* |
| 1761 | * Now actually draw anything that needs to be changed. |
| 1762 | */ |
| 1763 | for (y = 0; y < w+2; y++) { |
| 1764 | for (x = 0; x < w+2; x++) { |
| 1765 | long tl, tr, bl, br; |
| 1766 | int i = y*(w+2)+x; |
| 1767 | |
| 1768 | tr = ds->tiles[y*(w+2)+x]; |
| 1769 | tl = (x == 0 ? 0 : ds->tiles[y*(w+2)+(x-1)]); |
| 1770 | br = (y == w+1 ? 0 : ds->tiles[(y+1)*(w+2)+x]); |
| 1771 | bl = (x == 0 || y == w+1 ? 0 : ds->tiles[(y+1)*(w+2)+(x-1)]); |
| 1772 | |
| 1773 | if (ds->drawn[i*4] != tl || ds->drawn[i*4+1] != tr || |
| 1774 | ds->drawn[i*4+2] != bl || ds->drawn[i*4+3] != br) { |
| 1775 | clip(dr, COORD(x-1), COORD(y-1), TILESIZE, TILESIZE); |
| 1776 | |
| 1777 | draw_tile(dr, ds, state->clues, x-1, y-1, tr); |
| 1778 | if (x > 0) |
| 1779 | draw_tile(dr, ds, state->clues, x-2, y-1, tl); |
| 1780 | if (y <= w) |
| 1781 | draw_tile(dr, ds, state->clues, x-1, y, br); |
| 1782 | if (x > 0 && y <= w) |
| 1783 | draw_tile(dr, ds, state->clues, x-2, y, bl); |
| 1784 | |
| 1785 | unclip(dr); |
| 1786 | draw_update(dr, COORD(x-1), COORD(y-1), TILESIZE, TILESIZE); |
| 1787 | |
| 1788 | ds->drawn[i*4] = tl; |
| 1789 | ds->drawn[i*4+1] = tr; |
| 1790 | ds->drawn[i*4+2] = bl; |
| 1791 | ds->drawn[i*4+3] = br; |
| 1792 | } |
| 1793 | } |
| 1794 | } |
| 1795 | } |
| 1796 | |
| 1797 | static float game_anim_length(game_state *oldstate, game_state *newstate, |
| 1798 | int dir, game_ui *ui) |
| 1799 | { |
| 1800 | return 0.0F; |
| 1801 | } |
| 1802 | |
| 1803 | static float game_flash_length(game_state *oldstate, game_state *newstate, |
| 1804 | int dir, game_ui *ui) |
| 1805 | { |
| 1806 | if (!oldstate->completed && newstate->completed && |
| 1807 | !oldstate->cheated && !newstate->cheated) |
| 1808 | return FLASH_TIME; |
| 1809 | return 0.0F; |
| 1810 | } |
| 1811 | |
| 1812 | static int game_timing_state(game_state *state, game_ui *ui) |
| 1813 | { |
| 1814 | if (state->completed) |
| 1815 | return FALSE; |
| 1816 | return TRUE; |
| 1817 | } |
| 1818 | |
| 1819 | static void game_print_size(game_params *params, float *x, float *y) |
| 1820 | { |
| 1821 | int pw, ph; |
| 1822 | |
| 1823 | /* |
| 1824 | * We use 9mm squares by default, like Solo. |
| 1825 | */ |
| 1826 | game_compute_size(params, 900, &pw, &ph); |
| 1827 | *x = pw / 100.0F; |
| 1828 | *y = ph / 100.0F; |
| 1829 | } |
| 1830 | |
| 1831 | static void game_print(drawing *dr, game_state *state, int tilesize) |
| 1832 | { |
| 1833 | int w = state->par.w; |
| 1834 | int ink = print_mono_colour(dr, 0); |
| 1835 | int i, x, y; |
| 1836 | |
| 1837 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ |
| 1838 | game_drawstate ads, *ds = &ads; |
| 1839 | game_set_size(dr, ds, NULL, tilesize); |
| 1840 | |
| 1841 | /* |
| 1842 | * Border. |
| 1843 | */ |
| 1844 | print_line_width(dr, 3 * TILESIZE / 40); |
| 1845 | draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, w*TILESIZE, ink); |
| 1846 | |
| 1847 | /* |
| 1848 | * Main grid. |
| 1849 | */ |
| 1850 | for (x = 1; x < w; x++) { |
| 1851 | print_line_width(dr, TILESIZE / 40); |
| 1852 | draw_line(dr, BORDER+x*TILESIZE, BORDER, |
| 1853 | BORDER+x*TILESIZE, BORDER+w*TILESIZE, ink); |
| 1854 | } |
| 1855 | for (y = 1; y < w; y++) { |
| 1856 | print_line_width(dr, TILESIZE / 40); |
| 1857 | draw_line(dr, BORDER, BORDER+y*TILESIZE, |
| 1858 | BORDER+w*TILESIZE, BORDER+y*TILESIZE, ink); |
| 1859 | } |
| 1860 | |
| 1861 | /* |
| 1862 | * Clues. |
| 1863 | */ |
| 1864 | for (i = 0; i < 4*w; i++) { |
| 1865 | char str[128]; |
| 1866 | |
| 1867 | if (!state->clues->clues[i]) |
| 1868 | continue; |
| 1869 | |
| 1870 | CLUEPOS(x, y, i, w); |
| 1871 | |
| 1872 | sprintf (str, "%d", state->clues->clues[i]); |
| 1873 | |
| 1874 | draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2, |
| 1875 | BORDER + y*TILESIZE + TILESIZE/2, |
| 1876 | FONT_VARIABLE, TILESIZE/2, |
| 1877 | ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); |
| 1878 | } |
| 1879 | |
| 1880 | /* |
| 1881 | * Numbers for the solution, if any. |
| 1882 | */ |
| 1883 | for (y = 0; y < w; y++) |
| 1884 | for (x = 0; x < w; x++) |
| 1885 | if (state->grid[y*w+x]) { |
| 1886 | char str[2]; |
| 1887 | str[1] = '\0'; |
| 1888 | str[0] = state->grid[y*w+x] + '0'; |
| 1889 | draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2, |
| 1890 | BORDER + y*TILESIZE + TILESIZE/2, |
| 1891 | FONT_VARIABLE, TILESIZE/2, |
| 1892 | ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); |
| 1893 | } |
| 1894 | } |
| 1895 | |
| 1896 | #ifdef COMBINED |
| 1897 | #define thegame towers |
| 1898 | #endif |
| 1899 | |
| 1900 | const struct game thegame = { |
| 1901 | "Towers", "games.towers", "towers", |
| 1902 | default_params, |
| 1903 | game_fetch_preset, |
| 1904 | decode_params, |
| 1905 | encode_params, |
| 1906 | free_params, |
| 1907 | dup_params, |
| 1908 | TRUE, game_configure, custom_params, |
| 1909 | validate_params, |
| 1910 | new_game_desc, |
| 1911 | validate_desc, |
| 1912 | new_game, |
| 1913 | dup_game, |
| 1914 | free_game, |
| 1915 | TRUE, solve_game, |
| 1916 | TRUE, game_can_format_as_text_now, game_text_format, |
| 1917 | new_ui, |
| 1918 | free_ui, |
| 1919 | encode_ui, |
| 1920 | decode_ui, |
| 1921 | game_changed_state, |
| 1922 | interpret_move, |
| 1923 | execute_move, |
| 1924 | PREFERRED_TILESIZE, game_compute_size, game_set_size, |
| 1925 | game_colours, |
| 1926 | game_new_drawstate, |
| 1927 | game_free_drawstate, |
| 1928 | game_redraw, |
| 1929 | game_anim_length, |
| 1930 | game_flash_length, |
| 1931 | TRUE, FALSE, game_print_size, game_print, |
| 1932 | FALSE, /* wants_statusbar */ |
| 1933 | FALSE, game_timing_state, |
| 1934 | REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */ |
| 1935 | }; |
| 1936 | |
| 1937 | #ifdef STANDALONE_SOLVER |
| 1938 | |
| 1939 | #include <stdarg.h> |
| 1940 | |
| 1941 | int main(int argc, char **argv) |
| 1942 | { |
| 1943 | game_params *p; |
| 1944 | game_state *s; |
| 1945 | char *id = NULL, *desc, *err; |
| 1946 | int grade = FALSE; |
| 1947 | int ret, diff, really_show_working = FALSE; |
| 1948 | |
| 1949 | while (--argc > 0) { |
| 1950 | char *p = *++argv; |
| 1951 | if (!strcmp(p, "-v")) { |
| 1952 | really_show_working = TRUE; |
| 1953 | } else if (!strcmp(p, "-g")) { |
| 1954 | grade = TRUE; |
| 1955 | } else if (*p == '-') { |
| 1956 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); |
| 1957 | return 1; |
| 1958 | } else { |
| 1959 | id = p; |
| 1960 | } |
| 1961 | } |
| 1962 | |
| 1963 | if (!id) { |
| 1964 | fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]); |
| 1965 | return 1; |
| 1966 | } |
| 1967 | |
| 1968 | desc = strchr(id, ':'); |
| 1969 | if (!desc) { |
| 1970 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); |
| 1971 | return 1; |
| 1972 | } |
| 1973 | *desc++ = '\0'; |
| 1974 | |
| 1975 | p = default_params(); |
| 1976 | decode_params(p, id); |
| 1977 | err = validate_desc(p, desc); |
| 1978 | if (err) { |
| 1979 | fprintf(stderr, "%s: %s\n", argv[0], err); |
| 1980 | return 1; |
| 1981 | } |
| 1982 | s = new_game(NULL, p, desc); |
| 1983 | |
| 1984 | /* |
| 1985 | * When solving an Easy puzzle, we don't want to bother the |
| 1986 | * user with Hard-level deductions. For this reason, we grade |
| 1987 | * the puzzle internally before doing anything else. |
| 1988 | */ |
| 1989 | ret = -1; /* placate optimiser */ |
| 1990 | solver_show_working = FALSE; |
| 1991 | for (diff = 0; diff < DIFFCOUNT; diff++) { |
| 1992 | memcpy(s->grid, s->clues->immutable, p->w * p->w); |
| 1993 | ret = solver(p->w, s->clues->clues, s->grid, diff); |
| 1994 | if (ret <= diff) |
| 1995 | break; |
| 1996 | } |
| 1997 | |
| 1998 | if (diff == DIFFCOUNT) { |
| 1999 | if (grade) |
| 2000 | printf("Difficulty rating: ambiguous\n"); |
| 2001 | else |
| 2002 | printf("Unable to find a unique solution\n"); |
| 2003 | } else { |
| 2004 | if (grade) { |
| 2005 | if (ret == diff_impossible) |
| 2006 | printf("Difficulty rating: impossible (no solution exists)\n"); |
| 2007 | else |
| 2008 | printf("Difficulty rating: %s\n", towers_diffnames[ret]); |
| 2009 | } else { |
| 2010 | solver_show_working = really_show_working; |
| 2011 | memcpy(s->grid, s->clues->immutable, p->w * p->w); |
| 2012 | ret = solver(p->w, s->clues->clues, s->grid, diff); |
| 2013 | if (ret != diff) |
| 2014 | printf("Puzzle is inconsistent\n"); |
| 2015 | else |
| 2016 | fputs(game_text_format(s), stdout); |
| 2017 | } |
| 2018 | } |
| 2019 | |
| 2020 | return 0; |
| 2021 | } |
| 2022 | |
| 2023 | #endif |
| 2024 | |
| 2025 | /* vim: set shiftwidth=4 tabstop=8: */ |