2 * keen.c: an implementation of the Times's 'KenKen' puzzle.
16 * Difficulty levels. I do some macro ickery here to ensure that my
17 * enum and the various forms of my name list always match up.
20 A(EASY,Easy,solver_easy,e) \
21 A(NORMAL,Normal,solver_normal,n) \
22 A(HARD,Hard,solver_hard,h) \
23 A(EXTREME,Extreme,NULL,x) \
24 A(UNREASONABLE,Unreasonable,NULL,u)
25 #define ENUM(upper,title,func,lower) DIFF_ ## upper,
26 #define TITLE(upper,title,func,lower) #title,
27 #define ENCODE(upper,title,func,lower) #lower
28 #define CONFIG(upper,title,func,lower) ":" #title
29 enum { DIFFLIST(ENUM
) DIFFCOUNT
};
30 static char const *const keen_diffnames
[] = { DIFFLIST(TITLE
) };
31 static char const keen_diffchars
[] = DIFFLIST(ENCODE
);
32 #define DIFFCONFIG DIFFLIST(CONFIG)
35 * Clue notation. Important here that ADD and MUL come before SUB
36 * and DIV, and that DIV comes last.
38 #define C_ADD 0x00000000L
39 #define C_MUL 0x20000000L
40 #define C_SUB 0x40000000L
41 #define C_DIV 0x60000000L
42 #define CMASK 0x60000000L
43 #define CUNIT 0x20000000L
70 int *pencil
; /* bitmaps using bits 1<<1..1<<n */
71 int completed
, cheated
;
74 static game_params
*default_params(void)
76 game_params
*ret
= snew(game_params
);
79 ret
->diff
= DIFF_NORMAL
;
84 const static struct game_params keen_presets
[] = {
91 { 6, DIFF_UNREASONABLE
},
95 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
100 if (i
< 0 || i
>= lenof(keen_presets
))
103 ret
= snew(game_params
);
104 *ret
= keen_presets
[i
]; /* structure copy */
106 sprintf(buf
, "%dx%d %s", ret
->w
, ret
->w
, keen_diffnames
[ret
->diff
]);
113 static void free_params(game_params
*params
)
118 static game_params
*dup_params(game_params
*params
)
120 game_params
*ret
= snew(game_params
);
121 *ret
= *params
; /* structure copy */
125 static void decode_params(game_params
*params
, char const *string
)
127 char const *p
= string
;
130 while (*p
&& isdigit((unsigned char)*p
)) p
++;
135 params
->diff
= DIFFCOUNT
+1; /* ...which is invalid */
137 for (i
= 0; i
< DIFFCOUNT
; i
++) {
138 if (*p
== keen_diffchars
[i
])
146 static char *encode_params(game_params
*params
, int full
)
150 sprintf(ret
, "%d", params
->w
);
152 sprintf(ret
+ strlen(ret
), "d%c", keen_diffchars
[params
->diff
]);
157 static config_item
*game_configure(game_params
*params
)
162 ret
= snewn(3, config_item
);
164 ret
[0].name
= "Grid size";
165 ret
[0].type
= C_STRING
;
166 sprintf(buf
, "%d", params
->w
);
167 ret
[0].sval
= dupstr(buf
);
170 ret
[1].name
= "Difficulty";
171 ret
[1].type
= C_CHOICES
;
172 ret
[1].sval
= DIFFCONFIG
;
173 ret
[1].ival
= params
->diff
;
183 static game_params
*custom_params(config_item
*cfg
)
185 game_params
*ret
= snew(game_params
);
187 ret
->w
= atoi(cfg
[0].sval
);
188 ret
->diff
= cfg
[1].ival
;
193 static char *validate_params(game_params
*params
, int full
)
195 if (params
->w
< 3 || params
->w
> 9)
196 return "Grid size must be between 3 and 9";
197 if (params
->diff
>= DIFFCOUNT
)
198 return "Unknown difficulty rating";
202 /* ----------------------------------------------------------------------
209 int *boxes
, *boxlist
, *whichbox
;
216 static void solver_clue_candidate(struct solver_ctx
*ctx
, int diff
, int box
)
219 int n
= ctx
->boxes
[box
+1] - ctx
->boxes
[box
];
223 * This function is called from the main clue-based solver
224 * routine when we discover a candidate layout for a given clue
225 * box consistent with everything we currently know about the
226 * digit constraints in that box. We expect to find the digits
227 * of the candidate layout in ctx->dscratch, and we update
228 * ctx->iscratch as appropriate.
230 if (diff
== DIFF_EASY
) {
233 * Easy-mode clue deductions: we do not record information
234 * about which squares take which values, so we amalgamate
235 * all the values in dscratch and OR them all into
238 for (j
= 0; j
< n
; j
++)
239 mask
|= 1 << ctx
->dscratch
[j
];
240 for (j
= 0; j
< n
; j
++)
241 ctx
->iscratch
[j
] |= mask
;
242 } else if (diff
== DIFF_NORMAL
) {
244 * Normal-mode deductions: we process the information in
245 * dscratch in the obvious way.
247 for (j
= 0; j
< n
; j
++)
248 ctx
->iscratch
[j
] |= 1 << ctx
->dscratch
[j
];
249 } else if (diff
== DIFF_HARD
) {
251 * Hard-mode deductions: instead of ruling things out
252 * _inside_ the clue box, we look for numbers which occur in
253 * a given row or column in all candidate layouts, and rule
254 * them out of all squares in that row or column that
255 * _aren't_ part of this clue box.
257 int *sq
= ctx
->boxlist
+ ctx
->boxes
[box
];
259 for (j
= 0; j
< 2*w
; j
++)
260 ctx
->iscratch
[2*w
+j
] = 0;
261 for (j
= 0; j
< n
; j
++) {
262 int x
= sq
[j
] / w
, y
= sq
[j
] % w
;
263 ctx
->iscratch
[2*w
+x
] |= 1 << ctx
->dscratch
[j
];
264 ctx
->iscratch
[3*w
+y
] |= 1 << ctx
->dscratch
[j
];
266 for (j
= 0; j
< 2*w
; j
++)
267 ctx
->iscratch
[j
] &= ctx
->iscratch
[2*w
+j
];
271 static int solver_common(struct latin_solver
*solver
, void *vctx
, int diff
)
273 struct solver_ctx
*ctx
= (struct solver_ctx
*)vctx
;
279 * Iterate over each clue box and deduce what we can.
281 for (box
= 0; box
< ctx
->nboxes
; box
++) {
282 int *sq
= ctx
->boxlist
+ ctx
->boxes
[box
];
283 int n
= ctx
->boxes
[box
+1] - ctx
->boxes
[box
];
284 long value
= ctx
->clues
[box
] & ~CMASK
;
285 long op
= ctx
->clues
[box
] & CMASK
;
287 if (diff
== DIFF_HARD
) {
288 for (i
= 0; i
< n
; i
++)
289 ctx
->iscratch
[i
] = (1 << (w
+1)) - (1 << 1);
291 for (i
= 0; i
< n
; i
++)
292 ctx
->iscratch
[i
] = 0;
299 * These two clue types must always apply to a box of
300 * area 2. Also, the two digits in these boxes can never
301 * be the same (because any domino must have its two
302 * squares in either the same row or the same column).
303 * So we simply iterate over all possibilities for the
304 * two squares (both ways round), rule out any which are
305 * inconsistent with the digit constraints we already
306 * have, and update the digit constraints with any new
307 * information thus garnered.
311 for (i
= 1; i
<= w
; i
++) {
312 j
= (op
== C_SUB ? i
+ value
: i
* value
);
315 /* (i,j) is a valid digit pair. Try it both ways round. */
317 if (solver
->cube
[sq
[0]*w
+i
-1] &&
318 solver
->cube
[sq
[1]*w
+j
-1]) {
319 ctx
->dscratch
[0] = i
;
320 ctx
->dscratch
[1] = j
;
321 solver_clue_candidate(ctx
, diff
, box
);
324 if (solver
->cube
[sq
[0]*w
+j
-1] &&
325 solver
->cube
[sq
[1]*w
+i
-1]) {
326 ctx
->dscratch
[0] = j
;
327 ctx
->dscratch
[1] = i
;
328 solver_clue_candidate(ctx
, diff
, box
);
337 * For these clue types, I have no alternative but to go
338 * through all possible number combinations.
340 * Instead of a tedious physical recursion, I iterate in
341 * the scratch array through all possibilities. At any
342 * given moment, i indexes the element of the box that
343 * will next be incremented.
346 ctx
->dscratch
[i
] = 0;
347 total
= value
; /* start with the identity */
351 * Find the next valid value for cell i.
353 for (j
= ctx
->dscratch
[i
] + 1; j
<= w
; j
++) {
354 if (op
== C_ADD ?
(total
< j
) : (total
% j
!= 0))
355 continue; /* this one won't fit */
356 if (!solver
->cube
[sq
[i
]*w
+j
-1])
357 continue; /* this one is ruled out already */
358 for (k
= 0; k
< i
; k
++)
359 if (ctx
->dscratch
[k
] == j
&&
360 (sq
[k
] % w
== sq
[i
] % w
||
361 sq
[k
] / w
== sq
[i
] / w
))
362 break; /* clashes with another row/col */
371 /* No valid values left; drop back. */
374 break; /* overall iteration is finished */
376 total
+= ctx
->dscratch
[i
];
378 total
*= ctx
->dscratch
[i
];
380 /* Got a valid value; store it and move on. */
381 ctx
->dscratch
[i
++] = j
;
386 ctx
->dscratch
[i
] = 0;
389 if (total
== (op
== C_ADD ?
0 : 1))
390 solver_clue_candidate(ctx
, diff
, box
);
393 total
+= ctx
->dscratch
[i
];
395 total
*= ctx
->dscratch
[i
];
402 if (diff
< DIFF_HARD
) {
403 #ifdef STANDALONE_SOLVER
406 if (solver_show_working
)
407 sprintf(prefix
, "%*susing clue at (%d,%d):\n",
408 solver_recurse_depth
*4, "",
409 sq
[0]/w
+1, sq
[0]%w
+1);
411 prefix
[0] = '\0'; /* placate optimiser */
414 for (i
= 0; i
< n
; i
++)
415 for (j
= 1; j
<= w
; j
++) {
416 if (solver
->cube
[sq
[i
]*w
+j
-1] &&
417 !(ctx
->iscratch
[i
] & (1 << j
))) {
418 #ifdef STANDALONE_SOLVER
419 if (solver_show_working
) {
420 printf("%s%*s ruling out %d at (%d,%d)\n",
421 prefix
, solver_recurse_depth
*4, "",
422 j
, sq
[i
]/w
+1, sq
[i
]%w
+1);
426 solver
->cube
[sq
[i
]*w
+j
-1] = 0;
431 #ifdef STANDALONE_SOLVER
434 if (solver_show_working
)
435 sprintf(prefix
, "%*susing clue at (%d,%d):\n",
436 solver_recurse_depth
*4, "",
437 sq
[0]/w
+1, sq
[0]%w
+1);
439 prefix
[0] = '\0'; /* placate optimiser */
442 for (i
= 0; i
< 2*w
; i
++) {
443 int start
= (i
< w ? i
*w
: i
-w
);
444 int step
= (i
< w ?
1 : w
);
445 for (j
= 1; j
<= w
; j
++) if (ctx
->iscratch
[i
] & (1 << j
)) {
446 #ifdef STANDALONE_SOLVER
449 if (solver_show_working
)
450 sprintf(prefix2
, "%*s this clue requires %d in"
451 " %s %d:\n", solver_recurse_depth
*4, "",
452 j
, i
< w ?
"column" : "row", i
%w
+1);
454 prefix2
[0] = '\0'; /* placate optimiser */
457 for (k
= 0; k
< w
; k
++) {
458 int pos
= start
+ k
*step
;
459 if (ctx
->whichbox
[pos
] != box
&&
460 solver
->cube
[pos
*w
+j
-1]) {
461 #ifdef STANDALONE_SOLVER
462 if (solver_show_working
) {
463 printf("%s%s%*s ruling out %d at (%d,%d)\n",
465 solver_recurse_depth
*4, "",
466 j
, pos
/w
+1, pos
%w
+1);
467 prefix
[0] = prefix2
[0] = '\0';
470 solver
->cube
[pos
*w
+j
-1] = 0;
478 * Once we find one block we can do something with in
479 * this way, revert to trying easier deductions, so as
480 * not to generate solver diagnostics that make the
481 * problem look harder than it is. (We have to do this
482 * for the Hard deductions but not the Easy/Normal ones,
483 * because only the Hard deductions are cross-box.)
493 static int solver_easy(struct latin_solver
*solver
, void *vctx
)
496 * Omit the EASY deductions when solving at NORMAL level, since
497 * the NORMAL deductions are a superset of them anyway and it
498 * saves on time and confusing solver diagnostics.
500 * Note that this breaks the natural semantics of the return
501 * value of latin_solver. Without this hack, you could determine
502 * a puzzle's difficulty in one go by trying to solve it at
503 * maximum difficulty and seeing what difficulty value was
504 * returned; but with this hack, solving an Easy puzzle on
505 * Normal difficulty will typically return Normal. Hence the
506 * uses of the solver to determine difficulty are all arranged
507 * so as to double-check by re-solving at the next difficulty
508 * level down and making sure it failed.
510 struct solver_ctx
*ctx
= (struct solver_ctx
*)vctx
;
511 if (ctx
->diff
> DIFF_EASY
)
513 return solver_common(solver
, vctx
, DIFF_EASY
);
516 static int solver_normal(struct latin_solver
*solver
, void *vctx
)
518 return solver_common(solver
, vctx
, DIFF_NORMAL
);
521 static int solver_hard(struct latin_solver
*solver
, void *vctx
)
523 return solver_common(solver
, vctx
, DIFF_HARD
);
526 #define SOLVER(upper,title,func,lower) func,
527 static usersolver_t
const keen_solvers
[] = { DIFFLIST(SOLVER
) };
529 static int solver(int w
, int *dsf
, long *clues
, digit
*soln
, int maxdiff
)
532 struct solver_ctx ctx
;
541 * Transform the dsf-formatted clue list into one over which we
542 * can iterate more easily.
544 * Also transpose the x- and y-coordinates at this point,
545 * because the 'cube' array in the general Latin square solver
546 * puts x first (oops).
548 for (ctx
.nboxes
= i
= 0; i
< a
; i
++)
549 if (dsf_canonify(dsf
, i
) == i
)
551 ctx
.boxlist
= snewn(a
, int);
552 ctx
.boxes
= snewn(ctx
.nboxes
+1, int);
553 ctx
.clues
= snewn(ctx
.nboxes
, long);
554 ctx
.whichbox
= snewn(a
, int);
555 for (n
= m
= i
= 0; i
< a
; i
++)
556 if (dsf_canonify(dsf
, i
) == i
) {
557 ctx
.clues
[n
] = clues
[i
];
559 for (j
= 0; j
< a
; j
++)
560 if (dsf_canonify(dsf
, j
) == i
) {
561 ctx
.boxlist
[m
++] = (j
% w
) * w
+ (j
/ w
); /* transpose */
562 ctx
.whichbox
[ctx
.boxlist
[m
-1]] = n
;
566 assert(n
== ctx
.nboxes
);
570 ctx
.dscratch
= snewn(a
+1, digit
);
571 ctx
.iscratch
= snewn(max(a
+1, 4*w
), int);
573 ret
= latin_solver(soln
, w
, maxdiff
,
574 DIFF_EASY
, DIFF_HARD
, DIFF_EXTREME
,
575 DIFF_EXTREME
, DIFF_UNREASONABLE
,
576 keen_solvers
, &ctx
, NULL
, NULL
);
588 /* ----------------------------------------------------------------------
592 static char *encode_block_structure(char *p
, int w
, int *dsf
)
595 char *orig
, *q
, *r
, c
;
600 * Encode the block structure. We do this by encoding the
601 * pattern of dividing lines: first we iterate over the w*(w-1)
602 * internal vertical grid lines in ordinary reading order, then
603 * over the w*(w-1) internal horizontal ones in transposed
606 * We encode the number of non-lines between the lines; _ means
607 * zero (two adjacent divisions), a means 1, ..., y means 25,
608 * and z means 25 non-lines _and no following line_ (so that za
609 * means 26, zb 27 etc).
611 for (i
= 0; i
<= 2*w
*(w
-1); i
++) {
612 int x
, y
, p0
, p1
, edge
;
614 if (i
== 2*w
*(w
-1)) {
615 edge
= TRUE
; /* terminating virtual edge */
628 edge
= (dsf_canonify(dsf
, p0
) != dsf_canonify(dsf
, p1
));
633 *p
++ = 'z', currrun
-= 25;
635 *p
++ = 'a'-1 + currrun
;
644 * Now go through and compress the string by replacing runs of
645 * the same letter with a single copy of that letter followed by
646 * a repeat count, where that makes it shorter. (This puzzle
647 * seems to generate enough long strings of _ to make this a
650 for (q
= r
= orig
; r
< p
;) {
653 for (i
= 0; r
+i
< p
&& r
[i
] == c
; i
++);
659 q
+= sprintf(q
, "%d", i
);
666 static char *parse_block_structure(const char **p
, int w
, int *dsf
)
670 int repc
= 0, repn
= 0;
674 while (**p
&& (repn
> 0 || **p
!= ',')) {
680 } else if (**p
== '_' || (**p
>= 'a' && **p
<= 'z')) {
681 c
= (**p
== '_' ?
0 : **p
- 'a' + 1);
683 if (**p
&& isdigit((unsigned char)**p
)) {
686 while (**p
&& isdigit((unsigned char)**p
)) (*p
)++;
689 return "Invalid character in game description";
691 adv
= (c
!= 25); /* 'z' is a special case */
697 * Non-edge; merge the two dsf classes on either
700 if (pos
>= 2*w
*(w
-1))
701 return "Too much data in block structure specification";
708 int x
= pos
/(w
-1) - w
;
713 dsf_merge(dsf
, p0
, p1
);
719 if (pos
> 2*w
*(w
-1)+1)
720 return "Too much data in block structure specification";
725 * When desc is exhausted, we expect to have gone exactly
726 * one space _past_ the end of the grid, due to the dummy
729 if (pos
!= 2*w
*(w
-1)+1)
730 return "Not enough data in block structure specification";
735 static char *new_game_desc(game_params
*params
, random_state
*rs
,
736 char **aux
, int interactive
)
738 int w
= params
->w
, a
= w
*w
;
740 int *order
, *revorder
, *singletons
, *dsf
;
741 long *clues
, *cluevals
;
742 int i
, j
, k
, n
, x
, y
, ret
;
743 int diff
= params
->diff
;
747 * Difficulty exceptions: 3x3 puzzles at difficulty Hard or
748 * higher are currently not generable - the generator will spin
749 * forever looking for puzzles of the appropriate difficulty. We
750 * dial each of these down to the next lower difficulty.
752 * Remember to re-test this whenever a change is made to the
755 * I tested it using the following shell command:
757 for d in e n h x u; do
759 echo ./keen --generate 1 ${i}d${d}
760 perl -e 'alarm 30; exec @ARGV' ./keen --generate 5 ${i}d${d} >/dev/null \
765 * Of course, it's better to do that after taking the exceptions
766 * _out_, so as to detect exceptions that should be removed as
767 * well as those which should be added.
769 if (w
== 3 && diff
> DIFF_NORMAL
)
774 order
= snewn(a
, int);
775 revorder
= snewn(a
, int);
776 singletons
= snewn(a
, int);
778 clues
= snewn(a
, long);
779 cluevals
= snewn(a
, long);
780 soln
= snewn(a
, digit
);
784 * First construct a latin square to be the solution.
787 grid
= latin_generate(w
, rs
);
790 * Divide the grid into arbitrarily sized blocks, but so as
791 * to arrange plenty of dominoes which can be SUB/DIV clues.
792 * We do this by first placing dominoes at random for a
793 * while, then tying the remaining singletons one by one
794 * into neighbouring blocks.
796 for (i
= 0; i
< a
; i
++)
798 shuffle(order
, a
, sizeof(*order
), rs
);
799 for (i
= 0; i
< a
; i
++)
800 revorder
[order
[i
]] = i
;
802 for (i
= 0; i
< a
; i
++)
803 singletons
[i
] = TRUE
;
807 /* Place dominoes. */
808 for (i
= 0; i
< a
; i
++) {
815 if (x
> 0 && singletons
[i
-1] &&
816 (best
== -1 || revorder
[i
-1] < revorder
[best
]))
818 if (x
+1 < w
&& singletons
[i
+1] &&
819 (best
== -1 || revorder
[i
+1] < revorder
[best
]))
821 if (y
> 0 && singletons
[i
-w
] &&
822 (best
== -1 || revorder
[i
-w
] < revorder
[best
]))
824 if (y
+1 < w
&& singletons
[i
+w
] &&
825 (best
== -1 || revorder
[i
+w
] < revorder
[best
]))
829 * When we find a potential domino, we place it with
830 * probability 3/4, which seems to strike a decent
831 * balance between plenty of dominoes and leaving
832 * enough singletons to make interesting larger
835 if (best
>= 0 && random_upto(rs
, 4)) {
836 singletons
[i
] = singletons
[best
] = FALSE
;
837 dsf_merge(dsf
, i
, best
);
842 /* Fold in singletons. */
843 for (i
= 0; i
< a
; i
++) {
851 (best
== -1 || revorder
[i
-1] < revorder
[best
]))
854 (best
== -1 || revorder
[i
+1] < revorder
[best
]))
857 (best
== -1 || revorder
[i
-w
] < revorder
[best
]))
860 (best
== -1 || revorder
[i
+w
] < revorder
[best
]))
864 singletons
[i
] = FALSE
;
865 dsf_merge(dsf
, i
, best
);
871 * Decide what would be acceptable clues for each block.
873 * Blocks larger than 2 have free choice of ADD or MUL;
874 * blocks of size 2 can be anything in principle (except
875 * that they can only be DIV if the two numbers have an
876 * integer quotient, of course), but we rule out (or try to
877 * avoid) some clues because they're of low quality.
879 * Hence, we iterate once over the grid, stopping at the
880 * canonical element of every >2 block and the _non_-
881 * canonical element of every 2-block; the latter means that
882 * we can make our decision about a 2-block in the knowledge
883 * of both numbers in it.
885 * We reuse the 'singletons' array (finished with in the
886 * above loop) to hold information about which blocks are
890 #define F_ADD_BAD 0x02
892 #define F_SUB_BAD 0x08
894 #define F_MUL_BAD 0x20
896 #define F_DIV_BAD 0x80
897 for (i
= 0; i
< a
; i
++) {
899 j
= dsf_canonify(dsf
, i
);
900 k
= dsf_size(dsf
, j
);
901 if (j
== i
&& k
> 2) {
902 singletons
[j
] |= F_ADD
| F_MUL
;
903 } else if (j
!= i
&& k
== 2) {
904 /* Fetch the two numbers and sort them into order. */
905 int p
= grid
[j
], q
= grid
[i
], v
;
907 int t
= p
; p
= q
; q
= t
;
911 * Addition clues are always allowed, but we try to
912 * avoid sums of 3, 4, (2w-1) and (2w-2) if we can,
913 * because they're too easy - they only leave one
914 * option for the pair of numbers involved.
917 if (v
> 4 && v
< 2*w
-2)
918 singletons
[j
] |= F_ADD
;
920 singletons
[j
] |= F_ADD_BAD
;
923 * Multiplication clues: similarly, we prefer clues
924 * of this type which leave multiple options open.
925 * We can't rule out all the others, though, because
926 * there are very very few 2-square multiplication
927 * clues that _don't_ leave only one option.
931 for (k
= 1; k
<= w
; k
++)
932 if (v
% k
== 0 && v
/ k
<= w
&& v
/ k
!= k
)
935 singletons
[j
] |= F_MUL
;
937 singletons
[j
] |= F_MUL_BAD
;
940 * Subtraction: we completely avoid a difference of
945 singletons
[j
] |= F_SUB
;
948 * Division: for a start, the quotient must be an
949 * integer or the clue type is impossible. Also, we
950 * never use quotients strictly greater than w/2,
951 * because they're not only too easy but also
954 if (p
% q
== 0 && 2 * (p
/ q
) <= w
)
955 singletons
[j
] |= F_DIV
;
960 * Actually choose a clue for each block, trying to keep the
961 * numbers of each type even, and starting with the
962 * preferred candidates for each type where possible.
964 * I'm sure there should be a faster algorithm for doing
965 * this, but I can't be bothered: O(N^2) is good enough when
966 * N is at most the number of dominoes that fits into a 9x9
969 shuffle(order
, a
, sizeof(*order
), rs
);
970 for (i
= 0; i
< a
; i
++)
973 int done_something
= FALSE
;
975 for (k
= 0; k
< 4; k
++) {
979 case 0: clue
= C_DIV
; good
= F_DIV
; bad
= F_DIV_BAD
; break;
980 case 1: clue
= C_SUB
; good
= F_SUB
; bad
= F_SUB_BAD
; break;
981 case 2: clue
= C_MUL
; good
= F_MUL
; bad
= F_MUL_BAD
; break;
982 default /* case 3 */ :
983 clue
= C_ADD
; good
= F_ADD
; bad
= F_ADD_BAD
; break;
986 for (i
= 0; i
< a
; i
++) {
988 if (singletons
[j
] & good
) {
995 /* didn't find a nice one, use a nasty one */
996 for (i
= 0; i
< a
; i
++) {
998 if (singletons
[j
] & good
) {
1006 done_something
= TRUE
;
1009 if (!done_something
)
1022 * Having chosen the clue types, calculate the clue values.
1024 for (i
= 0; i
< a
; i
++) {
1025 j
= dsf_canonify(dsf
, i
);
1027 cluevals
[j
] = grid
[i
];
1031 cluevals
[j
] += grid
[i
];
1034 cluevals
[j
] *= grid
[i
];
1037 cluevals
[j
] = abs(cluevals
[j
] - grid
[i
]);
1041 int d1
= cluevals
[j
], d2
= grid
[i
];
1042 if (d1
== 0 || d2
== 0)
1045 cluevals
[j
] = d2
/d1
+ d1
/d2
;/* one is 0 :-) */
1052 for (i
= 0; i
< a
; i
++) {
1053 j
= dsf_canonify(dsf
, i
);
1055 clues
[j
] |= cluevals
[j
];
1060 * See if the game can be solved at the specified difficulty
1061 * level, but not at the one below.
1065 ret
= solver(w
, dsf
, clues
, soln
, diff
-1);
1070 ret
= solver(w
, dsf
, clues
, soln
, diff
);
1072 continue; /* go round again */
1075 * I wondered if at this point it would be worth trying to
1076 * merge adjacent blocks together, to make the puzzle
1077 * gradually more difficult if it's currently easier than
1078 * specced, increasing the chance of a given generation run
1081 * It doesn't seem to be critical for the generation speed,
1082 * though, so for the moment I'm leaving it out.
1086 * We've got a usable puzzle!
1092 * Encode the puzzle description.
1094 desc
= snewn(40*a
, char);
1096 p
= encode_block_structure(p
, w
, dsf
);
1098 for (i
= 0; i
< a
; i
++) {
1099 j
= dsf_canonify(dsf
, i
);
1101 switch (clues
[j
] & CMASK
) {
1102 case C_ADD
: *p
++ = 'a'; break;
1103 case C_SUB
: *p
++ = 's'; break;
1104 case C_MUL
: *p
++ = 'm'; break;
1105 case C_DIV
: *p
++ = 'd'; break;
1107 p
+= sprintf(p
, "%ld", clues
[j
] & ~CMASK
);
1111 desc
= sresize(desc
, p
- desc
, char);
1114 * Encode the solution.
1116 assert(memcmp(soln
, grid
, a
) == 0);
1117 *aux
= snewn(a
+2, char);
1119 for (i
= 0; i
< a
; i
++)
1120 (*aux
)[i
+1] = '0' + soln
[i
];
1135 /* ----------------------------------------------------------------------
1139 static char *validate_desc(game_params
*params
, char *desc
)
1141 int w
= params
->w
, a
= w
*w
;
1144 const char *p
= desc
;
1148 * Verify that the block structure makes sense.
1151 ret
= parse_block_structure(&p
, w
, dsf
);
1158 return "Expected ',' after block structure description";
1162 * Verify that the right number of clues are given, and that SUB
1163 * and DIV clues don't apply to blocks of the wrong size.
1165 for (i
= 0; i
< a
; i
++) {
1166 if (dsf_canonify(dsf
, i
) == i
) {
1167 if (*p
== 'a' || *p
== 'm') {
1168 /* these clues need no validation */
1169 } else if (*p
== 'd' || *p
== 's') {
1170 if (dsf_size(dsf
, i
) != 2)
1171 return "Subtraction and division blocks must have area 2";
1173 return "Too few clues for block structure";
1175 return "Unrecognised clue type";
1178 while (*p
&& isdigit((unsigned char)*p
)) p
++;
1182 return "Too many clues for block structure";
1187 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1189 int w
= params
->w
, a
= w
*w
;
1190 game_state
*state
= snew(game_state
);
1192 const char *p
= desc
;
1195 state
->par
= *params
; /* structure copy */
1196 state
->clues
= snew(struct clues
);
1197 state
->clues
->refcount
= 1;
1198 state
->clues
->w
= w
;
1199 state
->clues
->dsf
= snew_dsf(a
);
1200 err
= parse_block_structure(&p
, w
, state
->clues
->dsf
);
1205 state
->clues
->clues
= snewn(a
, long);
1206 for (i
= 0; i
< a
; i
++) {
1207 if (dsf_canonify(state
->clues
->dsf
, i
) == i
) {
1218 assert(dsf_size(state
->clues
->dsf
, i
) == 2);
1222 assert(dsf_size(state
->clues
->dsf
, i
) == 2);
1225 assert(!"Bad description in new_game");
1229 while (*p
&& isdigit((unsigned char)*p
)) p
++;
1230 state
->clues
->clues
[i
] = clue
;
1232 state
->clues
->clues
[i
] = 0;
1235 state
->grid
= snewn(a
, digit
);
1236 state
->pencil
= snewn(a
, int);
1237 for (i
= 0; i
< a
; i
++) {
1239 state
->pencil
[i
] = 0;
1242 state
->completed
= state
->cheated
= FALSE
;
1247 static game_state
*dup_game(game_state
*state
)
1249 int w
= state
->par
.w
, a
= w
*w
;
1250 game_state
*ret
= snew(game_state
);
1252 ret
->par
= state
->par
; /* structure copy */
1254 ret
->clues
= state
->clues
;
1255 ret
->clues
->refcount
++;
1257 ret
->grid
= snewn(a
, digit
);
1258 ret
->pencil
= snewn(a
, int);
1259 memcpy(ret
->grid
, state
->grid
, a
*sizeof(digit
));
1260 memcpy(ret
->pencil
, state
->pencil
, a
*sizeof(int));
1262 ret
->completed
= state
->completed
;
1263 ret
->cheated
= state
->cheated
;
1268 static void free_game(game_state
*state
)
1271 sfree(state
->pencil
);
1272 if (--state
->clues
->refcount
<= 0) {
1273 sfree(state
->clues
->dsf
);
1274 sfree(state
->clues
->clues
);
1275 sfree(state
->clues
);
1280 static char *solve_game(game_state
*state
, game_state
*currstate
,
1281 char *aux
, char **error
)
1283 int w
= state
->par
.w
, a
= w
*w
;
1291 soln
= snewn(a
, digit
);
1294 ret
= solver(w
, state
->clues
->dsf
, state
->clues
->clues
,
1297 if (ret
== diff_impossible
) {
1298 *error
= "No solution exists for this puzzle";
1300 } else if (ret
== diff_ambiguous
) {
1301 *error
= "Multiple solutions exist for this puzzle";
1304 out
= snewn(a
+2, char);
1306 for (i
= 0; i
< a
; i
++)
1307 out
[i
+1] = '0' + soln
[i
];
1315 static int game_can_format_as_text_now(game_params
*params
)
1320 static char *game_text_format(game_state
*state
)
1327 * These are the coordinates of the currently highlighted
1328 * square on the grid, if hshow = 1.
1332 * This indicates whether the current highlight is a
1333 * pencil-mark one or a real one.
1337 * This indicates whether or not we're showing the highlight
1338 * (used to be hx = hy = -1); important so that when we're
1339 * using the cursor keys it doesn't keep coming back at a
1340 * fixed position. When hshow = 1, pressing a valid number
1341 * or letter key or Space will enter that number or letter in the grid.
1345 * This indicates whether we're using the highlight as a cursor;
1346 * it means that it doesn't vanish on a keypress, and that it is
1347 * allowed on immutable squares.
1352 static game_ui
*new_ui(game_state
*state
)
1354 game_ui
*ui
= snew(game_ui
);
1356 ui
->hx
= ui
->hy
= 0;
1357 ui
->hpencil
= ui
->hshow
= ui
->hcursor
= 0;
1362 static void free_ui(game_ui
*ui
)
1367 static char *encode_ui(game_ui
*ui
)
1372 static void decode_ui(game_ui
*ui
, char *encoding
)
1376 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1377 game_state
*newstate
)
1379 int w
= newstate
->par
.w
;
1381 * We prevent pencil-mode highlighting of a filled square, unless
1382 * we're using the cursor keys. So if the user has just filled in
1383 * a square which we had a pencil-mode highlight in (by Undo, or
1384 * by Redo, or by Solve), then we cancel the highlight.
1386 if (ui
->hshow
&& ui
->hpencil
&& !ui
->hcursor
&&
1387 newstate
->grid
[ui
->hy
* w
+ ui
->hx
] != 0) {
1392 #define PREFERRED_TILESIZE 48
1393 #define TILESIZE (ds->tilesize)
1394 #define BORDER (TILESIZE / 2)
1395 #define GRIDEXTRA max((TILESIZE / 32),1)
1396 #define COORD(x) ((x)*TILESIZE + BORDER)
1397 #define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1)
1399 #define FLASH_TIME 0.4F
1401 #define DF_PENCIL_SHIFT 16
1402 #define DF_ERR_LATIN 0x8000
1403 #define DF_ERR_CLUE 0x4000
1404 #define DF_HIGHLIGHT 0x2000
1405 #define DF_HIGHLIGHT_PENCIL 0x1000
1406 #define DF_DIGIT_MASK 0x000F
1408 struct game_drawstate
{
1413 char *minus_sign
, *times_sign
, *divide_sign
;
1416 static int check_errors(game_state
*state
, long *errors
)
1418 int w
= state
->par
.w
, a
= w
*w
;
1419 int i
, j
, x
, y
, errs
= FALSE
;
1423 cluevals
= snewn(a
, long);
1424 full
= snewn(a
, int);
1427 for (i
= 0; i
< a
; i
++) {
1432 for (i
= 0; i
< a
; i
++) {
1435 j
= dsf_canonify(state
->clues
->dsf
, i
);
1437 cluevals
[i
] = state
->grid
[i
];
1439 clue
= state
->clues
->clues
[j
] & CMASK
;
1443 cluevals
[j
] += state
->grid
[i
];
1446 cluevals
[j
] *= state
->grid
[i
];
1449 cluevals
[j
] = abs(cluevals
[j
] - state
->grid
[i
]);
1453 int d1
= min(cluevals
[j
], state
->grid
[i
]);
1454 int d2
= max(cluevals
[j
], state
->grid
[i
]);
1455 if (d1
== 0 || d2
% d1
!= 0)
1458 cluevals
[j
] = d2
/ d1
;
1464 if (!state
->grid
[i
])
1468 for (i
= 0; i
< a
; i
++) {
1469 j
= dsf_canonify(state
->clues
->dsf
, i
);
1471 if ((state
->clues
->clues
[j
] & ~CMASK
) != cluevals
[i
]) {
1473 if (errors
&& full
[j
])
1474 errors
[j
] |= DF_ERR_CLUE
;
1482 for (y
= 0; y
< w
; y
++) {
1483 int mask
= 0, errmask
= 0;
1484 for (x
= 0; x
< w
; x
++) {
1485 int bit
= 1 << state
->grid
[y
*w
+x
];
1486 errmask
|= (mask
& bit
);
1490 if (mask
!= (1 << (w
+1)) - (1 << 1)) {
1494 for (x
= 0; x
< w
; x
++)
1495 if (errmask
& (1 << state
->grid
[y
*w
+x
]))
1496 errors
[y
*w
+x
] |= DF_ERR_LATIN
;
1501 for (x
= 0; x
< w
; x
++) {
1502 int mask
= 0, errmask
= 0;
1503 for (y
= 0; y
< w
; y
++) {
1504 int bit
= 1 << state
->grid
[y
*w
+x
];
1505 errmask
|= (mask
& bit
);
1509 if (mask
!= (1 << (w
+1)) - (1 << 1)) {
1513 for (y
= 0; y
< w
; y
++)
1514 if (errmask
& (1 << state
->grid
[y
*w
+x
]))
1515 errors
[y
*w
+x
] |= DF_ERR_LATIN
;
1523 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1524 int x
, int y
, int button
)
1526 int w
= state
->par
.w
;
1530 button
&= ~MOD_MASK
;
1535 if (tx
>= 0 && tx
< w
&& ty
>= 0 && ty
< w
) {
1536 if (button
== LEFT_BUTTON
) {
1537 if (tx
== ui
->hx
&& ty
== ui
->hy
&&
1538 ui
->hshow
&& ui
->hpencil
== 0) {
1547 return ""; /* UI activity occurred */
1549 if (button
== RIGHT_BUTTON
) {
1551 * Pencil-mode highlighting for non filled squares.
1553 if (state
->grid
[ty
*w
+tx
] == 0) {
1554 if (tx
== ui
->hx
&& ty
== ui
->hy
&&
1555 ui
->hshow
&& ui
->hpencil
) {
1567 return ""; /* UI activity occurred */
1570 if (IS_CURSOR_MOVE(button
)) {
1571 move_cursor(button
, &ui
->hx
, &ui
->hy
, w
, w
, 0);
1572 ui
->hshow
= ui
->hcursor
= 1;
1576 (button
== CURSOR_SELECT
)) {
1577 ui
->hpencil
= 1 - ui
->hpencil
;
1583 ((button
>= '0' && button
<= '9' && button
- '0' <= w
) ||
1584 button
== CURSOR_SELECT2
|| button
== '\b')) {
1585 int n
= button
- '0';
1586 if (button
== CURSOR_SELECT2
|| button
== '\b')
1590 * Can't make pencil marks in a filled square. This can only
1591 * become highlighted if we're using cursor keys.
1593 if (ui
->hpencil
&& state
->grid
[ui
->hy
*w
+ui
->hx
])
1596 sprintf(buf
, "%c%d,%d,%d",
1597 (char)(ui
->hpencil
&& n
> 0 ?
'P' : 'R'), ui
->hx
, ui
->hy
, n
);
1599 if (!ui
->hcursor
) ui
->hshow
= 0;
1604 if (button
== 'M' || button
== 'm')
1610 static game_state
*execute_move(game_state
*from
, char *move
)
1612 int w
= from
->par
.w
, a
= w
*w
;
1616 if (move
[0] == 'S') {
1617 ret
= dup_game(from
);
1618 ret
->completed
= ret
->cheated
= TRUE
;
1620 for (i
= 0; i
< a
; i
++) {
1621 if (move
[i
+1] < '1' || move
[i
+1] > '0'+w
) {
1625 ret
->grid
[i
] = move
[i
+1] - '0';
1629 if (move
[a
+1] != '\0') {
1635 } else if ((move
[0] == 'P' || move
[0] == 'R') &&
1636 sscanf(move
+1, "%d,%d,%d", &x
, &y
, &n
) == 3 &&
1637 x
>= 0 && x
< w
&& y
>= 0 && y
< w
&& n
>= 0 && n
<= w
) {
1639 ret
= dup_game(from
);
1640 if (move
[0] == 'P' && n
> 0) {
1641 ret
->pencil
[y
*w
+x
] ^= 1 << n
;
1643 ret
->grid
[y
*w
+x
] = n
;
1644 ret
->pencil
[y
*w
+x
] = 0;
1646 if (!ret
->completed
&& !check_errors(ret
, NULL
))
1647 ret
->completed
= TRUE
;
1650 } else if (move
[0] == 'M') {
1652 * Fill in absolutely all pencil marks everywhere. (I
1653 * wouldn't use this for actual play, but it's a handy
1654 * starting point when following through a set of
1655 * diagnostics output by the standalone solver.)
1657 ret
= dup_game(from
);
1658 for (i
= 0; i
< a
; i
++) {
1660 ret
->pencil
[i
] = (1 << (w
+1)) - (1 << 1);
1664 return NULL
; /* couldn't parse move string */
1667 /* ----------------------------------------------------------------------
1671 #define SIZE(w) ((w) * TILESIZE + 2*BORDER)
1673 static void game_compute_size(game_params
*params
, int tilesize
,
1676 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1677 struct { int tilesize
; } ads
, *ds
= &ads
;
1678 ads
.tilesize
= tilesize
;
1680 *x
= *y
= SIZE(params
->w
);
1683 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1684 game_params
*params
, int tilesize
)
1686 ds
->tilesize
= tilesize
;
1689 static float *game_colours(frontend
*fe
, int *ncolours
)
1691 float *ret
= snewn(3 * NCOLOURS
, float);
1693 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1695 ret
[COL_GRID
* 3 + 0] = 0.0F
;
1696 ret
[COL_GRID
* 3 + 1] = 0.0F
;
1697 ret
[COL_GRID
* 3 + 2] = 0.0F
;
1699 ret
[COL_USER
* 3 + 0] = 0.0F
;
1700 ret
[COL_USER
* 3 + 1] = 0.6F
* ret
[COL_BACKGROUND
* 3 + 1];
1701 ret
[COL_USER
* 3 + 2] = 0.0F
;
1703 ret
[COL_HIGHLIGHT
* 3 + 0] = 0.78F
* ret
[COL_BACKGROUND
* 3 + 0];
1704 ret
[COL_HIGHLIGHT
* 3 + 1] = 0.78F
* ret
[COL_BACKGROUND
* 3 + 1];
1705 ret
[COL_HIGHLIGHT
* 3 + 2] = 0.78F
* ret
[COL_BACKGROUND
* 3 + 2];
1707 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
1708 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
1709 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
1711 ret
[COL_PENCIL
* 3 + 0] = 0.5F
* ret
[COL_BACKGROUND
* 3 + 0];
1712 ret
[COL_PENCIL
* 3 + 1] = 0.5F
* ret
[COL_BACKGROUND
* 3 + 1];
1713 ret
[COL_PENCIL
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2];
1715 *ncolours
= NCOLOURS
;
1719 static const char *const minus_signs
[] = { "\xE2\x88\x92", "-" };
1720 static const char *const times_signs
[] = { "\xC3\x97", "*" };
1721 static const char *const divide_signs
[] = { "\xC3\xB7", "/" };
1723 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1725 int w
= state
->par
.w
, a
= w
*w
;
1726 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1730 ds
->started
= FALSE
;
1731 ds
->tiles
= snewn(a
, long);
1732 for (i
= 0; i
< a
; i
++)
1734 ds
->errors
= snewn(a
, long);
1735 ds
->minus_sign
= text_fallback(dr
, minus_signs
, lenof(minus_signs
));
1736 ds
->times_sign
= text_fallback(dr
, times_signs
, lenof(times_signs
));
1737 ds
->divide_sign
= text_fallback(dr
, divide_signs
, lenof(divide_signs
));
1742 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1746 sfree(ds
->minus_sign
);
1747 sfree(ds
->times_sign
);
1748 sfree(ds
->divide_sign
);
1752 static void draw_tile(drawing
*dr
, game_drawstate
*ds
, struct clues
*clues
,
1753 int x
, int y
, long tile
)
1755 int w
= clues
->w
/* , a = w*w */;
1760 tx
= BORDER
+ x
* TILESIZE
+ 1 + GRIDEXTRA
;
1761 ty
= BORDER
+ y
* TILESIZE
+ 1 + GRIDEXTRA
;
1765 cw
= tw
= TILESIZE
-1-2*GRIDEXTRA
;
1766 ch
= th
= TILESIZE
-1-2*GRIDEXTRA
;
1768 if (x
> 0 && dsf_canonify(clues
->dsf
, y
*w
+x
) == dsf_canonify(clues
->dsf
, y
*w
+x
-1))
1769 cx
-= GRIDEXTRA
, cw
+= GRIDEXTRA
;
1770 if (x
+1 < w
&& dsf_canonify(clues
->dsf
, y
*w
+x
) == dsf_canonify(clues
->dsf
, y
*w
+x
+1))
1772 if (y
> 0 && dsf_canonify(clues
->dsf
, y
*w
+x
) == dsf_canonify(clues
->dsf
, (y
-1)*w
+x
))
1773 cy
-= GRIDEXTRA
, ch
+= GRIDEXTRA
;
1774 if (y
+1 < w
&& dsf_canonify(clues
->dsf
, y
*w
+x
) == dsf_canonify(clues
->dsf
, (y
+1)*w
+x
))
1777 clip(dr
, cx
, cy
, cw
, ch
);
1779 /* background needs erasing */
1780 draw_rect(dr
, cx
, cy
, cw
, ch
,
1781 (tile
& DF_HIGHLIGHT
) ? COL_HIGHLIGHT
: COL_BACKGROUND
);
1784 * Draw the corners of thick lines in corner-adjacent squares,
1785 * which jut into this square by one pixel.
1787 if (x
> 0 && y
> 0 && dsf_canonify(clues
->dsf
, y
*w
+x
) != dsf_canonify(clues
->dsf
, (y
-1)*w
+x
-1))
1788 draw_rect(dr
, tx
-GRIDEXTRA
, ty
-GRIDEXTRA
, GRIDEXTRA
, GRIDEXTRA
, COL_GRID
);
1789 if (x
+1 < w
&& y
> 0 && dsf_canonify(clues
->dsf
, y
*w
+x
) != dsf_canonify(clues
->dsf
, (y
-1)*w
+x
+1))
1790 draw_rect(dr
, tx
+TILESIZE
-1-2*GRIDEXTRA
, ty
-GRIDEXTRA
, GRIDEXTRA
, GRIDEXTRA
, COL_GRID
);
1791 if (x
> 0 && y
+1 < w
&& dsf_canonify(clues
->dsf
, y
*w
+x
) != dsf_canonify(clues
->dsf
, (y
+1)*w
+x
-1))
1792 draw_rect(dr
, tx
-GRIDEXTRA
, ty
+TILESIZE
-1-2*GRIDEXTRA
, GRIDEXTRA
, GRIDEXTRA
, COL_GRID
);
1793 if (x
+1 < w
&& y
+1 < w
&& dsf_canonify(clues
->dsf
, y
*w
+x
) != dsf_canonify(clues
->dsf
, (y
+1)*w
+x
+1))
1794 draw_rect(dr
, tx
+TILESIZE
-1-2*GRIDEXTRA
, ty
+TILESIZE
-1-2*GRIDEXTRA
, GRIDEXTRA
, GRIDEXTRA
, COL_GRID
);
1796 /* pencil-mode highlight */
1797 if (tile
& DF_HIGHLIGHT_PENCIL
) {
1801 coords
[2] = cx
+cw
/2;
1804 coords
[5] = cy
+ch
/2;
1805 draw_polygon(dr
, coords
, 3, COL_HIGHLIGHT
, COL_HIGHLIGHT
);
1808 /* Draw the box clue. */
1809 if (dsf_canonify(clues
->dsf
, y
*w
+x
) == y
*w
+x
) {
1810 long clue
= clues
->clues
[y
*w
+x
];
1811 long cluetype
= clue
& CMASK
, clueval
= clue
& ~CMASK
;
1812 int size
= dsf_size(clues
->dsf
, y
*w
+x
);
1814 * Special case of clue-drawing: a box with only one square
1815 * is written as just the number, with no operation, because
1816 * it doesn't matter whether the operation is ADD or MUL.
1817 * The generation code above should never produce puzzles
1818 * containing such a thing - I think they're inelegant - but
1819 * it's possible to type in game IDs from elsewhere, so I
1820 * want to display them right if so.
1822 sprintf (str
, "%ld%s", clueval
,
1824 cluetype
== C_ADD ?
"+" :
1825 cluetype
== C_SUB ? ds
->minus_sign
:
1826 cluetype
== C_MUL ? ds
->times_sign
:
1827 /* cluetype == C_DIV ? */ ds
->divide_sign
));
1828 draw_text(dr
, tx
+ GRIDEXTRA
* 2, ty
+ GRIDEXTRA
* 2 + TILESIZE
/4,
1829 FONT_VARIABLE
, TILESIZE
/4, ALIGN_VNORMAL
| ALIGN_HLEFT
,
1830 (tile
& DF_ERR_CLUE ? COL_ERROR
: COL_GRID
), str
);
1833 /* new number needs drawing? */
1834 if (tile
& DF_DIGIT_MASK
) {
1836 str
[0] = (tile
& DF_DIGIT_MASK
) + '0';
1837 draw_text(dr
, tx
+ TILESIZE
/2, ty
+ TILESIZE
/2,
1838 FONT_VARIABLE
, TILESIZE
/2, ALIGN_VCENTRE
| ALIGN_HCENTRE
,
1839 (tile
& DF_ERR_LATIN
) ? COL_ERROR
: COL_USER
, str
);
1844 int pw
, ph
, minph
, pbest
, fontsize
;
1846 /* Count the pencil marks required. */
1847 for (i
= 1, npencil
= 0; i
<= w
; i
++)
1848 if (tile
& (1L << (i
+ DF_PENCIL_SHIFT
)))
1855 * Determine the bounding rectangle within which we're going
1856 * to put the pencil marks.
1858 /* Start with the whole square */
1859 pl
= tx
+ GRIDEXTRA
;
1860 pr
= pl
+ TILESIZE
- GRIDEXTRA
;
1861 pt
= ty
+ GRIDEXTRA
;
1862 pb
= pt
+ TILESIZE
- GRIDEXTRA
;
1863 if (dsf_canonify(clues
->dsf
, y
*w
+x
) == y
*w
+x
) {
1865 * Make space for the clue text.
1872 * We arrange our pencil marks in a grid layout, with
1873 * the number of rows and columns adjusted to allow the
1874 * maximum font size.
1876 * So now we work out what the grid size ought to be.
1881 for (pw
= 3; pw
< max(npencil
,4); pw
++) {
1884 ph
= (npencil
+ pw
- 1) / pw
;
1885 ph
= max(ph
, minph
);
1886 fw
= (pr
- pl
) / (float)pw
;
1887 fh
= (pb
- pt
) / (float)ph
;
1889 if (fs
> bestsize
) {
1896 ph
= (npencil
+ pw
- 1) / pw
;
1897 ph
= max(ph
, minph
);
1900 * Now we've got our grid dimensions, work out the pixel
1901 * size of a grid element, and round it to the nearest
1902 * pixel. (We don't want rounding errors to make the
1903 * grid look uneven at low pixel sizes.)
1905 fontsize
= min((pr
- pl
) / pw
, (pb
- pt
) / ph
);
1908 * Centre the resulting figure in the square.
1910 pl
= tx
+ (TILESIZE
- fontsize
* pw
) / 2;
1911 pt
= ty
+ (TILESIZE
- fontsize
* ph
) / 2;
1914 * And move it down a bit if it's collided with some
1917 if (dsf_canonify(clues
->dsf
, y
*w
+x
) == y
*w
+x
) {
1918 pt
= max(pt
, ty
+ GRIDEXTRA
* 3 + TILESIZE
/4);
1922 * Now actually draw the pencil marks.
1924 for (i
= 1, j
= 0; i
<= w
; i
++)
1925 if (tile
& (1L << (i
+ DF_PENCIL_SHIFT
))) {
1926 int dx
= j
% pw
, dy
= j
/ pw
;
1930 draw_text(dr
, pl
+ fontsize
* (2*dx
+1) / 2,
1931 pt
+ fontsize
* (2*dy
+1) / 2,
1932 FONT_VARIABLE
, fontsize
,
1933 ALIGN_VCENTRE
| ALIGN_HCENTRE
, COL_PENCIL
, str
);
1941 draw_update(dr
, cx
, cy
, cw
, ch
);
1944 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1945 game_state
*state
, int dir
, game_ui
*ui
,
1946 float animtime
, float flashtime
)
1948 int w
= state
->par
.w
/*, a = w*w */;
1953 * The initial contents of the window are not guaranteed and
1954 * can vary with front ends. To be on the safe side, all
1955 * games should start by drawing a big background-colour
1956 * rectangle covering the whole window.
1958 draw_rect(dr
, 0, 0, SIZE(w
), SIZE(w
), COL_BACKGROUND
);
1961 * Big containing rectangle.
1963 draw_rect(dr
, COORD(0) - GRIDEXTRA
, COORD(0) - GRIDEXTRA
,
1964 w
*TILESIZE
+1+GRIDEXTRA
*2, w
*TILESIZE
+1+GRIDEXTRA
*2,
1967 draw_update(dr
, 0, 0, SIZE(w
), SIZE(w
));
1972 check_errors(state
, ds
->errors
);
1974 for (y
= 0; y
< w
; y
++) {
1975 for (x
= 0; x
< w
; x
++) {
1978 if (state
->grid
[y
*w
+x
])
1979 tile
= state
->grid
[y
*w
+x
];
1981 tile
= (long)state
->pencil
[y
*w
+x
] << DF_PENCIL_SHIFT
;
1983 if (ui
->hshow
&& ui
->hx
== x
&& ui
->hy
== y
)
1984 tile
|= (ui
->hpencil ? DF_HIGHLIGHT_PENCIL
: DF_HIGHLIGHT
);
1986 if (flashtime
> 0 &&
1987 (flashtime
<= FLASH_TIME
/3 ||
1988 flashtime
>= FLASH_TIME
*2/3))
1989 tile
|= DF_HIGHLIGHT
; /* completion flash */
1991 tile
|= ds
->errors
[y
*w
+x
];
1993 if (ds
->tiles
[y
*w
+x
] != tile
) {
1994 ds
->tiles
[y
*w
+x
] = tile
;
1995 draw_tile(dr
, ds
, state
->clues
, x
, y
, tile
);
2001 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2002 int dir
, game_ui
*ui
)
2007 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2008 int dir
, game_ui
*ui
)
2010 if (!oldstate
->completed
&& newstate
->completed
&&
2011 !oldstate
->cheated
&& !newstate
->cheated
)
2016 static int game_timing_state(game_state
*state
, game_ui
*ui
)
2018 if (state
->completed
)
2023 static void game_print_size(game_params
*params
, float *x
, float *y
)
2028 * We use 9mm squares by default, like Solo.
2030 game_compute_size(params
, 900, &pw
, &ph
);
2036 * Subfunction to draw the thick lines between cells. In order to do
2037 * this using the line-drawing rather than rectangle-drawing API (so
2038 * as to get line thicknesses to scale correctly) and yet have
2039 * correctly mitred joins between lines, we must do this by tracing
2040 * the boundary of each sub-block and drawing it in one go as a
2043 static void outline_block_structure(drawing
*dr
, game_drawstate
*ds
,
2044 int w
, int *dsf
, int ink
)
2049 int x
, y
, dx
, dy
, sx
, sy
, sdx
, sdy
;
2051 coords
= snewn(4*a
, int);
2054 * Iterate over all the blocks.
2056 for (i
= 0; i
< a
; i
++) {
2057 if (dsf_canonify(dsf
, i
) != i
)
2061 * For each block, we need a starting square within it which
2062 * has a boundary at the left. Conveniently, we have one
2063 * right here, by construction.
2071 * Now begin tracing round the perimeter. At all
2072 * times, (x,y) describes some square within the
2073 * block, and (x+dx,y+dy) is some adjacent square
2074 * outside it; so the edge between those two squares
2075 * is always an edge of the block.
2077 sx
= x
, sy
= y
, sdx
= dx
, sdy
= dy
; /* save starting position */
2080 int cx
, cy
, tx
, ty
, nin
;
2083 * Advance to the next edge, by looking at the two
2084 * squares beyond it. If they're both outside the block,
2085 * we turn right (by leaving x,y the same and rotating
2086 * dx,dy clockwise); if they're both inside, we turn
2087 * left (by rotating dx,dy anticlockwise and contriving
2088 * to leave x+dx,y+dy unchanged); if one of each, we go
2089 * straight on (and may enforce by assertion that
2090 * they're one of each the _right_ way round).
2095 nin
+= (tx
>= 0 && tx
< w
&& ty
>= 0 && ty
< w
&&
2096 dsf_canonify(dsf
, ty
*w
+tx
) == i
);
2099 nin
+= (tx
>= 0 && tx
< w
&& ty
>= 0 && ty
< w
&&
2100 dsf_canonify(dsf
, ty
*w
+tx
) == i
);
2109 } else if (nin
== 2) {
2133 * Now enforce by assertion that we ended up
2134 * somewhere sensible.
2136 assert(x
>= 0 && x
< w
&& y
>= 0 && y
< w
&&
2137 dsf_canonify(dsf
, y
*w
+x
) == i
);
2138 assert(x
+dx
< 0 || x
+dx
>= w
|| y
+dy
< 0 || y
+dy
>= w
||
2139 dsf_canonify(dsf
, (y
+dy
)*w
+(x
+dx
)) != i
);
2142 * Record the point we just went past at one end of the
2143 * edge. To do this, we translate (x,y) down and right
2144 * by half a unit (so they're describing a point in the
2145 * _centre_ of the square) and then translate back again
2146 * in a manner rotated by dy and dx.
2149 cx
= ((2*x
+1) + dy
+ dx
) / 2;
2150 cy
= ((2*y
+1) - dx
+ dy
) / 2;
2151 coords
[2*n
+0] = BORDER
+ cx
* TILESIZE
;
2152 coords
[2*n
+1] = BORDER
+ cy
* TILESIZE
;
2155 } while (x
!= sx
|| y
!= sy
|| dx
!= sdx
|| dy
!= sdy
);
2158 * That's our polygon; now draw it.
2160 draw_polygon(dr
, coords
, n
, -1, ink
);
2166 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
2168 int w
= state
->par
.w
;
2169 int ink
= print_mono_colour(dr
, 0);
2171 char *minus_sign
, *times_sign
, *divide_sign
;
2173 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2174 game_drawstate ads
, *ds
= &ads
;
2175 game_set_size(dr
, ds
, NULL
, tilesize
);
2177 minus_sign
= text_fallback(dr
, minus_signs
, lenof(minus_signs
));
2178 times_sign
= text_fallback(dr
, times_signs
, lenof(times_signs
));
2179 divide_sign
= text_fallback(dr
, divide_signs
, lenof(divide_signs
));
2184 print_line_width(dr
, 3 * TILESIZE
/ 40);
2185 draw_rect_outline(dr
, BORDER
, BORDER
, w
*TILESIZE
, w
*TILESIZE
, ink
);
2190 for (x
= 1; x
< w
; x
++) {
2191 print_line_width(dr
, TILESIZE
/ 40);
2192 draw_line(dr
, BORDER
+x
*TILESIZE
, BORDER
,
2193 BORDER
+x
*TILESIZE
, BORDER
+w
*TILESIZE
, ink
);
2195 for (y
= 1; y
< w
; y
++) {
2196 print_line_width(dr
, TILESIZE
/ 40);
2197 draw_line(dr
, BORDER
, BORDER
+y
*TILESIZE
,
2198 BORDER
+w
*TILESIZE
, BORDER
+y
*TILESIZE
, ink
);
2202 * Thick lines between cells.
2204 print_line_width(dr
, 3 * TILESIZE
/ 40);
2205 outline_block_structure(dr
, ds
, w
, state
->clues
->dsf
, ink
);
2210 for (y
= 0; y
< w
; y
++)
2211 for (x
= 0; x
< w
; x
++)
2212 if (dsf_canonify(state
->clues
->dsf
, y
*w
+x
) == y
*w
+x
) {
2213 long clue
= state
->clues
->clues
[y
*w
+x
];
2214 long cluetype
= clue
& CMASK
, clueval
= clue
& ~CMASK
;
2215 int size
= dsf_size(state
->clues
->dsf
, y
*w
+x
);
2219 * As in the drawing code, we omit the operator for
2222 sprintf (str
, "%ld%s", clueval
,
2224 cluetype
== C_ADD ?
"+" :
2225 cluetype
== C_SUB ? minus_sign
:
2226 cluetype
== C_MUL ? times_sign
:
2227 /* cluetype == C_DIV ? */ divide_sign
));
2230 BORDER
+x
*TILESIZE
+ 5*TILESIZE
/80,
2231 BORDER
+y
*TILESIZE
+ 20*TILESIZE
/80,
2232 FONT_VARIABLE
, TILESIZE
/4,
2233 ALIGN_VNORMAL
| ALIGN_HLEFT
,
2238 * Numbers for the solution, if any.
2240 for (y
= 0; y
< w
; y
++)
2241 for (x
= 0; x
< w
; x
++)
2242 if (state
->grid
[y
*w
+x
]) {
2245 str
[0] = state
->grid
[y
*w
+x
] + '0';
2246 draw_text(dr
, BORDER
+ x
*TILESIZE
+ TILESIZE
/2,
2247 BORDER
+ y
*TILESIZE
+ TILESIZE
/2,
2248 FONT_VARIABLE
, TILESIZE
/2,
2249 ALIGN_VCENTRE
| ALIGN_HCENTRE
, ink
, str
);
2258 #define thegame keen
2261 const struct game thegame
= {
2262 "Keen", "games.keen", "keen",
2269 TRUE
, game_configure
, custom_params
,
2277 FALSE
, game_can_format_as_text_now
, game_text_format
,
2285 PREFERRED_TILESIZE
, game_compute_size
, game_set_size
,
2288 game_free_drawstate
,
2292 TRUE
, FALSE
, game_print_size
, game_print
,
2293 FALSE
, /* wants_statusbar */
2294 FALSE
, game_timing_state
,
2295 REQUIRE_RBUTTON
| REQUIRE_NUMPAD
, /* flags */
2298 #ifdef STANDALONE_SOLVER
2302 int main(int argc
, char **argv
)
2306 char *id
= NULL
, *desc
, *err
;
2308 int ret
, diff
, really_show_working
= FALSE
;
2310 while (--argc
> 0) {
2312 if (!strcmp(p
, "-v")) {
2313 really_show_working
= TRUE
;
2314 } else if (!strcmp(p
, "-g")) {
2316 } else if (*p
== '-') {
2317 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
2325 fprintf(stderr
, "usage: %s [-g | -v] <game_id>\n", argv
[0]);
2329 desc
= strchr(id
, ':');
2331 fprintf(stderr
, "%s: game id expects a colon in it\n", argv
[0]);
2336 p
= default_params();
2337 decode_params(p
, id
);
2338 err
= validate_desc(p
, desc
);
2340 fprintf(stderr
, "%s: %s\n", argv
[0], err
);
2343 s
= new_game(NULL
, p
, desc
);
2346 * When solving an Easy puzzle, we don't want to bother the
2347 * user with Hard-level deductions. For this reason, we grade
2348 * the puzzle internally before doing anything else.
2350 ret
= -1; /* placate optimiser */
2351 solver_show_working
= FALSE
;
2352 for (diff
= 0; diff
< DIFFCOUNT
; diff
++) {
2353 memset(s
->grid
, 0, p
->w
* p
->w
);
2354 ret
= solver(p
->w
, s
->clues
->dsf
, s
->clues
->clues
,
2360 if (diff
== DIFFCOUNT
) {
2362 printf("Difficulty rating: ambiguous\n");
2364 printf("Unable to find a unique solution\n");
2367 if (ret
== diff_impossible
)
2368 printf("Difficulty rating: impossible (no solution exists)\n");
2370 printf("Difficulty rating: %s\n", keen_diffnames
[ret
]);
2372 solver_show_working
= really_show_working
;
2373 memset(s
->grid
, 0, p
->w
* p
->w
);
2374 ret
= solver(p
->w
, s
->clues
->dsf
, s
->clues
->clues
,
2377 printf("Puzzle is inconsistent\n");
2380 * We don't have a game_text_format for this game,
2381 * so we have to output the solution manually.
2384 for (y
= 0; y
< p
->w
; y
++) {
2385 for (x
= 0; x
< p
->w
; x
++) {
2386 printf("%s%c", x
>0?
" ":"", '0' + s
->grid
[y
*p
->w
+x
]);
2399 /* vim: set shiftwidth=4 tabstop=8: */