343
344
int verbose = FALSE;
346
static void do_recurse(unsigned char *known, unsigned char *deduced,
347
unsigned char *row, int *data, int len,
347
static int do_recurse(unsigned char *known, unsigned char *deduced,
349
unsigned char *minpos_done, unsigned char *maxpos_done,
350
unsigned char *minpos_ok, unsigned char *maxpos_ok,
348
352
int freespace, int ndone, int lowest)
357
/* This algorithm basically tries all possible ways the given rows of
358
* black blocks can be laid out in the row/column being examined.
359
* Special care is taken to avoid checking the tail of a row/column
360
* if the same conditions have already been checked during this recursion
361
* The algorithm also takes care to cut its losses as soon as an
362
* invalid (partial) solution is detected.
352
364
if (data[ndone]) {
365
if (lowest >= minpos_done[ndone] && lowest <= maxpos_done[ndone]) {
366
if (lowest >= minpos_ok[ndone] && lowest <= maxpos_ok[ndone]) {
367
for (i=0; i<lowest; i++)
368
deduced[i] |= row[i];
370
return lowest >= minpos_ok[ndone] && lowest <= maxpos_ok[ndone];
372
if (lowest < minpos_done[ndone]) minpos_done[ndone] = lowest;
373
if (lowest > maxpos_done[ndone]) maxpos_done[ndone] = lowest;
353
375
for (i=0; i<=freespace; i++) {
355
for (k=0; k<i; k++) row[j++] = DOT;
356
for (k=0; k<data[ndone]; k++) row[j++] = BLOCK;
357
if (j < len) row[j++] = DOT;
358
do_recurse(known, deduced, row, data, len,
359
freespace-i, ndone+1, j);
377
for (k=0; k<i; k++) {
378
if (known[j] == BLOCK) goto next_iter;
381
for (k=0; k<data[ndone]; k++) {
382
if (known[j] == DOT) goto next_iter;
386
if (known[j] == BLOCK) goto next_iter;
389
if (do_recurse(known, deduced, row, minpos_done, maxpos_done,
390
minpos_ok, maxpos_ok, data, len, freespace-i, ndone+1, j)) {
391
if (lowest < minpos_ok[ndone]) minpos_ok[ndone] = lowest;
392
if (lowest + i > maxpos_ok[ndone]) maxpos_ok[ndone] = lowest + i;
393
if (lowest + i > maxpos_done[ndone]) maxpos_done[ndone] = lowest + i;
398
return lowest >= minpos_ok[ndone] && lowest <= maxpos_ok[ndone];
362
for (i=lowest; i<len; i++)
400
for (i=lowest; i<len; i++) {
401
if (known[i] == BLOCK) return FALSE;
364
for (i=0; i<len; i++)
365
if (known[i] && known[i] != row[i])
367
404
for (i=0; i<len; i++)
368
405
deduced[i] |= row[i];
372
411
static int do_row(unsigned char *known, unsigned char *deduced,
373
412
unsigned char *row,
374
unsigned char *start, int len, int step, int *data
413
unsigned char *minpos_done, unsigned char *maxpos_done,
414
unsigned char *minpos_ok, unsigned char *maxpos_ok,
415
unsigned char *start, int len, int step, int *data,
416
unsigned int *changed
375
417
#ifdef STANDALONE_SOLVER
376
418
, const char *rowcol, int index, int cluewid
380
422
int rowlen, i, freespace, done_any;
382
424
freespace = len+1;
383
for (rowlen = 0; data[rowlen]; rowlen++)
425
for (rowlen = 0; data[rowlen]; rowlen++) {
426
minpos_done[rowlen] = minpos_ok[rowlen] = len - 1;
427
maxpos_done[rowlen] = maxpos_ok[rowlen] = 0;
384
428
freespace -= data[rowlen]+1;
386
431
for (i = 0; i < len; i++) {
387
432
known[i] = start[i*step];
391
do_recurse(known, deduced, row, data, len, freespace, 0, 0);
435
for (i = len - 1; i >= 0 && known[i] == DOT; i--)
438
do_recurse(known, deduced, row, minpos_done, maxpos_done, minpos_ok, maxpos_ok, data, len, freespace, 0, 0);
392
440
done_any = FALSE;
393
441
for (i=0; i<len; i++)
394
442
if (deduced[i] && deduced[i] != STILL_UNKNOWN && !known[i]) {
395
443
start[i*step] = deduced[i];
444
if (changed) changed[i]++;
398
447
#ifdef STANDALONE_SOLVER
471
static int solve_puzzle(const game_state *state, unsigned char *grid,
473
unsigned char *matrix, unsigned char *workspace,
474
unsigned int *changed_h, unsigned int *changed_w,
476
#ifdef STANDALONE_SOLVER
486
assert((state!=NULL) ^ (grid!=NULL));
490
memset(matrix, 0, w*h);
492
/* For each column, compute how many squares can be deduced
493
* from just the row-data.
494
* Later, changed_* will hold how many squares were changed
495
* in every row/column in the previous iteration
496
* Changed_* is used to choose the next rows / cols to re-examine
498
for (i=0; i<h; i++) {
501
memcpy(rowdata, state->rowdata + state->rowsize*(w+i), max*sizeof(int));
502
rowdata[state->rowlen[w+i]] = 0;
504
rowdata[compute_rowdata(rowdata, grid+i*w, w, 1)] = 0;
506
for (j=0, freespace=w+1; rowdata[j]; j++) freespace -= rowdata[j] + 1;
507
for (j=0, changed_h[i]=0; rowdata[j]; j++)
508
if (rowdata[j] > freespace)
509
changed_h[i] += rowdata[j] - freespace;
511
for (i=0,max_h=0; i<h; i++)
512
if (changed_h[i] > max_h)
513
max_h = changed_h[i];
514
for (i=0; i<w; i++) {
517
memcpy(rowdata, state->rowdata + state->rowsize*i, max*sizeof(int));
518
rowdata[state->rowlen[i]] = 0;
520
rowdata[compute_rowdata(rowdata, grid+i, h, w)] = 0;
522
for (j=0, freespace=h+1; rowdata[j]; j++) freespace -= rowdata[j] + 1;
523
for (j=0, changed_w[i]=0; rowdata[j]; j++)
524
if (rowdata[j] > freespace)
525
changed_w[i] += rowdata[j] - freespace;
527
for (i=0,max_w=0; i<w; i++)
528
if (changed_w[i] > max_w)
529
max_w = changed_w[i];
532
* Process rows/columns individually. Deductions involving more than one
533
* row and/or column at a time are not supported.
534
* Take care to only process rows/columns which have been changed since they
535
* were previously processed.
536
* Also, prioritize rows/columns which have had the most changes since their
537
* previous processing, as they promise the greatest benefit.
538
* Extremely rectangular grids (e.g. 10x20, 15x40, etc.) are not treated specially.
541
for (; max_h && max_h >= max_w; max_h--) {
542
for (i=0; i<h; i++) {
543
if (changed_h[i] >= max_h) {
545
memcpy(rowdata, state->rowdata + state->rowsize*(w+i), max*sizeof(int));
546
rowdata[state->rowlen[w+i]] = 0;
548
rowdata[compute_rowdata(rowdata, grid+i*w, w, 1)] = 0;
550
do_row(workspace, workspace+max, workspace+2*max,
551
workspace+3*max, workspace+4*max,
552
workspace+5*max, workspace+6*max,
553
matrix+i*w, w, 1, rowdata, changed_w
554
#ifdef STANDALONE_SOLVER
555
, "row", i+1, cluewid
561
for (i=0,max_w=0; i<w; i++)
562
if (changed_w[i] > max_w)
563
max_w = changed_w[i];
565
for (; max_w && max_w >= max_h; max_w--) {
566
for (i=0; i<w; i++) {
567
if (changed_w[i] >= max_w) {
569
memcpy(rowdata, state->rowdata + state->rowsize*i, max*sizeof(int));
570
rowdata[state->rowlen[i]] = 0;
572
rowdata[compute_rowdata(rowdata, grid+i, h, w)] = 0;
574
do_row(workspace, workspace+max, workspace+2*max,
575
workspace+3*max, workspace+4*max,
576
workspace+5*max, workspace+6*max,
577
matrix+i, h, w, rowdata, changed_h
578
#ifdef STANDALONE_SOLVER
579
, "col", i+1, cluewid
585
for (i=0,max_h=0; i<h; i++)
586
if (changed_h[i] > max_h)
587
max_h = changed_h[i];
589
} while (max_h>0 || max_w>0);
592
for (i=0; i<h; i++) {
593
for (j=0; j<w; j++) {
594
if (matrix[i*w+j] == UNKNOWN)
422
602
static unsigned char *generate_soluble(random_state *rs, int w, int h)
424
int i, j, done_any, ok, ntries, max;
604
int i, j, ok, ntries, max;
425
605
unsigned char *grid, *matrix, *workspace;
606
unsigned int *changed_h, *changed_w;
428
611
grid = snewn(w*h, unsigned char);
612
/* Allocate this here, to avoid having to reallocate it again for every geneerated grid */
429
613
matrix = snewn(w*h, unsigned char);
431
workspace = snewn(max*3, unsigned char);
614
workspace = snewn(max*7, unsigned char);
615
changed_h = snewn(max+1, unsigned int);
616
changed_w = snewn(max+1, unsigned int);
432
617
rowdata = snewn(max+1, int);
469
memset(matrix, 0, w*h);
473
for (i=0; i<h; i++) {
474
rowdata[compute_rowdata(rowdata, grid+i*w, w, 1)] = 0;
475
done_any |= do_row(workspace, workspace+max, workspace+2*max,
476
matrix+i*w, w, 1, rowdata
477
#ifdef STANDALONE_SOLVER
478
, NULL, 0, 0 /* never do diagnostics here */
482
for (i=0; i<w; i++) {
483
rowdata[compute_rowdata(rowdata, grid+i, h, w)] = 0;
484
done_any |= do_row(workspace, workspace+max, workspace+2*max,
485
matrix+i, h, w, rowdata
486
#ifdef STANDALONE_SOLVER
487
, NULL, 0, 0 /* never do diagnostics here */
494
for (i=0; i<h; i++) {
495
for (j=0; j<w; j++) {
496
if (matrix[i*w+j] == UNKNOWN)
654
ok = solve_puzzle(NULL, grid, w, h, matrix, workspace,
655
changed_h, changed_w, rowdata, 0);
503
659
sfree(workspace);
508
static char *new_game_desc(game_params *params, random_state *rs,
666
static char *new_game_desc(const game_params *params, random_state *rs,
509
667
char **aux, int interactive)
511
669
unsigned char *grid;
719
879
return dupstr(ai);
721
882
matrix = snewn(w*h, unsigned char);
723
workspace = snewn(max*3, unsigned char);
883
workspace = snewn(max*7, unsigned char);
884
changed_h = snewn(max+1, unsigned int);
885
changed_w = snewn(max+1, unsigned int);
724
886
rowdata = snewn(max+1, int);
726
memset(matrix, 0, w*h);
730
for (i=0; i<h; i++) {
731
memcpy(rowdata, state->rowdata + state->rowsize*(w+i),
733
rowdata[state->rowlen[w+i]] = 0;
734
done_any |= do_row(workspace, workspace+max, workspace+2*max,
735
matrix+i*w, w, 1, rowdata
736
#ifdef STANDALONE_SOLVER
737
, NULL, 0, 0 /* never do diagnostics here */
741
for (i=0; i<w; i++) {
742
memcpy(rowdata, state->rowdata + state->rowsize*i, max*sizeof(int));
743
rowdata[state->rowlen[i]] = 0;
744
done_any |= do_row(workspace, workspace+max, workspace+2*max,
745
matrix+i, h, w, rowdata
746
#ifdef STANDALONE_SOLVER
747
, NULL, 0, 0 /* never do diagnostics here */
888
ok = solve_puzzle(state, NULL, w, h, matrix, workspace,
889
changed_h, changed_w, rowdata, 0);
753
891
sfree(workspace);
756
for (i = 0; i < w*h; i++) {
757
if (matrix[i] != BLOCK && matrix[i] != DOT) {
759
*error = "Solving algorithm cannot complete this puzzle";
898
*error = "Solving algorithm cannot complete this puzzle";
764
902
ret = snewn(w*h+2, char);
1040
1179
/* ----------------------------------------------------------------------
1180
* Error-checking during gameplay.
1184
* The difficulty in error-checking Pattern is to make the error check
1185
* _weak_ enough. The most obvious way would be to check each row and
1186
* column by calling (a modified form of) do_row() to recursively
1187
* analyse the row contents against the clue set and see if the
1188
* GRID_UNKNOWNs could be filled in in any way that would end up
1189
* correct. However, this turns out to be such a strong error check as
1190
* to constitute a spoiler in many situations: you make a typo while
1191
* trying to fill in one row, and not only does the row light up to
1192
* indicate an error, but several columns crossed by the move also
1193
* light up and draw your attention to deductions you hadn't even
1194
* noticed you could make.
1196
* So instead I restrict error-checking to 'complete runs' within a
1197
* row, by which I mean contiguous sequences of GRID_FULL bounded at
1198
* both ends by either GRID_EMPTY or the ends of the row. We identify
1199
* all the complete runs in a row, and verify that _those_ are
1200
* consistent with the row's clue list. Sequences of complete runs
1201
* separated by solid GRID_EMPTY are required to match contiguous
1202
* sequences in the clue list, whereas if there's at least one
1203
* GRID_UNKNOWN between any two complete runs then those two need not
1204
* be contiguous in the clue list.
1206
* To simplify the edge cases, I pretend that the clue list for the
1207
* row is extended with a 0 at each end, and I also pretend that the
1208
* grid data for the row is extended with a GRID_EMPTY and a
1209
* zero-length run at each end. This permits the contiguity checker to
1210
* handle the fiddly end effects (e.g. if the first contiguous
1211
* sequence of complete runs in the grid matches _something_ in the
1212
* clue list but not at the beginning, this is allowable iff there's a
1213
* GRID_UNKNOWN before the first one) with minimal faff, since the end
1214
* effects just drop out as special cases of the normal inter-run
1215
* handling (in this code the above case is not 'at the end of the
1216
* clue list' at all, but between the implicit initial zero run and
1217
* the first nonzero one).
1219
* We must also be a little careful about how we search for a
1220
* contiguous sequence of runs. In the clue list (1 1 2 1 2 3),
1221
* suppose we see a GRID_UNKNOWN and then a length-1 run. We search
1222
* for 1 in the clue list and find it at the very beginning. But now
1223
* suppose we find a length-2 run with no GRID_UNKNOWN before it. We
1224
* can't naively look at the next clue from the 1 we found, because
1225
* that'll be the second 1 and won't match. Instead, we must backtrack
1226
* by observing that the 2 we've just found must be contiguous with
1227
* the 1 we've already seen, so we search for the sequence (1 2) and
1228
* find it starting at the second 1. Now if we see a 3, we must
1229
* rethink again and search for (1 2 3).
1232
struct errcheck_state {
1234
* rowdata and rowlen point at the clue data for this row in the
1240
* rowpos indicates the lowest position where it would be valid to
1241
* see our next run length. It might be equal to rowlen,
1242
* indicating that the next run would have to be the terminating 0.
1246
* ncontig indicates how many runs we've seen in a contiguous
1247
* block. This is taken into account when searching for the next
1248
* run we find, unless ncontig is zeroed out first by encountering
1254
static int errcheck_found_run(struct errcheck_state *es, int r)
1256
/* Macro to handle the pretence that rowdata has a 0 at each end */
1257
#define ROWDATA(k) ((k)<0 || (k)>=es->rowlen ? 0 : es->rowdata[(k)])
1260
* See if we can find this new run length at a position where it
1261
* also matches the last 'ncontig' runs we've seen.
1264
for (newpos = es->rowpos; newpos <= es->rowlen; newpos++) {
1266
if (ROWDATA(newpos) != r)
1269
for (i = 1; i <= es->ncontig; i++)
1270
if (ROWDATA(newpos - i) != ROWDATA(es->rowpos - i))
1273
es->rowpos = newpos+1;
1285
static int check_errors(const game_state *state, int i)
1287
int start, step, end, j;
1289
struct errcheck_state aes, *es = &aes;
1291
es->rowlen = state->rowlen[i];
1292
es->rowdata = state->rowdata + state->rowsize * i;
1293
/* Pretend that we've already encountered the initial zero run */
1300
end = start + step * state->h;
1302
start = (i - state->w) * state->w;
1304
end = start + step * state->w;
1308
for (j = start - step; j <= end; j += step) {
1309
if (j < start || j == end)
1312
val = state->grid[j];
1314
if (val == GRID_UNKNOWN) {
1317
} else if (val == GRID_FULL) {
1320
} else if (val == GRID_EMPTY) {
1322
if (!errcheck_found_run(es, runlen))
1323
return TRUE; /* error! */
1329
/* Signal end-of-row by sending errcheck_found_run the terminating
1330
* zero run, which will be marked as contiguous with the previous
1331
* run if and only if there hasn't been a GRID_UNKNOWN before. */
1332
if (!errcheck_found_run(es, 0))
1333
return TRUE; /* error at the last minute! */
1335
return FALSE; /* no error */
1338
/* ----------------------------------------------------------------------
1041
1339
* Drawing routines.
1044
static void game_compute_size(game_params *params, int tilesize,
1342
static void game_compute_size(const game_params *params, int tilesize,
1047
1345
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
1048
1346
struct { int tilesize; } ads, *ds = &ads;
1131
1434
TILE_SIZE, TILE_SIZE);
1134
static void draw_numbers(drawing *dr, game_drawstate *ds, game_state *state,
1438
* Draw the numbers for a single row or column.
1440
static void draw_numbers(drawing *dr, game_drawstate *ds,
1441
const game_state *state, int i, int erase, int colour)
1443
int rowlen = state->rowlen[i];
1444
int *rowdata = state->rowdata + state->rowsize * i;
1450
draw_rect(dr, TOCOORD(state->w, i), 0,
1451
TILE_SIZE, BORDER + TLBORDER(state->h) * TILE_SIZE,
1454
draw_rect(dr, 0, TOCOORD(state->h, i - state->w),
1455
BORDER + TLBORDER(state->w) * TILE_SIZE, TILE_SIZE,
1461
* Normally I space the numbers out by the same distance as the
1462
* tile size. However, if there are more numbers than available
1463
* spaces, I have to squash them up a bit.
1142
for (i = 0; i < state->w + state->h; i++) {
1143
int rowlen = state->rowlen[i];
1144
int *rowdata = state->rowdata + state->rowsize * i;
1148
* Normally I space the numbers out by the same
1149
* distance as the tile size. However, if there are
1150
* more numbers than available spaces, I have to squash
1153
nfit = max(rowlen, TLBORDER(state->h))-1;
1156
for (j = 0; j < rowlen; j++) {
1161
x = TOCOORD(state->w, i);
1162
y = BORDER + TILE_SIZE * (TLBORDER(state->h)-1);
1163
y -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(state->h)-1) / nfit;
1165
y = TOCOORD(state->h, i - state->w);
1166
x = BORDER + TILE_SIZE * (TLBORDER(state->w)-1);
1167
x -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(state->h)-1) / nfit;
1170
sprintf(str, "%d", rowdata[j]);
1171
draw_text(dr, x+TILE_SIZE/2, y+TILE_SIZE/2, FONT_VARIABLE,
1172
TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, colour, str);
1466
nfit = TLBORDER(state->h);
1468
nfit = TLBORDER(state->w);
1469
nfit = max(rowlen, nfit) - 1;
1472
for (j = 0; j < rowlen; j++) {
1477
x = TOCOORD(state->w, i);
1478
y = BORDER + TILE_SIZE * (TLBORDER(state->h)-1);
1479
y -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(state->h)-1) / nfit;
1481
y = TOCOORD(state->h, i - state->w);
1482
x = BORDER + TILE_SIZE * (TLBORDER(state->w)-1);
1483
x -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(state->w)-1) / nfit;
1486
sprintf(str, "%d", rowdata[j]);
1487
draw_text(dr, x+TILE_SIZE/2, y+TILE_SIZE/2, FONT_VARIABLE,
1488
TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, colour, str);
1492
draw_update(dr, TOCOORD(state->w, i), 0,
1493
TILE_SIZE, BORDER + TLBORDER(state->h) * TILE_SIZE);
1495
draw_update(dr, 0, TOCOORD(state->h, i - state->w),
1496
BORDER + TLBORDER(state->w) * TILE_SIZE, TILE_SIZE);
1177
static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1178
game_state *state, int dir, game_ui *ui,
1500
static void game_redraw(drawing *dr, game_drawstate *ds,
1501
const game_state *oldstate, const game_state *state,
1502
int dir, const game_ui *ui,
1179
1503
float animtime, float flashtime)
1267
1586
ds->cur_x = cx; ds->cur_y = cy;
1589
* Redraw any numbers which have changed their colour due to error
1592
for (i = 0; i < state->w + state->h; i++) {
1593
int colour = check_errors(state, i) ? COL_ERROR : COL_TEXT;
1594
if (ds->numcolours[i] != colour) {
1595
draw_numbers(dr, ds, state, i, TRUE, colour);
1596
ds->numcolours[i] = colour;
1270
static float game_anim_length(game_state *oldstate,
1271
game_state *newstate, int dir, game_ui *ui)
1601
static float game_anim_length(const game_state *oldstate,
1602
const game_state *newstate, int dir, game_ui *ui)
1276
static float game_flash_length(game_state *oldstate,
1277
game_state *newstate, int dir, game_ui *ui)
1607
static float game_flash_length(const game_state *oldstate,
1608
const game_state *newstate, int dir, game_ui *ui)
1279
1610
if (!oldstate->completed && newstate->completed &&
1280
1611
!oldstate->cheated && !newstate->cheated)
1442
1774
s = new_game(NULL, p, desc);
1445
int w = p->w, h = p->h, i, j, done_any, max, cluewid = 0;
1777
int w = p->w, h = p->h, i, j, max, cluewid = 0;
1446
1778
unsigned char *matrix, *workspace;
1779
unsigned int *changed_h, *changed_w;
1449
1782
matrix = snewn(w*h, unsigned char);
1450
1783
max = max(w, h);
1451
workspace = snewn(max*3, unsigned char);
1784
workspace = snewn(max*7, unsigned char);
1785
changed_h = snewn(max+1, unsigned int);
1786
changed_w = snewn(max+1, unsigned int);
1452
1787
rowdata = snewn(max+1, int);
1454
memset(matrix, 0, w*h);
1474
for (i=0; i<h; i++) {
1475
memcpy(rowdata, s->rowdata + s->rowsize*(w+i),
1477
rowdata[s->rowlen[w+i]] = 0;
1478
done_any |= do_row(workspace, workspace+max, workspace+2*max,
1479
matrix+i*w, w, 1, rowdata
1480
#ifdef STANDALONE_SOLVER
1481
, "row", i+1, cluewid
1485
for (i=0; i<w; i++) {
1486
memcpy(rowdata, s->rowdata + s->rowsize*i, max*sizeof(int));
1487
rowdata[s->rowlen[i]] = 0;
1488
done_any |= do_row(workspace, workspace+max, workspace+2*max,
1489
matrix+i, h, w, rowdata
1490
#ifdef STANDALONE_SOLVER
1491
, "col", i+1, cluewid
1805
solve_puzzle(s, NULL, w, h, matrix, workspace,
1806
changed_h, changed_w, rowdata, cluewid);
1497
1808
for (i = 0; i < h; i++) {
1498
1809
for (j = 0; j < w; j++) {
added
removed
pattern.c
