2 * pattern.c: the pattern-reconstruction game known as `nonograms'.
26 #define PREFERRED_TILE_SIZE 24
27 #define TILE_SIZE (ds->tilesize)
28 #define BORDER (3 * TILE_SIZE / 4)
29 #define TLBORDER(d) ( (d) / 5 + 2 )
30 #define GUTTER (TILE_SIZE / 2)
32 #define FROMCOORD(d, x) \
33 ( ((x) - (BORDER + GUTTER + TILE_SIZE * TLBORDER(d))) / TILE_SIZE )
35 #define SIZE(d) (2*BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (d)))
36 #define GETTILESIZE(d, w) ((double)w / (2.0 + (double)TLBORDER(d) + (double)(d)))
38 #define TOCOORD(d, x) (BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (x)))
44 #define GRID_UNKNOWN 2
52 int *rowdata
, *rowlen
;
53 int completed
, cheated
;
56 #define FLASH_TIME 0.13F
58 static game_params
*default_params(void)
60 game_params
*ret
= snew(game_params
);
67 static const struct game_params pattern_presets
[] = {
77 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
82 if (i
< 0 || i
>= lenof(pattern_presets
))
85 ret
= snew(game_params
);
86 *ret
= pattern_presets
[i
];
88 sprintf(str
, "%dx%d", ret
->w
, ret
->h
);
95 static void free_params(game_params
*params
)
100 static game_params
*dup_params(game_params
*params
)
102 game_params
*ret
= snew(game_params
);
103 *ret
= *params
; /* structure copy */
107 static void decode_params(game_params
*ret
, char const *string
)
109 char const *p
= string
;
112 while (*p
&& isdigit((unsigned char)*p
)) p
++;
116 while (*p
&& isdigit((unsigned char)*p
)) p
++;
122 static char *encode_params(game_params
*params
, int full
)
127 len
= sprintf(ret
, "%dx%d", params
->w
, params
->h
);
128 assert(len
< lenof(ret
));
134 static config_item
*game_configure(game_params
*params
)
139 ret
= snewn(3, config_item
);
141 ret
[0].name
= "Width";
142 ret
[0].type
= C_STRING
;
143 sprintf(buf
, "%d", params
->w
);
144 ret
[0].sval
= dupstr(buf
);
147 ret
[1].name
= "Height";
148 ret
[1].type
= C_STRING
;
149 sprintf(buf
, "%d", params
->h
);
150 ret
[1].sval
= dupstr(buf
);
161 static game_params
*custom_params(config_item
*cfg
)
163 game_params
*ret
= snew(game_params
);
165 ret
->w
= atoi(cfg
[0].sval
);
166 ret
->h
= atoi(cfg
[1].sval
);
171 static char *validate_params(game_params
*params
, int full
)
173 if (params
->w
<= 0 || params
->h
<= 0)
174 return "Width and height must both be greater than zero";
178 /* ----------------------------------------------------------------------
179 * Puzzle generation code.
181 * For this particular puzzle, it seemed important to me to ensure
182 * a unique solution. I do this the brute-force way, by having a
183 * solver algorithm alongside the generator, and repeatedly
184 * generating a random grid until I find one whose solution is
185 * unique. It turns out that this isn't too onerous on a modern PC
186 * provided you keep grid size below around 30. Any offers of
187 * better algorithms, however, will be very gratefully received.
189 * Another annoyance of this approach is that it limits the
190 * available puzzles to those solvable by the algorithm I've used.
191 * My algorithm only ever considers a single row or column at any
192 * one time, which means it's incapable of solving the following
193 * difficult example (found by Bella Image around 1995/6, when she
194 * and I were both doing maths degrees):
208 * Obviously this cannot be solved by a one-row-or-column-at-a-time
209 * algorithm (it would require at least one row or column reading
210 * `2 1', `1 2', `3' or `4' to get started). However, it can be
211 * proved to have a unique solution: if the top left square were
212 * empty, then the only option for the top row would be to fill the
213 * two squares in the 1 columns, which would imply the squares
214 * below those were empty, leaving no place for the 2 in the second
215 * row. Contradiction. Hence the top left square is full, and the
216 * unique solution follows easily from that starting point.
218 * (The game ID for this puzzle is 4x4:2/1/2/1/1.1/2/1/1 , in case
219 * it's useful to anyone.)
222 static int float_compare(const void *av
, const void *bv
)
224 const float *a
= (const float *)av
;
225 const float *b
= (const float *)bv
;
234 static void generate(random_state
*rs
, int w
, int h
, unsigned char *retgrid
)
241 fgrid
= snewn(w
*h
, float);
243 for (i
= 0; i
< h
; i
++) {
244 for (j
= 0; j
< w
; j
++) {
245 fgrid
[i
*w
+j
] = random_upto(rs
, 100000000UL) / 100000000.F
;
250 * The above gives a completely random splattering of black and
251 * white cells. We want to gently bias this in favour of _some_
252 * reasonably thick areas of white and black, while retaining
253 * some randomness and fine detail.
255 * So we evolve the starting grid using a cellular automaton.
256 * Currently, I'm doing something very simple indeed, which is
257 * to set each square to the average of the surrounding nine
258 * cells (or the average of fewer, if we're on a corner).
260 for (step
= 0; step
< 1; step
++) {
261 fgrid2
= snewn(w
*h
, float);
263 for (i
= 0; i
< h
; i
++) {
264 for (j
= 0; j
< w
; j
++) {
269 * Compute the average of the surrounding cells.
273 for (p
= -1; p
<= +1; p
++) {
274 for (q
= -1; q
<= +1; q
++) {
275 if (i
+p
< 0 || i
+p
>= h
|| j
+q
< 0 || j
+q
>= w
)
278 * An additional special case not mentioned
279 * above: if a grid dimension is 2xn then
280 * we do not average across that dimension
281 * at all. Otherwise a 2x2 grid would
282 * contain four identical squares.
284 if ((h
==2 && p
!=0) || (w
==2 && q
!=0))
287 sx
+= fgrid
[(i
+p
)*w
+(j
+q
)];
292 fgrid2
[i
*w
+j
] = xbar
;
300 fgrid2
= snewn(w
*h
, float);
301 memcpy(fgrid2
, fgrid
, w
*h
*sizeof(float));
302 qsort(fgrid2
, w
*h
, sizeof(float), float_compare
);
303 threshold
= fgrid2
[w
*h
/2];
306 for (i
= 0; i
< h
; i
++) {
307 for (j
= 0; j
< w
; j
++) {
308 retgrid
[i
*w
+j
] = (fgrid
[i
*w
+j
] >= threshold ? GRID_FULL
:
316 static int compute_rowdata(int *ret
, unsigned char *start
, int len
, int step
)
322 for (i
= 0; i
< len
; i
++) {
323 if (start
[i
*step
] == GRID_FULL
) {
325 while (i
+runlen
< len
&& start
[(i
+runlen
)*step
] == GRID_FULL
)
331 if (i
< len
&& start
[i
*step
] == GRID_UNKNOWN
)
341 #define STILL_UNKNOWN 3
343 #ifdef STANDALONE_SOLVER
347 static void do_recurse(unsigned char *known
, unsigned char *deduced
,
348 unsigned char *row
, int *data
, int len
,
349 int freespace
, int ndone
, int lowest
)
354 for (i
=0; i
<=freespace
; i
++) {
356 for (k
=0; k
<i
; k
++) row
[j
++] = DOT
;
357 for (k
=0; k
<data
[ndone
]; k
++) row
[j
++] = BLOCK
;
358 if (j
< len
) row
[j
++] = DOT
;
359 do_recurse(known
, deduced
, row
, data
, len
,
360 freespace
-i
, ndone
+1, j
);
363 for (i
=lowest
; i
<len
; i
++)
365 for (i
=0; i
<len
; i
++)
366 if (known
[i
] && known
[i
] != row
[i
])
368 for (i
=0; i
<len
; i
++)
369 deduced
[i
] |= row
[i
];
373 static int do_row(unsigned char *known
, unsigned char *deduced
,
375 unsigned char *start
, int len
, int step
, int *data
376 #ifdef STANDALONE_SOLVER
377 , const char *rowcol
, int index
, int cluewid
381 int rowlen
, i
, freespace
, done_any
;
384 for (rowlen
= 0; data
[rowlen
]; rowlen
++)
385 freespace
-= data
[rowlen
]+1;
387 for (i
= 0; i
< len
; i
++) {
388 known
[i
] = start
[i
*step
];
392 do_recurse(known
, deduced
, row
, data
, len
, freespace
, 0, 0);
394 for (i
=0; i
<len
; i
++)
395 if (deduced
[i
] && deduced
[i
] != STILL_UNKNOWN
&& !known
[i
]) {
396 start
[i
*step
] = deduced
[i
];
399 #ifdef STANDALONE_SOLVER
400 if (verbose
&& done_any
) {
403 printf("%s %2d: [", rowcol
, index
);
404 for (thiscluewid
= -1, i
= 0; data
[i
]; i
++)
405 thiscluewid
+= sprintf(buf
, " %d", data
[i
]);
406 printf("%*s", cluewid
- thiscluewid
, "");
407 for (i
= 0; data
[i
]; i
++)
408 printf(" %d", data
[i
]);
410 for (i
= 0; i
< len
; i
++)
411 putchar(known
[i
] == BLOCK ?
'#' :
412 known
[i
] == DOT ?
'.' : '?');
414 for (i
= 0; i
< len
; i
++)
415 putchar(start
[i
*step
] == BLOCK ?
'#' :
416 start
[i
*step
] == DOT ?
'.' : '?');
423 static unsigned char *generate_soluble(random_state
*rs
, int w
, int h
)
425 int i
, j
, done_any
, ok
, ntries
, max
;
426 unsigned char *grid
, *matrix
, *workspace
;
429 grid
= snewn(w
*h
, unsigned char);
430 matrix
= snewn(w
*h
, unsigned char);
432 workspace
= snewn(max
*3, unsigned char);
433 rowdata
= snewn(max
+1, int);
440 generate(rs
, w
, h
, grid
);
443 * The game is a bit too easy if any row or column is
444 * completely black or completely white. An exception is
445 * made for rows/columns that are under 3 squares,
446 * otherwise nothing will ever be successfully generated.
450 for (i
= 0; i
< h
; i
++) {
452 for (j
= 0; j
< w
; j
++)
453 colours
|= (grid
[i
*w
+j
] == GRID_FULL ?
2 : 1);
459 for (j
= 0; j
< w
; j
++) {
461 for (i
= 0; i
< h
; i
++)
462 colours
|= (grid
[i
*w
+j
] == GRID_FULL ?
2 : 1);
470 memset(matrix
, 0, w
*h
);
474 for (i
=0; i
<h
; i
++) {
475 rowdata
[compute_rowdata(rowdata
, grid
+i
*w
, w
, 1)] = 0;
476 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
477 matrix
+i
*w
, w
, 1, rowdata
478 #ifdef STANDALONE_SOLVER
479 , NULL
, 0, 0 /* never do diagnostics here */
483 for (i
=0; i
<w
; i
++) {
484 rowdata
[compute_rowdata(rowdata
, grid
+i
, h
, w
)] = 0;
485 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
486 matrix
+i
, h
, w
, rowdata
487 #ifdef STANDALONE_SOLVER
488 , NULL
, 0, 0 /* never do diagnostics here */
495 for (i
=0; i
<h
; i
++) {
496 for (j
=0; j
<w
; j
++) {
497 if (matrix
[i
*w
+j
] == UNKNOWN
)
509 static char *new_game_desc(game_params
*params
, random_state
*rs
,
510 char **aux
, int interactive
)
513 int i
, j
, max
, rowlen
, *rowdata
;
514 char intbuf
[80], *desc
;
515 int desclen
, descpos
;
517 grid
= generate_soluble(rs
, params
->w
, params
->h
);
518 max
= max(params
->w
, params
->h
);
519 rowdata
= snewn(max
, int);
522 * Save the solved game in aux.
525 char *ai
= snewn(params
->w
* params
->h
+ 2, char);
528 * String format is exactly the same as a solve move, so we
529 * can just dupstr this in solve_game().
534 for (i
= 0; i
< params
->w
* params
->h
; i
++)
535 ai
[i
+1] = grid
[i
] ?
'1' : '0';
537 ai
[params
->w
* params
->h
+ 1] = '\0';
543 * Seed is a slash-separated list of row contents; each row
544 * contents section is a dot-separated list of integers. Row
545 * contents are listed in the order (columns left to right,
546 * then rows top to bottom).
548 * Simplest way to handle memory allocation is to make two
549 * passes, first computing the seed size and then writing it
553 for (i
= 0; i
< params
->w
+ params
->h
; i
++) {
555 rowlen
= compute_rowdata(rowdata
, grid
+i
, params
->h
, params
->w
);
557 rowlen
= compute_rowdata(rowdata
, grid
+(i
-params
->w
)*params
->w
,
560 for (j
= 0; j
< rowlen
; j
++) {
561 desclen
+= 1 + sprintf(intbuf
, "%d", rowdata
[j
]);
567 desc
= snewn(desclen
, char);
569 for (i
= 0; i
< params
->w
+ params
->h
; i
++) {
571 rowlen
= compute_rowdata(rowdata
, grid
+i
, params
->h
, params
->w
);
573 rowlen
= compute_rowdata(rowdata
, grid
+(i
-params
->w
)*params
->w
,
576 for (j
= 0; j
< rowlen
; j
++) {
577 int len
= sprintf(desc
+descpos
, "%d", rowdata
[j
]);
579 desc
[descpos
+ len
] = '.';
581 desc
[descpos
+ len
] = '/';
585 desc
[descpos
++] = '/';
588 assert(descpos
== desclen
);
589 assert(desc
[desclen
-1] == '/');
590 desc
[desclen
-1] = '\0';
596 static char *validate_desc(game_params
*params
, char *desc
)
601 for (i
= 0; i
< params
->w
+ params
->h
; i
++) {
603 rowspace
= params
->h
+ 1;
605 rowspace
= params
->w
+ 1;
607 if (*desc
&& isdigit((unsigned char)*desc
)) {
610 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
616 return "at least one column contains more numbers than will fit";
618 return "at least one row contains more numbers than will fit";
620 } while (*desc
++ == '.');
622 desc
++; /* expect a slash immediately */
625 if (desc
[-1] == '/') {
626 if (i
+1 == params
->w
+ params
->h
)
627 return "too many row/column specifications";
628 } else if (desc
[-1] == '\0') {
629 if (i
+1 < params
->w
+ params
->h
)
630 return "too few row/column specifications";
632 return "unrecognised character in game specification";
638 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
642 game_state
*state
= snew(game_state
);
644 state
->w
= params
->w
;
645 state
->h
= params
->h
;
647 state
->grid
= snewn(state
->w
* state
->h
, unsigned char);
648 memset(state
->grid
, GRID_UNKNOWN
, state
->w
* state
->h
);
650 state
->rowsize
= max(state
->w
, state
->h
);
651 state
->rowdata
= snewn(state
->rowsize
* (state
->w
+ state
->h
), int);
652 state
->rowlen
= snewn(state
->w
+ state
->h
, int);
654 state
->completed
= state
->cheated
= FALSE
;
656 for (i
= 0; i
< params
->w
+ params
->h
; i
++) {
657 state
->rowlen
[i
] = 0;
658 if (*desc
&& isdigit((unsigned char)*desc
)) {
661 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
662 state
->rowdata
[state
->rowsize
* i
+ state
->rowlen
[i
]++] =
664 } while (*desc
++ == '.');
666 desc
++; /* expect a slash immediately */
673 static game_state
*dup_game(game_state
*state
)
675 game_state
*ret
= snew(game_state
);
680 ret
->grid
= snewn(ret
->w
* ret
->h
, unsigned char);
681 memcpy(ret
->grid
, state
->grid
, ret
->w
* ret
->h
);
683 ret
->rowsize
= state
->rowsize
;
684 ret
->rowdata
= snewn(ret
->rowsize
* (ret
->w
+ ret
->h
), int);
685 ret
->rowlen
= snewn(ret
->w
+ ret
->h
, int);
686 memcpy(ret
->rowdata
, state
->rowdata
,
687 ret
->rowsize
* (ret
->w
+ ret
->h
) * sizeof(int));
688 memcpy(ret
->rowlen
, state
->rowlen
,
689 (ret
->w
+ ret
->h
) * sizeof(int));
691 ret
->completed
= state
->completed
;
692 ret
->cheated
= state
->cheated
;
697 static void free_game(game_state
*state
)
699 sfree(state
->rowdata
);
700 sfree(state
->rowlen
);
705 static char *solve_game(game_state
*state
, game_state
*currstate
,
706 char *ai
, char **error
)
708 unsigned char *matrix
;
709 int w
= state
->w
, h
= state
->h
;
713 unsigned char *workspace
;
717 * If we already have the solved state in ai, copy it out.
722 matrix
= snewn(w
*h
, unsigned char);
724 workspace
= snewn(max
*3, unsigned char);
725 rowdata
= snewn(max
+1, int);
727 memset(matrix
, 0, w
*h
);
731 for (i
=0; i
<h
; i
++) {
732 memcpy(rowdata
, state
->rowdata
+ state
->rowsize
*(w
+i
),
734 rowdata
[state
->rowlen
[w
+i
]] = 0;
735 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
736 matrix
+i
*w
, w
, 1, rowdata
737 #ifdef STANDALONE_SOLVER
738 , NULL
, 0, 0 /* never do diagnostics here */
742 for (i
=0; i
<w
; i
++) {
743 memcpy(rowdata
, state
->rowdata
+ state
->rowsize
*i
, max
*sizeof(int));
744 rowdata
[state
->rowlen
[i
]] = 0;
745 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
746 matrix
+i
, h
, w
, rowdata
747 #ifdef STANDALONE_SOLVER
748 , NULL
, 0, 0 /* never do diagnostics here */
757 for (i
= 0; i
< w
*h
; i
++) {
758 if (matrix
[i
] != BLOCK
&& matrix
[i
] != DOT
) {
760 *error
= "Solving algorithm cannot complete this puzzle";
765 ret
= snewn(w
*h
+2, char);
767 for (i
= 0; i
< w
*h
; i
++) {
768 assert(matrix
[i
] == BLOCK
|| matrix
[i
] == DOT
);
769 ret
[i
+1] = (matrix
[i
] == BLOCK ?
'1' : '0');
778 static int game_can_format_as_text_now(game_params
*params
)
783 static char *game_text_format(game_state
*state
)
794 int drag
, release
, state
;
795 int cur_x
, cur_y
, cur_visible
;
798 static game_ui
*new_ui(game_state
*state
)
803 ret
->dragging
= FALSE
;
804 ret
->cur_x
= ret
->cur_y
= ret
->cur_visible
= 0;
809 static void free_ui(game_ui
*ui
)
814 static char *encode_ui(game_ui
*ui
)
819 static void decode_ui(game_ui
*ui
, char *encoding
)
823 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
824 game_state
*newstate
)
828 struct game_drawstate
{
832 unsigned char *visible
, *numcolours
;
836 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
837 int x
, int y
, int button
)
841 x
= FROMCOORD(state
->w
, x
);
842 y
= FROMCOORD(state
->h
, y
);
844 if (x
>= 0 && x
< state
->w
&& y
>= 0 && y
< state
->h
&&
845 (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
||
846 button
== MIDDLE_BUTTON
)) {
848 int currstate
= state
->grid
[y
* state
->w
+ x
];
853 if (button
== LEFT_BUTTON
) {
854 ui
->drag
= LEFT_DRAG
;
855 ui
->release
= LEFT_RELEASE
;
857 ui
->state
= (currstate
+ 2) % 3; /* FULL -> EMPTY -> UNKNOWN */
859 ui
->state
= GRID_FULL
;
861 } else if (button
== RIGHT_BUTTON
) {
862 ui
->drag
= RIGHT_DRAG
;
863 ui
->release
= RIGHT_RELEASE
;
865 ui
->state
= (currstate
+ 1) % 3; /* EMPTY -> FULL -> UNKNOWN */
867 ui
->state
= GRID_EMPTY
;
869 } else /* if (button == MIDDLE_BUTTON) */ {
870 ui
->drag
= MIDDLE_DRAG
;
871 ui
->release
= MIDDLE_RELEASE
;
872 ui
->state
= GRID_UNKNOWN
;
875 ui
->drag_start_x
= ui
->drag_end_x
= x
;
876 ui
->drag_start_y
= ui
->drag_end_y
= y
;
879 return ""; /* UI activity occurred */
882 if (ui
->dragging
&& button
== ui
->drag
) {
884 * There doesn't seem much point in allowing a rectangle
885 * drag; people will generally only want to drag a single
886 * horizontal or vertical line, so we make that easy by
889 * Exception: if we're _middle_-button dragging to tag
890 * things as UNKNOWN, we may well want to trash an entire
891 * area and start over!
893 if (ui
->state
!= GRID_UNKNOWN
) {
894 if (abs(x
- ui
->drag_start_x
) > abs(y
- ui
->drag_start_y
))
895 y
= ui
->drag_start_y
;
897 x
= ui
->drag_start_x
;
902 if (x
>= state
->w
) x
= state
->w
- 1;
903 if (y
>= state
->h
) y
= state
->h
- 1;
908 return ""; /* UI activity occurred */
911 if (ui
->dragging
&& button
== ui
->release
) {
912 int x1
, x2
, y1
, y2
, xx
, yy
;
913 int move_needed
= FALSE
;
915 x1
= min(ui
->drag_start_x
, ui
->drag_end_x
);
916 x2
= max(ui
->drag_start_x
, ui
->drag_end_x
);
917 y1
= min(ui
->drag_start_y
, ui
->drag_end_y
);
918 y2
= max(ui
->drag_start_y
, ui
->drag_end_y
);
920 for (yy
= y1
; yy
<= y2
; yy
++)
921 for (xx
= x1
; xx
<= x2
; xx
++)
922 if (state
->grid
[yy
* state
->w
+ xx
] != ui
->state
)
925 ui
->dragging
= FALSE
;
929 sprintf(buf
, "%c%d,%d,%d,%d",
930 (char)(ui
->state
== GRID_FULL ?
'F' :
931 ui
->state
== GRID_EMPTY ?
'E' : 'U'),
932 x1
, y1
, x2
-x1
+1, y2
-y1
+1);
935 return ""; /* UI activity occurred */
938 if (IS_CURSOR_MOVE(button
)) {
939 move_cursor(button
, &ui
->cur_x
, &ui
->cur_y
, state
->w
, state
->h
, 0);
943 if (IS_CURSOR_SELECT(button
)) {
944 int currstate
= state
->grid
[ui
->cur_y
* state
->w
+ ui
->cur_x
];
948 if (!ui
->cur_visible
) {
953 if (button
== CURSOR_SELECT2
)
954 newstate
= currstate
== GRID_UNKNOWN ? GRID_EMPTY
:
955 currstate
== GRID_EMPTY ? GRID_FULL
: GRID_UNKNOWN
;
957 newstate
= currstate
== GRID_UNKNOWN ? GRID_FULL
:
958 currstate
== GRID_FULL ? GRID_EMPTY
: GRID_UNKNOWN
;
960 sprintf(buf
, "%c%d,%d,%d,%d",
961 (char)(newstate
== GRID_FULL ?
'F' :
962 newstate
== GRID_EMPTY ?
'E' : 'U'),
963 ui
->cur_x
, ui
->cur_y
, 1, 1);
970 static game_state
*execute_move(game_state
*from
, char *move
)
973 int x1
, x2
, y1
, y2
, xx
, yy
;
976 if (move
[0] == 'S' && strlen(move
) == from
->w
* from
->h
+ 1) {
979 ret
= dup_game(from
);
981 for (i
= 0; i
< ret
->w
* ret
->h
; i
++)
982 ret
->grid
[i
] = (move
[i
+1] == '1' ? GRID_FULL
: GRID_EMPTY
);
984 ret
->completed
= ret
->cheated
= TRUE
;
987 } else if ((move
[0] == 'F' || move
[0] == 'E' || move
[0] == 'U') &&
988 sscanf(move
+1, "%d,%d,%d,%d", &x1
, &y1
, &x2
, &y2
) == 4 &&
989 x1
>= 0 && x2
>= 0 && x1
+x2
<= from
->w
&&
990 y1
>= 0 && y2
>= 0 && y1
+y2
<= from
->h
) {
994 val
= (move
[0] == 'F' ? GRID_FULL
:
995 move
[0] == 'E' ? GRID_EMPTY
: GRID_UNKNOWN
);
997 ret
= dup_game(from
);
998 for (yy
= y1
; yy
< y2
; yy
++)
999 for (xx
= x1
; xx
< x2
; xx
++)
1000 ret
->grid
[yy
* ret
->w
+ xx
] = val
;
1003 * An actual change, so check to see if we've completed the
1006 if (!ret
->completed
) {
1007 int *rowdata
= snewn(ret
->rowsize
, int);
1010 ret
->completed
= TRUE
;
1012 for (i
=0; i
<ret
->w
; i
++) {
1013 len
= compute_rowdata(rowdata
,
1014 ret
->grid
+i
, ret
->h
, ret
->w
);
1015 if (len
!= ret
->rowlen
[i
] ||
1016 memcmp(ret
->rowdata
+i
*ret
->rowsize
, rowdata
,
1017 len
* sizeof(int))) {
1018 ret
->completed
= FALSE
;
1022 for (i
=0; i
<ret
->h
; i
++) {
1023 len
= compute_rowdata(rowdata
,
1024 ret
->grid
+i
*ret
->w
, ret
->w
, 1);
1025 if (len
!= ret
->rowlen
[i
+ret
->w
] ||
1026 memcmp(ret
->rowdata
+(i
+ret
->w
)*ret
->rowsize
, rowdata
,
1027 len
* sizeof(int))) {
1028 ret
->completed
= FALSE
;
1041 /* ----------------------------------------------------------------------
1042 * Error-checking during gameplay.
1046 * The difficulty in error-checking Pattern is to make the error check
1047 * _weak_ enough. The most obvious way would be to check each row and
1048 * column by calling (a modified form of) do_row() to recursively
1049 * analyse the row contents against the clue set and see if the
1050 * GRID_UNKNOWNs could be filled in in any way that would end up
1051 * correct. However, this turns out to be such a strong error check as
1052 * to constitute a spoiler in many situations: you make a typo while
1053 * trying to fill in one row, and not only does the row light up to
1054 * indicate an error, but several columns crossed by the move also
1055 * light up and draw your attention to deductions you hadn't even
1056 * noticed you could make.
1058 * So instead I restrict error-checking to 'complete runs' within a
1059 * row, by which I mean contiguous sequences of GRID_FULL bounded at
1060 * both ends by either GRID_EMPTY or the ends of the row. We identify
1061 * all the complete runs in a row, and verify that _those_ are
1062 * consistent with the row's clue list. Sequences of complete runs
1063 * separated by solid GRID_EMPTY are required to match contiguous
1064 * sequences in the clue list, whereas if there's at least one
1065 * GRID_UNKNOWN between any two complete runs then those two need not
1066 * be contiguous in the clue list.
1068 * To simplify the edge cases, I pretend that the clue list for the
1069 * row is extended with a 0 at each end, and I also pretend that the
1070 * grid data for the row is extended with a GRID_EMPTY and a
1071 * zero-length run at each end. This permits the contiguity checker to
1072 * handle the fiddly end effects (e.g. if the first contiguous
1073 * sequence of complete runs in the grid matches _something_ in the
1074 * clue list but not at the beginning, this is allowable iff there's a
1075 * GRID_UNKNOWN before the first one) with minimal faff, since the end
1076 * effects just drop out as special cases of the normal inter-run
1077 * handling (in this code the above case is not 'at the end of the
1078 * clue list' at all, but between the implicit initial zero run and
1079 * the first nonzero one).
1081 * We must also be a little careful about how we search for a
1082 * contiguous sequence of runs. In the clue list (1 1 2 1 2 3),
1083 * suppose we see a GRID_UNKNOWN and then a length-1 run. We search
1084 * for 1 in the clue list and find it at the very beginning. But now
1085 * suppose we find a length-2 run with no GRID_UNKNOWN before it. We
1086 * can't naively look at the next clue from the 1 we found, because
1087 * that'll be the second 1 and won't match. Instead, we must backtrack
1088 * by observing that the 2 we've just found must be contiguous with
1089 * the 1 we've already seen, so we search for the sequence (1 2) and
1090 * find it starting at the second 1. Now if we see a 3, we must
1091 * rethink again and search for (1 2 3).
1094 struct errcheck_state
{
1096 * rowdata and rowlen point at the clue data for this row in the
1102 * rowpos indicates the lowest position where it would be valid to
1103 * see our next run length. It might be equal to rowlen,
1104 * indicating that the next run would have to be the terminating 0.
1108 * ncontig indicates how many runs we've seen in a contiguous
1109 * block. This is taken into account when searching for the next
1110 * run we find, unless ncontig is zeroed out first by encountering
1116 static int errcheck_found_run(struct errcheck_state
*es
, int r
)
1118 /* Macro to handle the pretence that rowdata has a 0 at each end */
1119 #define ROWDATA(k) ((k)<0 || (k)>=es->rowlen ? 0 : es->rowdata[(k)])
1122 * See if we can find this new run length at a position where it
1123 * also matches the last 'ncontig' runs we've seen.
1126 for (newpos
= es
->rowpos
; newpos
<= es
->rowlen
; newpos
++) {
1128 if (ROWDATA(newpos
) != r
)
1131 for (i
= 1; i
<= es
->ncontig
; i
++)
1132 if (ROWDATA(newpos
- i
) != ROWDATA(es
->rowpos
- i
))
1135 es
->rowpos
= newpos
+1;
1147 static int check_errors(game_state
*state
, int i
)
1149 int start
, step
, end
, j
;
1151 struct errcheck_state aes
, *es
= &aes
;
1153 es
->rowlen
= state
->rowlen
[i
];
1154 es
->rowdata
= state
->rowdata
+ state
->rowsize
* i
;
1155 /* Pretend that we've already encountered the initial zero run */
1162 end
= start
+ step
* state
->h
;
1164 start
= (i
- state
->w
) * state
->w
;
1166 end
= start
+ step
* state
->w
;
1170 for (j
= start
- step
; j
<= end
; j
+= step
) {
1171 if (j
< start
|| j
== end
)
1174 val
= state
->grid
[j
];
1176 if (val
== GRID_UNKNOWN
) {
1179 } else if (val
== GRID_FULL
) {
1182 } else if (val
== GRID_EMPTY
) {
1184 if (!errcheck_found_run(es
, runlen
))
1185 return TRUE
; /* error! */
1191 /* Signal end-of-row by sending errcheck_found_run the terminating
1192 * zero run, which will be marked as contiguous with the previous
1193 * run if and only if there hasn't been a GRID_UNKNOWN before. */
1194 if (!errcheck_found_run(es
, 0))
1195 return TRUE
; /* error at the last minute! */
1197 return FALSE
; /* no error */
1200 /* ----------------------------------------------------------------------
1204 static void game_compute_size(game_params
*params
, int tilesize
,
1207 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1208 struct { int tilesize
; } ads
, *ds
= &ads
;
1209 ads
.tilesize
= tilesize
;
1211 *x
= SIZE(params
->w
);
1212 *y
= SIZE(params
->h
);
1215 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1216 game_params
*params
, int tilesize
)
1218 ds
->tilesize
= tilesize
;
1221 static float *game_colours(frontend
*fe
, int *ncolours
)
1223 float *ret
= snewn(3 * NCOLOURS
, float);
1226 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1228 for (i
= 0; i
< 3; i
++) {
1229 ret
[COL_GRID
* 3 + i
] = 0.3F
;
1230 ret
[COL_UNKNOWN
* 3 + i
] = 0.5F
;
1231 ret
[COL_TEXT
* 3 + i
] = 0.0F
;
1232 ret
[COL_FULL
* 3 + i
] = 0.0F
;
1233 ret
[COL_EMPTY
* 3 + i
] = 1.0F
;
1235 ret
[COL_CURSOR
* 3 + 0] = 1.0F
;
1236 ret
[COL_CURSOR
* 3 + 1] = 0.25F
;
1237 ret
[COL_CURSOR
* 3 + 2] = 0.25F
;
1238 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
1239 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
1240 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
1242 *ncolours
= NCOLOURS
;
1246 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1248 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1250 ds
->started
= FALSE
;
1253 ds
->visible
= snewn(ds
->w
* ds
->h
, unsigned char);
1254 ds
->tilesize
= 0; /* not decided yet */
1255 memset(ds
->visible
, 255, ds
->w
* ds
->h
);
1256 ds
->numcolours
= snewn(ds
->w
+ ds
->h
, unsigned char);
1257 memset(ds
->numcolours
, 255, ds
->w
+ ds
->h
);
1258 ds
->cur_x
= ds
->cur_y
= 0;
1263 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1269 static void grid_square(drawing
*dr
, game_drawstate
*ds
,
1270 int y
, int x
, int state
, int cur
)
1272 int xl
, xr
, yt
, yb
, dx
, dy
, dw
, dh
;
1274 draw_rect(dr
, TOCOORD(ds
->w
, x
), TOCOORD(ds
->h
, y
),
1275 TILE_SIZE
, TILE_SIZE
, COL_GRID
);
1277 xl
= (x
% 5 == 0 ?
1 : 0);
1278 yt
= (y
% 5 == 0 ?
1 : 0);
1279 xr
= (x
% 5 == 4 || x
== ds
->w
-1 ?
1 : 0);
1280 yb
= (y
% 5 == 4 || y
== ds
->h
-1 ?
1 : 0);
1282 dx
= TOCOORD(ds
->w
, x
) + 1 + xl
;
1283 dy
= TOCOORD(ds
->h
, y
) + 1 + yt
;
1284 dw
= TILE_SIZE
- xl
- xr
- 1;
1285 dh
= TILE_SIZE
- yt
- yb
- 1;
1287 draw_rect(dr
, dx
, dy
, dw
, dh
,
1288 (state
== GRID_FULL ? COL_FULL
:
1289 state
== GRID_EMPTY ? COL_EMPTY
: COL_UNKNOWN
));
1291 draw_rect_outline(dr
, dx
, dy
, dw
, dh
, COL_CURSOR
);
1292 draw_rect_outline(dr
, dx
+1, dy
+1, dw
-2, dh
-2, COL_CURSOR
);
1295 draw_update(dr
, TOCOORD(ds
->w
, x
), TOCOORD(ds
->h
, y
),
1296 TILE_SIZE
, TILE_SIZE
);
1300 * Draw the numbers for a single row or column.
1302 static void draw_numbers(drawing
*dr
, game_drawstate
*ds
, game_state
*state
,
1303 int i
, int erase
, int colour
)
1305 int rowlen
= state
->rowlen
[i
];
1306 int *rowdata
= state
->rowdata
+ state
->rowsize
* i
;
1312 draw_rect(dr
, TOCOORD(state
->w
, i
), 0,
1313 TILE_SIZE
, BORDER
+ TLBORDER(state
->w
) * TILE_SIZE
,
1316 draw_rect(dr
, 0, TOCOORD(state
->h
, i
- state
->w
),
1317 BORDER
+ TLBORDER(state
->h
) * TILE_SIZE
, TILE_SIZE
,
1323 * Normally I space the numbers out by the same distance as the
1324 * tile size. However, if there are more numbers than available
1325 * spaces, I have to squash them up a bit.
1327 nfit
= max(rowlen
, TLBORDER(state
->h
))-1;
1330 for (j
= 0; j
< rowlen
; j
++) {
1335 x
= TOCOORD(state
->w
, i
);
1336 y
= BORDER
+ TILE_SIZE
* (TLBORDER(state
->h
)-1);
1337 y
-= ((rowlen
-j
-1)*TILE_SIZE
) * (TLBORDER(state
->h
)-1) / nfit
;
1339 y
= TOCOORD(state
->h
, i
- state
->w
);
1340 x
= BORDER
+ TILE_SIZE
* (TLBORDER(state
->w
)-1);
1341 x
-= ((rowlen
-j
-1)*TILE_SIZE
) * (TLBORDER(state
->h
)-1) / nfit
;
1344 sprintf(str
, "%d", rowdata
[j
]);
1345 draw_text(dr
, x
+TILE_SIZE
/2, y
+TILE_SIZE
/2, FONT_VARIABLE
,
1346 TILE_SIZE
/2, ALIGN_HCENTRE
| ALIGN_VCENTRE
, colour
, str
);
1350 draw_update(dr
, TOCOORD(state
->w
, i
), 0,
1351 TILE_SIZE
, BORDER
+ TLBORDER(state
->w
) * TILE_SIZE
);
1353 draw_update(dr
, 0, TOCOORD(state
->h
, i
- state
->w
),
1354 BORDER
+ TLBORDER(state
->h
) * TILE_SIZE
, TILE_SIZE
);
1358 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1359 game_state
*state
, int dir
, game_ui
*ui
,
1360 float animtime
, float flashtime
)
1368 * The initial contents of the window are not guaranteed
1369 * and can vary with front ends. To be on the safe side,
1370 * all games should start by drawing a big background-
1371 * colour rectangle covering the whole window.
1373 draw_rect(dr
, 0, 0, SIZE(ds
->w
), SIZE(ds
->h
), COL_BACKGROUND
);
1376 * Draw the grid outline.
1378 draw_rect(dr
, TOCOORD(ds
->w
, 0) - 1, TOCOORD(ds
->h
, 0) - 1,
1379 ds
->w
* TILE_SIZE
+ 3, ds
->h
* TILE_SIZE
+ 3,
1384 draw_update(dr
, 0, 0, SIZE(ds
->w
), SIZE(ds
->h
));
1388 x1
= min(ui
->drag_start_x
, ui
->drag_end_x
);
1389 x2
= max(ui
->drag_start_x
, ui
->drag_end_x
);
1390 y1
= min(ui
->drag_start_y
, ui
->drag_end_y
);
1391 y2
= max(ui
->drag_start_y
, ui
->drag_end_y
);
1393 x1
= x2
= y1
= y2
= -1; /* placate gcc warnings */
1396 if (ui
->cur_visible
) {
1397 cx
= ui
->cur_x
; cy
= ui
->cur_y
;
1401 cmoved
= (cx
!= ds
->cur_x
|| cy
!= ds
->cur_y
);
1404 * Now draw any grid squares which have changed since last
1407 for (i
= 0; i
< ds
->h
; i
++) {
1408 for (j
= 0; j
< ds
->w
; j
++) {
1412 * Work out what state this square should be drawn in,
1413 * taking any current drag operation into account.
1415 if (ui
->dragging
&& x1
<= j
&& j
<= x2
&& y1
<= i
&& i
<= y2
)
1418 val
= state
->grid
[i
* state
->w
+ j
];
1421 /* the cursor has moved; if we were the old or
1422 * the new cursor position we need to redraw. */
1423 if (j
== cx
&& i
== cy
) cc
= 1;
1424 if (j
== ds
->cur_x
&& i
== ds
->cur_y
) cc
= 1;
1428 * Briefly invert everything twice during a completion
1431 if (flashtime
> 0 &&
1432 (flashtime
<= FLASH_TIME
/3 || flashtime
>= FLASH_TIME
*2/3) &&
1433 val
!= GRID_UNKNOWN
)
1434 val
= (GRID_FULL
^ GRID_EMPTY
) ^ val
;
1436 if (ds
->visible
[i
* ds
->w
+ j
] != val
|| cc
) {
1437 grid_square(dr
, ds
, i
, j
, val
,
1438 (j
== cx
&& i
== cy
));
1439 ds
->visible
[i
* ds
->w
+ j
] = val
;
1443 ds
->cur_x
= cx
; ds
->cur_y
= cy
;
1446 * Redraw any numbers which have changed their colour due to error
1449 for (i
= 0; i
< state
->w
+ state
->h
; i
++) {
1450 int colour
= check_errors(state
, i
) ? COL_ERROR
: COL_TEXT
;
1451 if (ds
->numcolours
[i
] != colour
) {
1452 draw_numbers(dr
, ds
, state
, i
, TRUE
, colour
);
1453 ds
->numcolours
[i
] = colour
;
1458 static float game_anim_length(game_state
*oldstate
,
1459 game_state
*newstate
, int dir
, game_ui
*ui
)
1464 static float game_flash_length(game_state
*oldstate
,
1465 game_state
*newstate
, int dir
, game_ui
*ui
)
1467 if (!oldstate
->completed
&& newstate
->completed
&&
1468 !oldstate
->cheated
&& !newstate
->cheated
)
1473 static int game_status(game_state
*state
)
1475 return state
->completed ?
+1 : 0;
1478 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1483 static void game_print_size(game_params
*params
, float *x
, float *y
)
1488 * I'll use 5mm squares by default.
1490 game_compute_size(params
, 500, &pw
, &ph
);
1495 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
1497 int w
= state
->w
, h
= state
->h
;
1498 int ink
= print_mono_colour(dr
, 0);
1501 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1502 game_drawstate ads
, *ds
= &ads
;
1503 game_set_size(dr
, ds
, NULL
, tilesize
);
1508 print_line_width(dr
, TILE_SIZE
/ 16);
1509 draw_rect_outline(dr
, TOCOORD(w
, 0), TOCOORD(h
, 0),
1510 w
*TILE_SIZE
, h
*TILE_SIZE
, ink
);
1515 for (x
= 1; x
< w
; x
++) {
1516 print_line_width(dr
, TILE_SIZE
/ (x
% 5 ?
128 : 24));
1517 draw_line(dr
, TOCOORD(w
, x
), TOCOORD(h
, 0),
1518 TOCOORD(w
, x
), TOCOORD(h
, h
), ink
);
1520 for (y
= 1; y
< h
; y
++) {
1521 print_line_width(dr
, TILE_SIZE
/ (y
% 5 ?
128 : 24));
1522 draw_line(dr
, TOCOORD(w
, 0), TOCOORD(h
, y
),
1523 TOCOORD(w
, w
), TOCOORD(h
, y
), ink
);
1529 for (i
= 0; i
< state
->w
+ state
->h
; i
++)
1530 draw_numbers(dr
, ds
, state
, i
, FALSE
, ink
);
1535 print_line_width(dr
, TILE_SIZE
/ 128);
1536 for (y
= 0; y
< h
; y
++)
1537 for (x
= 0; x
< w
; x
++) {
1538 if (state
->grid
[y
*w
+x
] == GRID_FULL
)
1539 draw_rect(dr
, TOCOORD(w
, x
), TOCOORD(h
, y
),
1540 TILE_SIZE
, TILE_SIZE
, ink
);
1541 else if (state
->grid
[y
*w
+x
] == GRID_EMPTY
)
1542 draw_circle(dr
, TOCOORD(w
, x
) + TILE_SIZE
/2,
1543 TOCOORD(h
, y
) + TILE_SIZE
/2,
1544 TILE_SIZE
/12, ink
, ink
);
1549 #define thegame pattern
1552 const struct game thegame
= {
1553 "Pattern", "games.pattern", "pattern",
1560 TRUE
, game_configure
, custom_params
,
1568 FALSE
, game_can_format_as_text_now
, game_text_format
,
1576 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
1579 game_free_drawstate
,
1584 TRUE
, FALSE
, game_print_size
, game_print
,
1585 FALSE
, /* wants_statusbar */
1586 FALSE
, game_timing_state
,
1587 REQUIRE_RBUTTON
, /* flags */
1590 #ifdef STANDALONE_SOLVER
1592 int main(int argc
, char **argv
)
1596 char *id
= NULL
, *desc
, *err
;
1598 while (--argc
> 0) {
1601 if (!strcmp(p
, "-v")) {
1604 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
1613 fprintf(stderr
, "usage: %s <game_id>\n", argv
[0]);
1617 desc
= strchr(id
, ':');
1619 fprintf(stderr
, "%s: game id expects a colon in it\n", argv
[0]);
1624 p
= default_params();
1625 decode_params(p
, id
);
1626 err
= validate_desc(p
, desc
);
1628 fprintf(stderr
, "%s: %s\n", argv
[0], err
);
1631 s
= new_game(NULL
, p
, desc
);
1634 int w
= p
->w
, h
= p
->h
, i
, j
, done_any
, max
, cluewid
= 0;
1635 unsigned char *matrix
, *workspace
;
1638 matrix
= snewn(w
*h
, unsigned char);
1640 workspace
= snewn(max
*3, unsigned char);
1641 rowdata
= snewn(max
+1, int);
1643 memset(matrix
, 0, w
*h
);
1648 * Work out the maximum text width of the clue numbers
1649 * in a row or column, so we can print the solver's
1650 * working in a nicely lined up way.
1652 for (i
= 0; i
< (w
+h
); i
++) {
1654 for (thiswid
= -1, j
= 0; j
< s
->rowlen
[i
]; j
++)
1655 thiswid
+= sprintf(buf
, " %d", s
->rowdata
[s
->rowsize
*i
+j
]);
1656 if (cluewid
< thiswid
)
1663 for (i
=0; i
<h
; i
++) {
1664 memcpy(rowdata
, s
->rowdata
+ s
->rowsize
*(w
+i
),
1666 rowdata
[s
->rowlen
[w
+i
]] = 0;
1667 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
1668 matrix
+i
*w
, w
, 1, rowdata
1669 #ifdef STANDALONE_SOLVER
1670 , "row", i
+1, cluewid
1674 for (i
=0; i
<w
; i
++) {
1675 memcpy(rowdata
, s
->rowdata
+ s
->rowsize
*i
, max
*sizeof(int));
1676 rowdata
[s
->rowlen
[i
]] = 0;
1677 done_any
|= do_row(workspace
, workspace
+max
, workspace
+2*max
,
1678 matrix
+i
, h
, w
, rowdata
1679 #ifdef STANDALONE_SOLVER
1680 , "col", i
+1, cluewid
1686 for (i
= 0; i
< h
; i
++) {
1687 for (j
= 0; j
< w
; j
++) {
1688 int c
= (matrix
[i
*w
+j
] == UNKNOWN ?
'?' :
1689 matrix
[i
*w
+j
] == BLOCK ?
'#' :
1690 matrix
[i
*w
+j
] == DOT ?
'.' :
1703 /* vim: set shiftwidth=4 tabstop=8: */