2 * unruly.c: Implementation for Binary Puzzles.
3 * (C) 2012 Lennard Sprong
4 * Created for Simon Tatham's Portable Puzzle Collection
5 * See LICENCE for licence details
7 * Objective of the game: Fill the grid with zeros and ones, with the
9 * - There can't be a run of three or more equal numbers.
10 * - Each row and column contains an equal amount of zeros and ones.
12 * This puzzle type is known under several names, including
13 * Tohu-Wa-Vohu, One and Two and Binairo.
15 * Some variants include an extra constraint, stating that no two rows or two
16 * columns may contain the same exact sequence of zeros and ones.
17 * This rule is rarely used, so it has been discarded for this implementation.
20 * http://www.janko.at/Raetsel/Tohu-Wa-Vohu/index.htm
24 * Possible future improvements:
26 * More solver cleverness
28 * - a counting-based deduction in which you find groups of squares
29 * which must each contain at least one of a given colour, plus
30 * other squares which are already known to be that colour, and see
31 * if you have any squares left over when you've worked out where
32 * they all have to be. This is a generalisation of the current
33 * check_near_complete: where that only covers rows with three
34 * unfilled squares, this would handle more, such as
36 * in which each of the two-square gaps must contain a 0, and there
37 * are three 0s placed, and that means the rightmost square can't
40 * - an 'Unreasonable' difficulty level, supporting recursion and
53 #ifdef STANDALONE_SOLVER
54 int solver_verbose
= FALSE
;
62 * When editing this enum, maintain the invariants
63 * COL_n_HIGHLIGHT = COL_n + 1
64 * COL_n_LOWLIGHT = COL_n + 2
78 int w2
, h2
; /* full grid width and height respectively */
85 #define ENUM(upper,title,lower) DIFF_ ## upper,
86 #define TITLE(upper,title,lower) #title,
87 #define ENCODE(upper,title,lower) #lower
88 #define CONFIG(upper,title,lower) ":" #title
89 enum { DIFFLIST(ENUM
) DIFFCOUNT
};
90 static char const *const unruly_diffnames
[] = { DIFFLIST(TITLE
) };
92 static char const unruly_diffchars
[] = DIFFLIST(ENCODE
);
93 #define DIFFCONFIG DIFFLIST(CONFIG)
95 const static struct game_params unruly_presets
[] = {
99 {10, 10, DIFF_NORMAL
},
101 {14, 14, DIFF_NORMAL
}
104 #define DEFAULT_PRESET 0
113 #define FE_HOR_ROW_LEFT 0x001
114 #define FE_HOR_ROW_MID 0x003
115 #define FE_HOR_ROW_RIGHT 0x002
117 #define FE_VER_ROW_TOP 0x004
118 #define FE_VER_ROW_MID 0x00C
119 #define FE_VER_ROW_BOTTOM 0x008
121 #define FE_COUNT 0x010
124 #define FF_ZERO 0x040
125 #define FF_CURSOR 0x080
127 #define FF_FLASH1 0x100
128 #define FF_FLASH2 0x200
129 #define FF_IMMUTABLE 0x400
134 unsigned char *immutable
;
136 int completed
, cheated
;
139 static game_params
*default_params(void)
141 game_params
*ret
= snew(game_params
);
143 *ret
= unruly_presets
[DEFAULT_PRESET
]; /* structure copy */
148 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
153 if (i
< 0 || i
>= lenof(unruly_presets
))
156 ret
= snew(game_params
);
157 *ret
= unruly_presets
[i
]; /* structure copy */
159 sprintf(buf
, "%dx%d %s", ret
->w2
, ret
->h2
, unruly_diffnames
[ret
->diff
]);
166 static void free_params(game_params
*params
)
171 static game_params
*dup_params(game_params
*params
)
173 game_params
*ret
= snew(game_params
);
174 *ret
= *params
; /* structure copy */
178 static void decode_params(game_params
*params
, char const *string
)
180 char const *p
= string
;
182 params
->w2
= atoi(p
);
183 while (*p
&& isdigit((unsigned char)*p
)) p
++;
186 params
->h2
= atoi(p
);
187 while (*p
&& isdigit((unsigned char)*p
)) p
++;
189 params
->h2
= params
->w2
;
195 params
->diff
= DIFFCOUNT
+ 1; /* ...which is invalid */
197 for (i
= 0; i
< DIFFCOUNT
; i
++) {
198 if (*p
== unruly_diffchars
[i
])
206 static char *encode_params(game_params
*params
, int full
)
210 sprintf(buf
, "%dx%d", params
->w2
, params
->h2
);
212 sprintf(buf
+ strlen(buf
), "d%c", unruly_diffchars
[params
->diff
]);
217 static config_item
*game_configure(game_params
*params
)
222 ret
= snewn(4, config_item
);
224 ret
[0].name
= "Width";
225 ret
[0].type
= C_STRING
;
226 sprintf(buf
, "%d", params
->w2
);
227 ret
[0].sval
= dupstr(buf
);
230 ret
[1].name
= "Height";
231 ret
[1].type
= C_STRING
;
232 sprintf(buf
, "%d", params
->h2
);
233 ret
[1].sval
= dupstr(buf
);
236 ret
[2].name
= "Difficulty";
237 ret
[2].type
= C_CHOICES
;
238 ret
[2].sval
= DIFFCONFIG
;
239 ret
[2].ival
= params
->diff
;
249 static game_params
*custom_params(config_item
*cfg
)
251 game_params
*ret
= snew(game_params
);
253 ret
->w2
= atoi(cfg
[0].sval
);
254 ret
->h2
= atoi(cfg
[1].sval
);
255 ret
->diff
= cfg
[2].ival
;
260 static char *validate_params(game_params
*params
, int full
)
262 if ((params
->w2
& 1) || (params
->h2
& 1))
263 return "Width and height must both be even";
264 if (params
->w2
< 6 || params
->h2
< 6)
265 return "Width and height must be at least 6";
266 if (params
->diff
>= DIFFCOUNT
)
267 return "Unknown difficulty rating";
272 static char *validate_desc(game_params
*params
, char *desc
)
274 int w2
= params
->w2
, h2
= params
->h2
;
281 if (*p
>= 'a' && *p
< 'z')
282 pos
+= 1 + (*p
- 'a');
283 else if (*p
>= 'A' && *p
< 'Z')
284 pos
+= 1 + (*p
- 'A');
285 else if (*p
== 'Z' || *p
== 'z')
288 return "Description contains invalid characters";
294 return "Description too short";
296 return "Description too long";
301 static game_state
*blank_state(int w2
, int h2
)
303 game_state
*state
= snew(game_state
);
308 state
->grid
= snewn(s
, char);
309 state
->immutable
= snewn(s
, unsigned char);
311 memset(state
->grid
, EMPTY
, s
);
312 memset(state
->immutable
, FALSE
, s
);
314 state
->completed
= state
->cheated
= FALSE
;
319 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
321 int w2
= params
->w2
, h2
= params
->h2
;
324 game_state
*state
= blank_state(w2
, h2
);
330 if (*p
>= 'a' && *p
< 'z') {
333 state
->grid
[pos
] = N_ZERO
;
334 state
->immutable
[pos
] = TRUE
;
337 } else if (*p
>= 'A' && *p
< 'Z') {
340 state
->grid
[pos
] = N_ONE
;
341 state
->immutable
[pos
] = TRUE
;
344 } else if (*p
== 'Z' || *p
== 'z') {
347 assert(!"Description contains invalid characters");
356 static game_state
*dup_game(game_state
*state
)
358 int w2
= state
->w2
, h2
= state
->h2
;
361 game_state
*ret
= blank_state(w2
, h2
);
363 memcpy(ret
->grid
, state
->grid
, s
);
364 memcpy(ret
->immutable
, state
->immutable
, s
);
366 ret
->completed
= state
->completed
;
367 ret
->cheated
= state
->cheated
;
372 static void free_game(game_state
*state
)
375 sfree(state
->immutable
);
380 static int game_can_format_as_text_now(game_params
*params
)
385 static char *game_text_format(game_state
*state
)
387 int w2
= state
->w2
, h2
= state
->h2
;
390 char *ret
= snewn(lr
* h2
+ 1, char);
394 for (y
= 0; y
< h2
; y
++) {
395 for (x
= 0; x
< w2
; x
++) {
397 char c
= state
->grid
[y
* w2
+ x
];
398 *p
++ = (c
== N_ONE ?
'1' : c
== N_ZERO ?
'0' : '.');
414 struct unruly_scratch
{
421 static void unruly_solver_update_remaining(game_state
*state
,
422 struct unruly_scratch
*scratch
)
424 int w2
= state
->w2
, h2
= state
->h2
;
427 /* Reset all scratch data */
428 memset(scratch
->ones_rows
, 0, h2
* sizeof(int));
429 memset(scratch
->ones_cols
, 0, w2
* sizeof(int));
430 memset(scratch
->zeros_rows
, 0, h2
* sizeof(int));
431 memset(scratch
->zeros_cols
, 0, w2
* sizeof(int));
433 for (x
= 0; x
< w2
; x
++)
434 for (y
= 0; y
< h2
; y
++) {
435 if (state
->grid
[y
* w2
+ x
] == N_ONE
) {
436 scratch
->ones_rows
[y
]++;
437 scratch
->ones_cols
[x
]++;
438 } else if (state
->grid
[y
* w2
+ x
] == N_ZERO
) {
439 scratch
->zeros_rows
[y
]++;
440 scratch
->zeros_cols
[x
]++;
445 static struct unruly_scratch
*unruly_new_scratch(game_state
*state
)
447 int w2
= state
->w2
, h2
= state
->h2
;
449 struct unruly_scratch
*ret
= snew(struct unruly_scratch
);
451 ret
->ones_rows
= snewn(h2
, int);
452 ret
->ones_cols
= snewn(w2
, int);
453 ret
->zeros_rows
= snewn(h2
, int);
454 ret
->zeros_cols
= snewn(w2
, int);
456 unruly_solver_update_remaining(state
, ret
);
461 static void unruly_free_scratch(struct unruly_scratch
*scratch
)
463 sfree(scratch
->ones_rows
);
464 sfree(scratch
->ones_cols
);
465 sfree(scratch
->zeros_rows
);
466 sfree(scratch
->zeros_cols
);
471 static int unruly_solver_check_threes(game_state
*state
, int *rowcount
,
472 int *colcount
, int horizontal
,
473 char check
, char block
)
475 int w2
= state
->w2
, h2
= state
->h2
;
477 int dx
= horizontal ?
1 : 0, dy
= 1 - dx
;
478 int sx
= dx
, sy
= dy
;
479 int ex
= w2
- dx
, ey
= h2
- dy
;
484 /* Check for any three squares which almost form three in a row */
485 for (y
= sy
; y
< ey
; y
++) {
486 for (x
= sx
; x
< ex
; x
++) {
487 int i1
= (y
-dy
) * w2
+ (x
-dx
);
489 int i3
= (y
+dy
) * w2
+ (x
+dx
);
491 if (state
->grid
[i1
] == check
&& state
->grid
[i2
] == check
492 && state
->grid
[i3
] == EMPTY
) {
494 #ifdef STANDALONE_SOLVER
495 if (solver_verbose
) {
496 printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n",
497 i1
% w2
, i1
/ w2
, i2
% w2
, i2
/ w2
,
498 (block
== N_ONE ?
'1' : '0'), i3
% w2
,
502 state
->grid
[i3
] = block
;
506 if (state
->grid
[i1
] == check
&& state
->grid
[i2
] == EMPTY
507 && state
->grid
[i3
] == check
) {
509 #ifdef STANDALONE_SOLVER
510 if (solver_verbose
) {
511 printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n",
512 i1
% w2
, i1
/ w2
, i3
% w2
, i3
/ w2
,
513 (block
== N_ONE ?
'1' : '0'), i2
% w2
,
517 state
->grid
[i2
] = block
;
521 if (state
->grid
[i1
] == EMPTY
&& state
->grid
[i2
] == check
522 && state
->grid
[i3
] == check
) {
524 #ifdef STANDALONE_SOLVER
525 if (solver_verbose
) {
526 printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n",
527 i2
% w2
, i2
/ w2
, i3
% w2
, i3
/ w2
,
528 (block
== N_ONE ?
'1' : '0'), i1
% w2
,
532 state
->grid
[i1
] = block
;
542 static int unruly_solver_check_all_threes(game_state
*state
,
543 struct unruly_scratch
*scratch
)
548 unruly_solver_check_threes(state
, scratch
->zeros_rows
,
549 scratch
->zeros_cols
, TRUE
, N_ONE
, N_ZERO
);
551 unruly_solver_check_threes(state
, scratch
->ones_rows
,
552 scratch
->ones_cols
, TRUE
, N_ZERO
, N_ONE
);
554 unruly_solver_check_threes(state
, scratch
->zeros_rows
,
555 scratch
->zeros_cols
, FALSE
, N_ONE
,
558 unruly_solver_check_threes(state
, scratch
->ones_rows
,
559 scratch
->ones_cols
, FALSE
, N_ZERO
, N_ONE
);
564 static int unruly_solver_fill_row(game_state
*state
, int i
, int horizontal
,
565 int *rowcount
, int *colcount
, char fill
)
568 int w2
= state
->w2
, h2
= state
->h2
;
571 #ifdef STANDALONE_SOLVER
572 if (solver_verbose
) {
573 printf("Solver: Filling %s %i with %c:",
574 (horizontal ?
"Row" : "Col"), i
,
575 (fill
== N_ZERO ?
'0' : '1'));
578 /* Place a number in every empty square in a row/column */
579 for (j
= 0; j
< (horizontal ? w2
: h2
); j
++) {
580 int p
= (horizontal ? i
* w2
+ j
: j
* w2
+ i
);
582 if (state
->grid
[p
] == EMPTY
) {
583 #ifdef STANDALONE_SOLVER
584 if (solver_verbose
) {
585 printf(" (%i,%i)", (horizontal ? j
: i
),
586 (horizontal ? i
: j
));
590 state
->grid
[p
] = fill
;
591 rowcount
[(horizontal ? i
: j
)]++;
592 colcount
[(horizontal ? j
: i
)]++;
596 #ifdef STANDALONE_SOLVER
597 if (solver_verbose
) {
605 static int unruly_solver_check_complete_nums(game_state
*state
,
606 int *complete
, int horizontal
,
607 int *rowcount
, int *colcount
,
610 int w2
= state
->w2
, h2
= state
->h2
;
611 int count
= (horizontal ? h2
: w2
); /* number of rows to check */
612 int target
= (horizontal ? w2
: h2
) / 2; /* target number of 0s/1s */
613 int *other
= (horizontal ? rowcount
: colcount
);
618 /* Check for completed rows/cols for one number, then fill in the rest */
619 for (i
= 0; i
< count
; i
++) {
620 if (complete
[i
] == target
&& other
[i
] < target
) {
621 #ifdef STANDALONE_SOLVER
622 if (solver_verbose
) {
623 printf("Solver: Row %i satisfied for %c\n", i
,
624 (fill
!= N_ZERO ?
'0' : '1'));
627 ret
+= unruly_solver_fill_row(state
, i
, horizontal
, rowcount
,
635 static int unruly_solver_check_all_complete_nums(game_state
*state
,
636 struct unruly_scratch
*scratch
)
641 unruly_solver_check_complete_nums(state
, scratch
->ones_rows
, TRUE
,
643 scratch
->zeros_cols
, N_ZERO
);
645 unruly_solver_check_complete_nums(state
, scratch
->ones_cols
, FALSE
,
647 scratch
->zeros_cols
, N_ZERO
);
649 unruly_solver_check_complete_nums(state
, scratch
->zeros_rows
, TRUE
,
651 scratch
->ones_cols
, N_ONE
);
653 unruly_solver_check_complete_nums(state
, scratch
->zeros_cols
, FALSE
,
655 scratch
->ones_cols
, N_ONE
);
660 static int unruly_solver_check_near_complete(game_state
*state
,
661 int *complete
, int horizontal
,
662 int *rowcount
, int *colcount
,
665 int w2
= state
->w2
, h2
= state
->h2
;
666 int w
= w2
/2, h
= h2
/2;
668 int dx
= horizontal ?
1 : 0, dy
= 1 - dx
;
670 int sx
= dx
, sy
= dy
;
671 int ex
= w2
- dx
, ey
= h2
- dy
;
677 * This function checks for a row with one Y remaining, then looks
678 * for positions that could cause the remaining squares in the row
679 * to make 3 X's in a row. Example:
681 * Consider the following row:
683 * If the last 1 was placed in the last square, the remaining
684 * squares would be 0:
686 * This violates the 3 in a row rule. We now know that the last 1
687 * shouldn't be in the last cell.
691 /* Check for any two blank and one filled square */
692 for (y
= sy
; y
< ey
; y
++) {
693 /* One type must have 1 remaining, the other at least 2 */
694 if (horizontal
&& (complete
[y
] < w
- 1 || rowcount
[y
] > w
- 2))
697 for (x
= sx
; x
< ex
; x
++) {
700 && (complete
[x
] < h
- 1 || colcount
[x
] > h
- 2))
703 i
= (horizontal ? y
: x
);
704 i1
= (y
-dy
) * w2
+ (x
-dx
);
706 i3
= (y
+dy
) * w2
+ (x
+dx
);
708 if (state
->grid
[i1
] == fill
&& state
->grid
[i2
] == EMPTY
709 && state
->grid
[i3
] == EMPTY
) {
711 * Temporarily fill the empty spaces with something else.
712 * This avoids raising the counts for the row and column
714 state
->grid
[i2
] = BOGUS
;
715 state
->grid
[i3
] = BOGUS
;
717 #ifdef STANDALONE_SOLVER
718 if (solver_verbose
) {
719 printf("Solver: Row %i nearly satisfied for %c\n", i
,
720 (fill
!= N_ZERO ?
'0' : '1'));
724 unruly_solver_fill_row(state
, i
, horizontal
, rowcount
,
727 state
->grid
[i2
] = EMPTY
;
728 state
->grid
[i3
] = EMPTY
;
731 else if (state
->grid
[i1
] == EMPTY
&& state
->grid
[i2
] == fill
732 && state
->grid
[i3
] == EMPTY
) {
733 state
->grid
[i1
] = BOGUS
;
734 state
->grid
[i3
] = BOGUS
;
736 #ifdef STANDALONE_SOLVER
737 if (solver_verbose
) {
738 printf("Solver: Row %i nearly satisfied for %c\n", i
,
739 (fill
!= N_ZERO ?
'0' : '1'));
743 unruly_solver_fill_row(state
, i
, horizontal
, rowcount
,
746 state
->grid
[i1
] = EMPTY
;
747 state
->grid
[i3
] = EMPTY
;
750 else if (state
->grid
[i1
] == EMPTY
&& state
->grid
[i2
] == EMPTY
751 && state
->grid
[i3
] == fill
) {
752 state
->grid
[i1
] = BOGUS
;
753 state
->grid
[i2
] = BOGUS
;
755 #ifdef STANDALONE_SOLVER
756 if (solver_verbose
) {
757 printf("Solver: Row %i nearly satisfied for %c\n", i
,
758 (fill
!= N_ZERO ?
'0' : '1'));
762 unruly_solver_fill_row(state
, i
, horizontal
, rowcount
,
765 state
->grid
[i1
] = EMPTY
;
766 state
->grid
[i2
] = EMPTY
;
769 else if (state
->grid
[i1
] == EMPTY
&& state
->grid
[i2
] == EMPTY
770 && state
->grid
[i3
] == EMPTY
) {
771 state
->grid
[i1
] = BOGUS
;
772 state
->grid
[i2
] = BOGUS
;
773 state
->grid
[i3
] = BOGUS
;
775 #ifdef STANDALONE_SOLVER
776 if (solver_verbose
) {
777 printf("Solver: Row %i nearly satisfied for %c\n", i
,
778 (fill
!= N_ZERO ?
'0' : '1'));
782 unruly_solver_fill_row(state
, i
, horizontal
, rowcount
,
785 state
->grid
[i1
] = EMPTY
;
786 state
->grid
[i2
] = EMPTY
;
787 state
->grid
[i3
] = EMPTY
;
795 static int unruly_solver_check_all_near_complete(game_state
*state
,
796 struct unruly_scratch
*scratch
)
801 unruly_solver_check_near_complete(state
, scratch
->ones_rows
, TRUE
,
803 scratch
->zeros_cols
, N_ZERO
);
805 unruly_solver_check_near_complete(state
, scratch
->ones_cols
, FALSE
,
807 scratch
->zeros_cols
, N_ZERO
);
809 unruly_solver_check_near_complete(state
, scratch
->zeros_rows
, TRUE
,
811 scratch
->ones_cols
, N_ONE
);
813 unruly_solver_check_near_complete(state
, scratch
->zeros_cols
, FALSE
,
815 scratch
->ones_cols
, N_ONE
);
820 static int unruly_validate_rows(game_state
*state
, int horizontal
,
821 char check
, int *errors
)
823 int w2
= state
->w2
, h2
= state
->h2
;
825 int dx
= horizontal ?
1 : 0, dy
= 1 - dx
;
827 int sx
= dx
, sy
= dy
;
828 int ex
= w2
- dx
, ey
= h2
- dy
;
833 int err1
= (horizontal ? FE_HOR_ROW_LEFT
: FE_VER_ROW_TOP
);
834 int err2
= (horizontal ? FE_HOR_ROW_MID
: FE_VER_ROW_MID
);
835 int err3
= (horizontal ? FE_HOR_ROW_RIGHT
: FE_VER_ROW_BOTTOM
);
837 /* Check for any three in a row, and mark errors accordingly (if
839 for (y
= sy
; y
< ey
; y
++) {
840 for (x
= sx
; x
< ex
; x
++) {
841 int i1
= (y
-dy
) * w2
+ (x
-dx
);
843 int i3
= (y
+dy
) * w2
+ (x
+dx
);
845 if (state
->grid
[i1
] == check
&& state
->grid
[i2
] == check
846 && state
->grid
[i3
] == check
) {
860 static int unruly_validate_all_rows(game_state
*state
, int *errors
)
864 errcount
+= unruly_validate_rows(state
, TRUE
, N_ONE
, errors
);
865 errcount
+= unruly_validate_rows(state
, FALSE
, N_ONE
, errors
);
866 errcount
+= unruly_validate_rows(state
, TRUE
, N_ZERO
, errors
);
867 errcount
+= unruly_validate_rows(state
, FALSE
, N_ZERO
, errors
);
874 static int unruly_validate_counts(game_state
*state
,
875 struct unruly_scratch
*scratch
, int *errors
)
877 int w2
= state
->w2
, h2
= state
->h2
;
878 int w
= w2
/2, h
= h2
/2;
883 /* See if all rows/columns are satisfied. If one is exceeded,
884 * mark it as an error (if required)
887 char hasscratch
= TRUE
;
889 scratch
= unruly_new_scratch(state
);
893 for (i
= 0; i
< w2
; i
++) {
894 if (scratch
->ones_cols
[i
] < h
)
896 if (scratch
->zeros_cols
[i
] < h
)
899 if (scratch
->ones_cols
[i
] > h
) {
902 errors
[2*h2
+ i
] = TRUE
;
904 errors
[2*h2
+ i
] = FALSE
;
906 if (scratch
->zeros_cols
[i
] > h
) {
909 errors
[2*h2
+ w2
+ i
] = TRUE
;
911 errors
[2*h2
+ w2
+ i
] = FALSE
;
913 for (i
= 0; i
< h2
; i
++) {
914 if (scratch
->ones_rows
[i
] < w
)
916 if (scratch
->zeros_rows
[i
] < w
)
919 if (scratch
->ones_rows
[i
] > w
) {
926 if (scratch
->zeros_rows
[i
] > w
) {
929 errors
[h2
+ i
] = TRUE
;
931 errors
[h2
+ i
] = FALSE
;
935 unruly_free_scratch(scratch
);
937 return (above ?
-1 : below ?
1 : 0);
940 static int unruly_solve_game(game_state
*state
,
941 struct unruly_scratch
*scratch
, int diff
)
943 int done
, maxdiff
= -1;
948 /* Check for impending 3's */
949 done
+= unruly_solver_check_all_threes(state
, scratch
);
951 /* Keep using the simpler techniques while they produce results */
953 if (maxdiff
< DIFF_EASY
)
958 /* Check for completed rows */
959 done
+= unruly_solver_check_all_complete_nums(state
, scratch
);
962 if (maxdiff
< DIFF_EASY
)
967 /* Normal techniques */
968 if (diff
< DIFF_NORMAL
)
971 /* Check for nearly completed rows */
972 done
+= unruly_solver_check_all_near_complete(state
, scratch
);
975 if (maxdiff
< DIFF_NORMAL
)
976 maxdiff
= DIFF_NORMAL
;
985 static char *solve_game(game_state
*state
, game_state
*currstate
,
986 char *aux
, char **error
)
988 game_state
*solved
= dup_game(state
);
989 struct unruly_scratch
*scratch
= unruly_new_scratch(solved
);
993 unruly_solve_game(solved
, scratch
, DIFFCOUNT
);
995 result
= unruly_validate_counts(solved
, scratch
, NULL
);
996 if (unruly_validate_all_rows(solved
, NULL
) == -1)
1000 int w2
= solved
->w2
, h2
= solved
->h2
;
1005 ret
= snewn(s
+ 2, char);
1009 for (i
= 0; i
< s
; i
++)
1010 *p
++ = (solved
->grid
[i
] == N_ONE ?
'1' : '0');
1013 } else if (result
== 1)
1014 *error
= "No solution found.";
1015 else if (result
== -1)
1016 *error
= "Puzzle is invalid.";
1019 unruly_free_scratch(scratch
);
1027 static int unruly_fill_game(game_state
*state
, struct unruly_scratch
*scratch
,
1031 int w2
= state
->w2
, h2
= state
->h2
;
1036 #ifdef STANDALONE_SOLVER
1037 if (solver_verbose
) {
1038 printf("Generator: Attempt to fill grid\n");
1042 /* Generate random array of spaces */
1043 spaces
= snewn(s
, int);
1044 for (i
= 0; i
< s
; i
++)
1046 shuffle(spaces
, s
, sizeof(*spaces
), rs
);
1049 * Construct a valid filled grid by repeatedly picking an unfilled
1050 * space and fill it, then calling the solver to fill in any
1051 * spaces forced by the change.
1053 for (j
= 0; j
< s
; j
++) {
1056 if (state
->grid
[i
] != EMPTY
)
1059 if (random_upto(rs
, 2)) {
1060 state
->grid
[i
] = N_ONE
;
1061 scratch
->ones_rows
[i
/ w2
]++;
1062 scratch
->ones_cols
[i
% w2
]++;
1064 state
->grid
[i
] = N_ZERO
;
1065 scratch
->zeros_rows
[i
/ w2
]++;
1066 scratch
->zeros_cols
[i
% w2
]++;
1069 unruly_solve_game(state
, scratch
, DIFFCOUNT
);
1073 if (unruly_validate_all_rows(state
, NULL
) != 0
1074 || unruly_validate_counts(state
, scratch
, NULL
) != 0)
1080 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1081 char **aux
, int interactive
)
1083 #ifdef STANDALONE_SOLVER
1085 int temp_verbose
= FALSE
;
1088 int w2
= params
->w2
, h2
= params
->h2
;
1095 struct unruly_scratch
*scratch
;
1103 state
= blank_state(w2
, h2
);
1104 scratch
= unruly_new_scratch(state
);
1105 if (unruly_fill_game(state
, scratch
, rs
))
1108 unruly_free_scratch(scratch
);
1111 #ifdef STANDALONE_SOLVER
1112 if (solver_verbose
) {
1113 printf("Puzzle generated in %i attempts\n", attempts
);
1114 debug
= game_text_format(state
);
1115 fputs(debug
, stdout
);
1118 temp_verbose
= solver_verbose
;
1119 solver_verbose
= FALSE
;
1123 unruly_free_scratch(scratch
);
1125 /* Generate random array of spaces */
1126 spaces
= snewn(s
, int);
1127 for (i
= 0; i
< s
; i
++)
1129 shuffle(spaces
, s
, sizeof(*spaces
), rs
);
1132 * Winnow the clues by starting from our filled grid, repeatedly
1133 * picking a filled space and emptying it, as long as the solver
1134 * reports that the puzzle can still be solved after doing so.
1136 for (j
= 0; j
< s
; j
++) {
1143 state
->grid
[i
] = EMPTY
;
1145 solver
= dup_game(state
);
1146 scratch
= unruly_new_scratch(state
);
1148 unruly_solve_game(solver
, scratch
, params
->diff
);
1150 if (unruly_validate_counts(solver
, scratch
, NULL
) != 0)
1154 unruly_free_scratch(scratch
);
1158 #ifdef STANDALONE_SOLVER
1160 solver_verbose
= TRUE
;
1162 printf("Final puzzle:\n");
1163 debug
= game_text_format(state
);
1164 fputs(debug
, stdout
);
1170 * See if the game has accidentally come out too easy.
1172 if (params
->diff
> 0) {
1176 solver
= dup_game(state
);
1177 scratch
= unruly_new_scratch(state
);
1179 unruly_solve_game(solver
, scratch
, params
->diff
- 1);
1181 ok
= unruly_validate_counts(solver
, scratch
, NULL
);
1184 unruly_free_scratch(scratch
);
1190 * Puzzles of the easiest difficulty can't be too easy.
1196 /* Encode description */
1197 ret
= snewn(s
+ 1, char);
1200 for (i
= 0; i
< s
+1; i
++) {
1201 if (i
== s
|| state
->grid
[i
] == N_ZERO
) {
1208 } else if (state
->grid
[i
] == N_ONE
) {
1235 static game_ui
*new_ui(game_state
*state
)
1237 game_ui
*ret
= snew(game_ui
);
1239 ret
->cx
= ret
->cy
= 0;
1240 ret
->cursor
= FALSE
;
1245 static void free_ui(game_ui
*ui
)
1250 static char *encode_ui(game_ui
*ui
)
1255 static void decode_ui(game_ui
*ui
, char *encoding
)
1259 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1260 game_state
*newstate
)
1264 struct game_drawstate
{
1275 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1277 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1279 int w2
= state
->w2
, h2
= state
->h2
;
1286 ds
->started
= FALSE
;
1288 ds
->gridfs
= snewn(s
, int);
1289 ds
->rowfs
= snewn(2 * (w2
+ h2
), int);
1291 ds
->grid
= snewn(s
, int);
1292 for (i
= 0; i
< s
; i
++)
1298 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1306 #define COORD(x) ( (x) * ds->tilesize + ds->tilesize/2 )
1307 #define FROMCOORD(x) ( ((x)-(ds->tilesize/2)) / ds->tilesize )
1309 static char *interpret_move(game_state
*state
, game_ui
*ui
,
1310 const game_drawstate
*ds
, int ox
, int oy
,
1316 int gx
= FROMCOORD(ox
);
1317 int gy
= FROMCOORD(oy
);
1319 int w2
= state
->w2
, h2
= state
->h2
;
1321 button
&= ~MOD_MASK
;
1324 if (button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
||
1325 button
== MIDDLE_BUTTON
) {
1326 if (ox
>= (ds
->tilesize
/ 2) && gx
< w2
1327 && oy
>= (ds
->tilesize
/ 2) && gy
< h2
) {
1336 if (IS_CURSOR_MOVE(button
)) {
1337 move_cursor(button
, &ui
->cx
, &ui
->cy
, w2
, h2
, 0);
1343 if ((ui
->cursor
&& (button
== CURSOR_SELECT
|| button
== CURSOR_SELECT2
1344 || button
== '\b' || button
== '0' || button
== '1'
1345 || button
== '2')) ||
1346 button
== LEFT_BUTTON
|| button
== RIGHT_BUTTON
||
1347 button
== MIDDLE_BUTTON
) {
1351 if (state
->immutable
[hy
* w2
+ hx
])
1355 i
= state
->grid
[hy
* w2
+ hx
];
1357 if (button
== '0' || button
== '2')
1359 else if (button
== '1')
1361 else if (button
== MIDDLE_BUTTON
)
1364 /* Cycle through options */
1365 else if (button
== CURSOR_SELECT
|| button
== RIGHT_BUTTON
)
1366 c
= (i
== EMPTY ?
'0' : i
== N_ZERO ?
'1' : '-');
1367 else if (button
== CURSOR_SELECT2
|| button
== LEFT_BUTTON
)
1368 c
= (i
== EMPTY ?
'1' : i
== N_ONE ?
'0' : '-');
1370 if (state
->grid
[hy
* w2
+ hx
] ==
1371 (c
== '0' ? N_ZERO
: c
== '1' ? N_ONE
: EMPTY
))
1372 return NULL
; /* don't put no-ops on the undo chain */
1374 sprintf(buf
, "P%c,%d,%d", c
, hx
, hy
);
1381 static game_state
*execute_move(game_state
*state
, char *move
)
1383 int w2
= state
->w2
, h2
= state
->h2
;
1390 if (move
[0] == 'S') {
1393 ret
= dup_game(state
);
1396 for (i
= 0; i
< s
; i
++) {
1398 if (!*p
|| !(*p
== '1' || *p
== '0')) {
1403 ret
->grid
[i
] = (*p
== '1' ? N_ONE
: N_ZERO
);
1407 ret
->completed
= ret
->cheated
= TRUE
;
1409 } else if (move
[0] == 'P'
1410 && sscanf(move
+ 1, "%c,%d,%d", &c
, &x
, &y
) == 3 && x
>= 0
1411 && x
< w2
&& y
>= 0 && y
< h2
&& (c
== '-' || c
== '0'
1413 ret
= dup_game(state
);
1416 if (state
->immutable
[i
]) {
1421 ret
->grid
[i
] = (c
== '1' ? N_ONE
: c
== '0' ? N_ZERO
: EMPTY
);
1423 if (!ret
->completed
&& unruly_validate_counts(ret
, NULL
, NULL
) == 0
1424 && (unruly_validate_all_rows(ret
, NULL
) == 0))
1425 ret
->completed
= TRUE
;
1433 /* ----------------------------------------------------------------------
1437 static void game_compute_size(game_params
*params
, int tilesize
,
1440 *x
= tilesize
* (params
->w2
+ 1);
1441 *y
= tilesize
* (params
->h2
+ 1);
1444 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1445 game_params
*params
, int tilesize
)
1447 ds
->tilesize
= tilesize
;
1450 static float *game_colours(frontend
*fe
, int *ncolours
)
1452 float *ret
= snewn(3 * NCOLOURS
, float);
1455 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1457 for (i
= 0; i
< 3; i
++) {
1458 ret
[COL_1
* 3 + i
] = 0.2F
;
1459 ret
[COL_1_HIGHLIGHT
* 3 + i
] = 0.4F
;
1460 ret
[COL_1_LOWLIGHT
* 3 + i
] = 0.0F
;
1461 ret
[COL_0
* 3 + i
] = 0.95F
;
1462 ret
[COL_0_HIGHLIGHT
* 3 + i
] = 1.0F
;
1463 ret
[COL_0_LOWLIGHT
* 3 + i
] = 0.9F
;
1464 ret
[COL_EMPTY
* 3 + i
] = 0.5F
;
1465 ret
[COL_GRID
* 3 + i
] = 0.3F
;
1467 game_mkhighlight_specific(fe
, ret
, COL_0
, COL_0_HIGHLIGHT
, COL_0_LOWLIGHT
);
1468 game_mkhighlight_specific(fe
, ret
, COL_1
, COL_1_HIGHLIGHT
, COL_1_LOWLIGHT
);
1470 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
1471 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
1472 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
1474 ret
[COL_CURSOR
* 3 + 0] = 0.0F
;
1475 ret
[COL_CURSOR
* 3 + 1] = 0.7F
;
1476 ret
[COL_CURSOR
* 3 + 2] = 0.0F
;
1478 *ncolours
= NCOLOURS
;
1482 static void unruly_draw_err_rectangle(drawing
*dr
, int x
, int y
, int w
, int h
,
1485 double thick
= tilesize
/ 10;
1486 double margin
= tilesize
/ 20;
1488 draw_rect(dr
, x
+margin
, y
+margin
, w
-2*margin
, thick
, COL_ERROR
);
1489 draw_rect(dr
, x
+margin
, y
+margin
, thick
, h
-2*margin
, COL_ERROR
);
1490 draw_rect(dr
, x
+margin
, y
+h
-margin
-thick
, w
-2*margin
, thick
, COL_ERROR
);
1491 draw_rect(dr
, x
+w
-margin
-thick
, y
+margin
, thick
, h
-2*margin
, COL_ERROR
);
1494 static void unruly_draw_tile(drawing
*dr
, int x
, int y
, int tilesize
, int tile
)
1496 clip(dr
, x
, y
, tilesize
, tilesize
);
1498 /* Draw the grid edge first, so the tile can overwrite it */
1499 draw_rect(dr
, x
, y
, tilesize
, tilesize
, COL_GRID
);
1501 /* Background of the tile */
1503 int val
= (tile
& FF_ZERO ?
0 : tile
& FF_ONE ?
2 : 1);
1504 val
= (val
== 0 ? COL_0
: val
== 2 ? COL_1
: COL_EMPTY
);
1506 if ((tile
& (FF_FLASH1
| FF_FLASH2
)) &&
1507 (val
== COL_0
|| val
== COL_1
)) {
1508 val
+= (tile
& FF_FLASH1 ?
1 : 2);
1511 draw_rect(dr
, x
, y
, tilesize
-1, tilesize
-1, val
);
1513 if ((val
== COL_0
|| val
== COL_1
) && (tile
& FF_IMMUTABLE
)) {
1514 draw_rect(dr
, x
+ tilesize
/6, y
+ tilesize
/6,
1515 tilesize
- 2*(tilesize
/6) - 2, 1, val
+ 2);
1516 draw_rect(dr
, x
+ tilesize
/6, y
+ tilesize
/6,
1517 1, tilesize
- 2*(tilesize
/6) - 2, val
+ 2);
1518 draw_rect(dr
, x
+ tilesize
/6 + 1, y
+ tilesize
- tilesize
/6 - 2,
1519 tilesize
- 2*(tilesize
/6) - 2, 1, val
+ 1);
1520 draw_rect(dr
, x
+ tilesize
- tilesize
/6 - 2, y
+ tilesize
/6 + 1,
1521 1, tilesize
- 2*(tilesize
/6) - 2, val
+ 1);
1525 /* 3-in-a-row errors */
1526 if (tile
& (FE_HOR_ROW_LEFT
| FE_HOR_ROW_RIGHT
)) {
1527 int left
= x
, right
= x
+ tilesize
- 1;
1528 if ((tile
& FE_HOR_ROW_LEFT
))
1529 right
+= tilesize
/2;
1530 if ((tile
& FE_HOR_ROW_RIGHT
))
1532 unruly_draw_err_rectangle(dr
, left
, y
, right
-left
, tilesize
-1, tilesize
);
1534 if (tile
& (FE_VER_ROW_TOP
| FE_VER_ROW_BOTTOM
)) {
1535 int top
= y
, bottom
= y
+ tilesize
- 1;
1536 if ((tile
& FE_VER_ROW_TOP
))
1537 bottom
+= tilesize
/2;
1538 if ((tile
& FE_VER_ROW_BOTTOM
))
1540 unruly_draw_err_rectangle(dr
, x
, top
, tilesize
-1, bottom
-top
, tilesize
);
1544 if (tile
& FE_COUNT
) {
1545 draw_text(dr
, x
+ tilesize
/2, y
+ tilesize
/2, FONT_VARIABLE
,
1546 tilesize
/2, ALIGN_HCENTRE
| ALIGN_VCENTRE
, COL_ERROR
, "!");
1549 /* Cursor rectangle */
1550 if (tile
& FF_CURSOR
) {
1551 draw_rect(dr
, x
, y
, tilesize
/12, tilesize
-1, COL_CURSOR
);
1552 draw_rect(dr
, x
, y
, tilesize
-1, tilesize
/12, COL_CURSOR
);
1553 draw_rect(dr
, x
+tilesize
-1-tilesize
/12, y
, tilesize
/12, tilesize
-1,
1555 draw_rect(dr
, x
, y
+tilesize
-1-tilesize
/12, tilesize
-1, tilesize
/12,
1560 draw_update(dr
, x
, y
, tilesize
, tilesize
);
1563 #define TILE_SIZE (ds->tilesize)
1564 #define DEFAULT_TILE_SIZE 32
1565 #define FLASH_FRAME 0.12F
1566 #define FLASH_TIME (FLASH_FRAME * 3)
1568 static void game_redraw(drawing
*dr
, game_drawstate
*ds
,
1569 game_state
*oldstate
, game_state
*state
, int dir
,
1570 game_ui
*ui
, float animtime
, float flashtime
)
1572 int w2
= state
->w2
, h2
= state
->h2
;
1578 /* Main window background */
1579 draw_rect(dr
, 0, 0, TILE_SIZE
* (w2
+1), TILE_SIZE
* (h2
+1),
1581 /* Outer edge of grid */
1582 draw_rect(dr
, COORD(0)-TILE_SIZE
/10, COORD(0)-TILE_SIZE
/10,
1583 TILE_SIZE
*w2
+ 2*(TILE_SIZE
/10) - 1,
1584 TILE_SIZE
*h2
+ 2*(TILE_SIZE
/10) - 1, COL_GRID
);
1586 draw_update(dr
, 0, 0, TILE_SIZE
* (w2
+1), TILE_SIZE
* (h2
+1));
1592 flash
= (int)(flashtime
/ FLASH_FRAME
) == 1 ? FF_FLASH2
: FF_FLASH1
;
1594 for (i
= 0; i
< s
; i
++)
1596 unruly_validate_all_rows(state
, ds
->gridfs
);
1597 for (i
= 0; i
< 2 * (h2
+ w2
); i
++)
1599 unruly_validate_counts(state
, NULL
, ds
->rowfs
);
1601 for (y
= 0; y
< h2
; y
++) {
1602 for (x
= 0; x
< w2
; x
++) {
1607 tile
= ds
->gridfs
[i
];
1609 if (state
->grid
[i
] == N_ONE
) {
1611 if (ds
->rowfs
[y
] || ds
->rowfs
[2*h2
+ x
])
1613 } else if (state
->grid
[i
] == N_ZERO
) {
1615 if (ds
->rowfs
[h2
+ y
] || ds
->rowfs
[2*h2
+ w2
+ x
])
1621 if (state
->immutable
[i
])
1622 tile
|= FF_IMMUTABLE
;
1624 if (ui
->cursor
&& ui
->cx
== x
&& ui
->cy
== y
)
1627 if (ds
->grid
[i
] != tile
) {
1629 unruly_draw_tile(dr
, COORD(x
), COORD(y
), TILE_SIZE
, tile
);
1635 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1636 int dir
, game_ui
*ui
)
1641 static float game_flash_length(game_state
*oldstate
,
1642 game_state
*newstate
, int dir
,
1645 if (!oldstate
->completed
&& newstate
->completed
&&
1646 !oldstate
->cheated
&& !newstate
->cheated
)
1651 static int game_status(game_state
*state
)
1653 return state
->completed ?
+1 : 0;
1656 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1661 static void game_print_size(game_params
*params
, float *x
, float *y
)
1665 /* Using 7mm squares */
1666 game_compute_size(params
, 700, &pw
, &ph
);
1671 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
1673 int w2
= state
->w2
, h2
= state
->h2
;
1676 int ink
= print_mono_colour(dr
, 0);
1680 for (y
= 0; y
< h2
; y
++)
1681 for (x
= 0; x
< w2
; x
++) {
1682 int tx
= x
* tilesize
+ (tilesize
/ 2);
1683 int ty
= y
* tilesize
+ (tilesize
/ 2);
1685 /* Draw the border */
1689 coords
[2] = tx
+ tilesize
;
1691 coords
[4] = tx
+ tilesize
;
1692 coords
[5] = ty
+ tilesize
- 1;
1694 coords
[7] = ty
+ tilesize
- 1;
1695 draw_polygon(dr
, coords
, 4, -1, ink
);
1697 if (state
->grid
[y
* w2
+ x
] == N_ONE
)
1698 draw_rect(dr
, tx
, ty
, tilesize
, tilesize
, ink
);
1699 else if (state
->grid
[y
* w2
+ x
] == N_ZERO
)
1700 draw_circle(dr
, tx
+ tilesize
/2, ty
+ tilesize
/2,
1701 tilesize
/12, ink
, ink
);
1706 #define thegame unruly
1709 const struct game thegame
= {
1710 "Unruly", "games.unruly", "unruly",
1717 TRUE
, game_configure
, custom_params
,
1725 TRUE
, game_can_format_as_text_now
, game_text_format
,
1733 DEFAULT_TILE_SIZE
, game_compute_size
, game_set_size
,
1736 game_free_drawstate
,
1741 TRUE
, FALSE
, game_print_size
, game_print
,
1742 FALSE
, /* wants_statusbar */
1743 FALSE
, game_timing_state
,
1747 /* ***************** *
1748 * Standalone solver *
1749 * ***************** */
1751 #ifdef STANDALONE_SOLVER
1755 /* Most of the standalone solver code was copied from unequal.c and singles.c */
1759 static void usage_exit(const char *msg
)
1762 fprintf(stderr
, "%s: %s\n", quis
, msg
);
1764 "Usage: %s [-v] [--seed SEED] <params> | [game_id [game_id ...]]\n",
1769 int main(int argc
, char *argv
[])
1772 time_t seed
= time(NULL
);
1774 game_params
*params
= NULL
;
1776 char *id
= NULL
, *desc
= NULL
, *err
;
1780 while (--argc
> 0) {
1782 if (!strcmp(p
, "--seed")) {
1784 usage_exit("--seed needs an argument");
1785 seed
= (time_t) atoi(*++argv
);
1787 } else if (!strcmp(p
, "-v"))
1788 solver_verbose
= TRUE
;
1790 usage_exit("unrecognised option");
1796 desc
= strchr(id
, ':');
1800 params
= default_params();
1801 decode_params(params
, id
);
1802 err
= validate_params(params
, TRUE
);
1804 fprintf(stderr
, "Parameters are invalid\n");
1805 fprintf(stderr
, "%s: %s", argv
[0], err
);
1811 char *desc_gen
, *aux
;
1812 rs
= random_new((void *) &seed
, sizeof(time_t));
1814 params
= default_params();
1815 printf("Generating puzzle with parameters %s\n",
1816 encode_params(params
, TRUE
));
1817 desc_gen
= new_game_desc(params
, rs
, &aux
, FALSE
);
1819 if (!solver_verbose
) {
1820 char *fmt
= game_text_format(new_game(NULL
, params
, desc_gen
));
1825 printf("Game ID: %s\n", desc_gen
);
1828 struct unruly_scratch
*scratch
;
1829 int maxdiff
, errcode
;
1831 err
= validate_desc(params
, desc
);
1833 fprintf(stderr
, "Description is invalid\n");
1834 fprintf(stderr
, "%s", err
);
1838 input
= new_game(NULL
, params
, desc
);
1839 scratch
= unruly_new_scratch(input
);
1841 maxdiff
= unruly_solve_game(input
, scratch
, DIFFCOUNT
);
1843 errcode
= unruly_validate_counts(input
, scratch
, NULL
);
1844 if (unruly_validate_all_rows(input
, NULL
) == -1)
1847 if (errcode
!= -1) {
1848 char *fmt
= game_text_format(input
);
1852 printf("Difficulty: already solved!\n");
1854 printf("Difficulty: %s\n", unruly_diffnames
[maxdiff
]);
1858 printf("No solution found.\n");
1859 else if (errcode
== -1)
1860 printf("Puzzle is invalid.\n");
1863 unruly_free_scratch(scratch
);