blib/lib/Regexp/Sudoku.pm untested

filter: Statementstmt 0.0% 0 / 428 Branchbran 0.0% 0 / 88 Conditioncond 0.0% 0 / 88 MC/DCmcdc n/a Subroutinesub 0.0% 0 / 72 Podpod 0.0% 0 / 61 totaltotal 0.0% 0 / 737 CC 45 SCAR 30.7
CC
45
Cov
0%
init_diagonal
132.0
cells
42.0
init_subject_and_pattern
42.0
CRAP 21.6
1 package Regexp::Sudoku;
2  
3 use 5.028;
4 use strict;
5 use warnings;
6 no warnings 'syntax';
7  
8 use experimental 'signatures';
9 use experimental 'lexical_subs';
10  
11 our $VERSION = '2022030401';
12  
13 use Hash::Util::FieldHash qw [fieldhash];
14 use List::Util qw [min max];
15 use Math::Sequence::DeBruijn;
16  
17 use Exporter ();
18  
19 my $DEFAULT_SIZE = 9;
20 my $SENTINEL = "\n";
21 my $CLAUSE_LIST = ",";
22  
23 my $NR_OF_DIGITS = 9;
24 my $NR_OF_LETTERS = 26;
25 my $NR_OF_SYMBOLS = $NR_OF_DIGITS + $NR_OF_LETTERS;
26  
27 my $ANTI_KNIGHT = 1;
28 my $ANTI_KING = 2;
29  
30 my $MAIN_DIAGONAL = 1;
31 my $MINOR_DIAGONAL = 2;
32  
33 fieldhash my %size;
34 fieldhash my %values;
35 fieldhash my %evens;
36 fieldhash my %odds;
37 fieldhash my %box_width;
38 fieldhash my %box_height;
39 fieldhash my %values_range;
40 fieldhash my %cell2houses;
41 fieldhash my %house2cells;
42 fieldhash my %clues;
43 fieldhash my %is_even;
44 fieldhash my %is_odd;
45 fieldhash my %subject;
46 fieldhash my %pattern;
47 fieldhash my %constraints;
48 fieldhash my %renban2cells;
49 fieldhash my %cell2renbans;
50  
51  
52 my sub has_bit ($vec) {$vec =~ /[^\x{00}]/}
53  
54  
55 ################################################################################
56 #
57 # new ($class)
58 #
59 # Create an uninitialized object.
60 #
61 ################################################################################
62  
63 sub new ($class) {bless \do {my $v} => $class}
64  
65  
66 ################################################################################
67 #
68 # sub cell_name ($row, $column)
69 #
70 # Given a row number and a cell number, return the name of the cell.
71 #
72 # TESTS: 090-cell_name_row_column.t
73 #
74 ################################################################################
75  
76 sub cell_name ($row, $column) {
77 "R" . $row . "C" . $column
78 }
79  
80  
81 ################################################################################
82 #
83 # sub cell_row_column ($cell_name)
84 #
85 # Given the name of a cell, return its row and column.
86 #
87 # TESTS: 090-cell_name_row_column.t
88 #
89 ################################################################################
90  
91 sub cell_row_column ($name) {
92 $name =~ /R([0-9]+)C([0-9]+)/ ? ($1, $2) : (0, 0)
93 }
94  
95  
96 ################################################################################
97 #
98 # init_sizes ($self, $size)
99 #
100 # Initialize the sizes of the soduko.
101 #
102 # Calls init_size () and init_box () doing the work.
103 #
104 # TESTS: 010_size.t
105 #
106 ################################################################################
107  
108 sub init_sizes ($self, $args) {
109 $self -> init_size ($args)
110 -> init_box ($args);
111 }
112  
113  
114 ################################################################################
115 #
116 # init_size ($self, $size)
117 #
118 # Initialize the size of a sudoku. If the size is not given, use the default.
119 #
120 # TESTS: 010_size.t
121 #
122 ################################################################################
123  
124 sub init_size ($self, $args = {}) {
125 $size {$self} = delete $$args {size} || $DEFAULT_SIZE;
126 die "Size should not exceed $NR_OF_SYMBOLS\n"
127 if $size {$self} > $NR_OF_SYMBOLS;
128 $self;
129 }
130  
131  
132 ################################################################################
133 #
134 # size ($self)
135 #
136 # Returns the size of the sudoku. If there is no size supplied, use
137 # the default (9).
138 #
139 # TESTS: 010_size.t
140 #
141 ################################################################################
142  
143 sub size ($self) {
144 $size {$self}
145 }
146  
147  
148 ################################################################################
149 #
150 # init_values ($self, $args)
151 #
152 # Initializes the values. We calculate them from the range (1-9, A-Z),
153 # as many as needed.
154 #
155 # TESTS: 020_values.t
156 #
157 ################################################################################
158  
159 sub init_values ($self, $args = {}) {
160 my $size = $self -> size;
161 my $values = join "" => 1 .. min $size, $NR_OF_DIGITS;
162 if ($size > $NR_OF_DIGITS) {
163 $values .= join "" =>
164 map {chr (ord ('A') + $_ - $NR_OF_DIGITS - 1)}
165 ($NR_OF_DIGITS + 1) .. min $size, $NR_OF_SYMBOLS;
166 }
167  
168 my $evens = do {my $i = 1; join "" => grep {$i = !$i} split // => $values};
169 my $odds = do {my $i = 0; join "" => grep {$i = !$i} split // => $values};
170  
171 $values {$self} = $values;
172 $evens {$self} = $evens;
173 $odds {$self} = $odds;
174  
175 $self -> init_values_range ($args);
176 }
177  
178  
179 ################################################################################
180 #
181 # init_value_ranges ($self, $args)
182 #
183 # Processes the values to turn them into ranges for use in a character class
184 #
185 # TESTS: 020_values.t
186 #
187 ################################################################################
188  
189 sub init_values_range ($self, $args = {}) {
190 my @values = sort {$a cmp $b} $self -> values;
191 my $size = $self -> size;
192 my $range = "1-";
193  
194 if ($size < 10) {$range .= $values [-1];}
195 elsif ($size == 10) {$range .= "9A"; }
196 else {$range .= "9A-" . $values [-1];}
197  
198 $values_range {$self} = $range;
199  
200 $self;
201 }
202  
203  
204 ################################################################################
205 #
206 # values ($self)
207 #
208 # Return the set of values used in the sudoku. In list context, this will
209 # be an array of characters; in scalar context, a string.
210 #
211 # TESTS: 020_values.t
212 #
213 ################################################################################
214  
215 sub values ($self) {
216 wantarray ? split // => $values {$self} : $values {$self};
217 }
218  
219  
220 ################################################################################
221 #
222 # evens ($self)
223 #
224 # Return the set of even values used in the sudoku. In list context, this will
225 # be an array of characters; in scalar context, a string.
226 #
227 # TESTS: 020_values.t
228 #
229 ################################################################################
230  
231 sub evens ($self) {
232 wantarray ? split // => $evens {$self} : $evens {$self};
233 }
234  
235  
236 ################################################################################
237 #
238 # odds ($self)
239 #
240 # Return the set of odd values used in the sudoku. In list context, this will
241 # be an array of characters; in scalar context, a string.
242 #
243 # TESTS: 020_values.t
244 #
245 ################################################################################
246  
247 sub odds ($self) {
248 wantarray ? split // => $odds {$self} : $odds {$self};
249 }
250  
251  
252 ################################################################################
253 #
254 # values_range ($self)
255 #
256 # Return the set of values used in the sudoku, as ranges to be used in
257 # a character class. Calls $self -> values () to get the values.
258 #
259 # TESTS: 020_values.t
260 #
261 ################################################################################
262  
263 sub values_range ($self) {
264 $values_range {$self}
265 }
266  
267  
268 ################################################################################
269 #
270 # init_box ($self, $args)
271 #
272 # Find the width and height of a box. If the size of the sudoku is a square,
273 # the width and height of a box are equal, and the square root of the size
274 # of the sudoku. Else, we'll find the most squarish width and height (with
275 # the width larger than the height). The width and height are stored as
276 # attributes. If they are already set, the function immediately returns.
277 #
278 # TESTS: 030-box.t
279 #
280 ################################################################################
281  
282 sub init_box ($self, $args = {}) {
283 return if $box_height {$self} && $box_width {$self};
284 my $size = $self -> size;
285 my $box_height = int sqrt $size;
286 $box_height -- while $size % $box_height;
287 my $box_width = $size / $box_height;
288  
289 $box_height {$self} = $box_height;
290 $box_width {$self} = $box_width;
291  
292 $self;
293 }
294  
295  
296 ################################################################################
297 #
298 # box_height ($self)
299 # box_width ($self)
300 #
301 # Return the height and width of a box in the sudoku. These methods will
302 # call $self -> box_init first, to calculate the values if necessary.
303 #
304 # TESTS: 030_values.t
305 #
306 ################################################################################
307  
308 sub box_height ($self) {
309 $box_height {$self};
310 }
311  
312 sub box_width ($self) {
313 $box_width {$self};
314 }
315  
316  
317 ################################################################################
318 #
319 # create_house ($self, $house_name, @cells)
320 #
321 # Create a house with the given name, containing the passed in cells.
322 #
323 # TESTS: 040-create_house.t
324 #
325 ################################################################################
326  
327 sub create_house ($self, $name, @cells) {
328 for my $cell (@cells) {
329 $cell2houses {$self} {$cell} {$name} = 1;
330 $house2cells {$self} {$name} {$cell} = 1;
331 }
332 $self;
333 }
334  
335  
336 ################################################################################
337 #
338 # init_rows ($self, $args)
339 #
340 # Initialize the rows in the sudoku. Calculates which cells belong to which
341 # rows, and calls create_house for each row. Called from init_houses.
342 # Rows are named "R1" .. "Rn", where n is the size of the sudoku.
343 #
344 # TESTS: 041-init_rows
345 #
346 ################################################################################
347  
348 sub init_rows ($self, $args = {}) {
349 my $size = $self -> size;
350 for my $r (1 .. $size) {
351 my $row_name = "R$r";
352 my @cells = map {cell_name $r, $_} 1 .. $size;
353 $self -> create_house ($row_name, @cells);
354 }
355 $self;
356 }
357  
358  
359 ################################################################################
360 #
361 # init_columns ($self, $args)
362 #
363 # Initialize the columns in the sudoku. Calculates which cells belong to which
364 # columns, and calls create_house for each column. Called from init_houses.
365 # Columns are named "C1" .. "Cn", where n is the size of the sudoku.
366 #
367 # TESTS: 042-init_columns
368 #
369 ################################################################################
370  
371 sub init_columns ($self, $args = {}) {
372 my $size = $self -> size;
373 for my $c (1 .. $size) {
374 my $col_name = "C$c";
375 my @cells = map {cell_name $_, $c} 1 .. $size;
376 $self -> create_house ($col_name, @cells);
377 }
378 $self;
379 }
380  
381  
382 ################################################################################
383 #
384 # init_boxes ($self, $args)
385 #
386 # Initialize the boxes in the sudoku. Calculates which cells belong to which
387 # boxes, and calls create_house for each box. Called from init_houses.
388 # Boxes are named "B1-1" .. "Bh-w" where we have h rows of w boxes.
389 #
390 # TESTS: 043-init_boxes
391 #
392 ################################################################################
393  
394 sub init_boxes ($self, $args = {}) {
395 my $size = $self -> size;
396 my $box_width = $self -> box_width;
397 my $box_height = $self -> box_height;
398  
399 my $bc = $size / $box_width;
400 my $br = $size / $box_height;
401 for my $r (1 .. $br) {
402 for my $c (1 .. $bc) {
403 my $box_name = "B${r}-${c}";
404 my $tlr = 1 + ($r - 1) * $box_height;
405 my $tlc = 1 + ($c - 1) * $box_width;
406 my @cells;
407 for my $dr (1 .. $box_height) {
408 for my $dc (1 .. $box_width) {
409 my $cell = cell_name $tlr + $dr - 1, $tlc + $dc - 1;
410 push @cells => $cell;
411 }
412 }
413 $self -> create_house ($box_name, @cells);
414 }
415 }
416 $self;
417 }
418  
419  
420 ################################################################################
421 #
422 # init_houses ($self, $args)
423 # init_rows ($self)
424 # init_columns ($self)
425 # init_boxes ($self)
426 #
427 # Calculate which cells go into which houses.
428 #
429 # Calls init_rows (), init_columns (), and init_boxes () to initialize
430 # the rows, columns and boxes.
431 #
432 # TESTS: 045-init_houses.t
433 #
434 ################################################################################
435  
436 sub init_houses ($self, $args = {}) {
437 $self -> init_rows ($args)
438 -> init_columns ($args)
439 -> init_boxes ($args)
440 }
441  
442  
443 ################################################################################
444 #
445 # set_nrc_houses ($self, $args)
446 #
447 # For NRC style puzzles, handle creating the houses.
448 #
449 # There are four NRC houses (9 x 9 Sudokus only):
450 #
451 # . . . . . . . . .
452 # . * * * . * * * .
453 # . * * * . * * * .
454 #
455 # . * * * . * * * .
456 # . . . . . . . . .
457 # . * * * . * * * .
458 #
459 # . * * * . * * * .
460 # . * * * . * * * .
461 # . . . . . . . . .
462 #
463 #
464 # TESTS: 046-set_nrc_houses.t
465 #
466 ################################################################################
467  
468 sub set_nrc_houses ($self, $args = {}) {
469 return $self unless $self -> size == $DEFAULT_SIZE;
470  
471 my @top_left = ([2, 2], [2, 6], [6, 2], [6, 6]);
472 foreach my $i (keys @top_left) {
473 my $top_left = $top_left [$i];
474 my $house = "NRC" . ($i + 1);
475 my @cells;
476 foreach my $dr (0 .. 2) {
477 foreach my $dc (0 .. 2) {
478 my $cell = cell_name $$top_left [0] + $dr,
479 $$top_left [1] + $dc;
480 push @cells => $cell;
481 }
482 }
483 $self -> create_house ($house, @cells);
484 }
485  
486 $self;
487 }
488  
489  
490 ################################################################################
491 #
492 # sub set_asterisk_house ($self, $args)
493 #
494 # An asterisk sudoku has an additional house: one cell from each box.
495 # This method initializes that house.
496 #
497 # An asterisk is defined for a 9 x 9 sudoku as follows:
498 #
499 # . . . . . . . . .
500 # . . . . * . . . .
501 # . . * . . . * . .
502 #
503 # . . . . . . . . .
504 # . * . . * . . * .
505 # . . . . . . . . .
506 #
507 # . . * . . . * . .
508 # . . . . * . . . .
509 # . . . . . . . . .
510 #
511 # TESTS: 047-set_asterisk_house.t
512 #
513 ################################################################################
514  
515 sub set_asterisk_house ($self, $args = {}) {
516 return $self unless $self -> size == $DEFAULT_SIZE;
517  
518 $self -> create_house ("AS" => map {cell_name @$_}
519 [3, 3], [2, 5], [3, 7],
520 [5, 2], [5, 5], [5, 8],
521 [7, 3], [8, 5], [7, 7]);
522 }
523  
524  
525 ################################################################################
526 #
527 # sub set_girandola_house ($self, $args)
528 #
529 # An girandola sudoku has an additional house: one cell from each box.
530 # This method initializes that house.
531 #
532 # An girandola is defined for a 9 x 9 sudoku as follows:
533 #
534 # * . . . . . . . *
535 # . . . . * . . . .
536 # . . . . . . . . .
537 #
538 # . . . . . . . . .
539 # . * . . * . . * .
540 # . . . . . . . . .
541 #
542 # . . . . . . . . .
543 # . . . . * . . . .
544 # * . . . . . . . *
545 #
546 # TESTS: 048-set_girandola_house.t
547 #
548 ################################################################################
549  
550 sub set_girandola_house ($self) {
551 return $self unless $self -> size == $DEFAULT_SIZE;
552  
553 $self -> create_house ("GR" => map {cell_name @$_}
554 [1, 1], [2, 5], [1, 9],
555 [5, 2], [5, 5], [5, 8],
556 [9, 1], [8, 5], [9, 9]);
557 }
558  
559 ################################################################################
560 #
561 # sub set_center_dot_house ($self, $args)
562 #
563 # An center dot sudoku has an additional house: one cell from each box.
564 # This method initializes that house.
565 #
566 # A center dot is defined for a 9 x 9 sudoku as follows:
567 #
568 # . . . . . . . . .
569 # . * . . * . . * .
570 # . . . . . . . . .
571 #
572 # . . . . . . . . .
573 # . * . . * . . * .
574 # . . . . . . . . .
575 #
576 # . . . . . . . . .
577 # . * . . * . . * .
578 # . . . . . . . . .
579 #
580 # TESTS: 049-set_center_dot_house.t
581 #
582 ################################################################################
583  
584 sub set_center_dot_house ($self) {
585 my $width = $self -> box_width;
586 my $height = $self -> box_height;
587 my $size = $self -> size;
588  
589 #
590 # We can only do center dots if boxes are odd sized width and heigth.
591 #
592 return $self unless $width % 2 && $height % 2;
593  
594 my $width_start = ($width + 1) / 2;
595 my $height_start = ($height + 1) / 2;
596  
597 my @center_cells;
598 for (my $x = $width_start; $x <= $size; $x += $width) {
599 for (my $y = $height_start; $y <= $size; $y += $height) {
600 push @center_cells => [$x, $y];
601 }
602 }
603  
604 $self -> create_house ("CD" => map {cell_name @$_} @center_cells);
605 }
606  
607  
608 ################################################################################
609 #
610 # sub init_diagonal ($self, $args)
611 #
612 # If we have diagonals, it means cells on one or more diagonals
613 # should differ. This method initializes the houses for that.
614 #
615 # The main diagonal for a 9 x 9 sudoku is defined as follows:
616 #
617 # * . . . . . . . .
618 # . * . . . . . . .
619 # . . * . . . . . .
620 #
621 # . . . * . . . . .
622 # . . . . * . . . .
623 # . . . . . * . . .
624 #
625 # . . . . . . * . .
626 # . . . . . . . * .
627 # . . . . . . . . *
628 #
629 # The minor diagonal for a 9 x 9 sudoku is defined as follows:
630 #
631 # . . . . . . . . *
632 # . . . . . . . * .
633 # . . . . . . * . .
634 #
635 # . . . . . * . . .
636 # . . . . * . . . .
637 # . . . * . . . . .
638 #
639 # . . * . . . . . .
640 # . * . . . . . . .
641 # * . . . . . . . .
642 #
643 # TESTS: 050-set_diagonals.t
644 # 051-set_diagonals.t
645 # 052-set_diagonals.t
646 #
647 ################################################################################
648  
649 my sub init_diagonal ($self, $type, $offset = 0) {
650 my $size = $self -> size;
651  
652 return $self if $offset >= $size;
653  
654 my @cells;
655 for (my ($r, $c) = $type == $MAIN_DIAGONAL
656 ? ($offset >= 0 ? (1, 1 + $offset)
657 : (1 - $offset, 1))
658 : ($offset >= 0 ? ($size, 1 + $offset)
659 : ($size + $offset, 1));
660 0 < $r && $r <= $size && 0 < $c && $c <= $size;
661 ($r, $c) = $type == $MAIN_DIAGONAL ? ($r + 1, $c + 1)
662 : ($r - 1, $c + 1)) {
663 push @cells => cell_name ($r, $c);
664 }
665  
666 my $name;
667 if ($type == $MAIN_DIAGONAL) {
668 $name = "DM";
669 if ($offset) {
670 $name .= $offset > 0 ? "S" : "s";
671 $name .= "-" . abs ($offset);
672 }
673 }
674 else {
675 $name = "Dm";
676 if ($offset) {
677 $name .= $offset < 0 ? "S" : "s";
678 $name .= "-" . abs ($offset);
679 }
680 }
681  
682 $self -> create_house ($name => @cells);
683 }
684  
685 sub set_diagonal_main ($self) {
686 init_diagonal ($self, $MAIN_DIAGONAL);
687 }
688 sub set_diagonal_minor ($self) {
689 init_diagonal ($self, $MINOR_DIAGONAL);
690 }
691 sub set_cross ($self) {
692 $self -> set_diagonal_main
693 -> set_diagonal_minor
694 }
695 sub set_diagonal_double ($self) {
696 $self -> set_cross_1
697 }
698 sub set_diagonal_triple ($self) {
699 $self -> set_cross_1
700 -> set_cross
701 }
702 sub set_argyle ($self) {
703 $self -> set_cross_1
704 -> set_cross_4
705 }
706  
707  
708 foreach my $offset (1 .. $NR_OF_SYMBOLS - 1) {
709 no strict 'refs';
710  
711 *{"set_diagonal_main_super_$offset"} = sub ($self) {
712 init_diagonal ($self, $MAIN_DIAGONAL, $offset);
713 };
714  
715 *{"set_diagonal_main_sub_$offset"} = sub ($self) {
716 init_diagonal ($self, $MAIN_DIAGONAL, - $offset);
717 };
718  
719 *{"set_diagonal_minor_super_$offset"} = sub ($self) {
720 init_diagonal ($self, $MINOR_DIAGONAL, - $offset);
721 };
722  
723 *{"set_diagonal_minor_sub_$offset"} = sub ($self) {
724 init_diagonal ($self, $MINOR_DIAGONAL, $offset);
725 };
726  
727 *{"set_cross_$offset"} = sub ($self) {
728 init_diagonal ($self, $MAIN_DIAGONAL, $offset);
729 init_diagonal ($self, $MAIN_DIAGONAL, - $offset);
730 init_diagonal ($self, $MINOR_DIAGONAL, - $offset);
731 init_diagonal ($self, $MINOR_DIAGONAL, $offset);
732 };
733 }
734  
735  
736 ################################################################################
737 #
738 # cell2houses ($self, $cell)
739 #
740 # Give the name of a cell, return the names of all the houses this cell
741 # is part off.
742 #
743 # TESTS: 040-houses.t
744 #
745 ################################################################################
746  
747 sub cell2houses ($self, $cell) {
748 keys %{$cell2houses {$self} {$cell} || {}}
749 }
750  
751  
752 ################################################################################
753 #
754 # house2cells ($self, $house)
755 #
756 # Give the name of a house, return the names of all the cells in this house.
757 #
758 # TESTS: 040-houses.t
759 #
760 ################################################################################
761  
762 sub house2cells ($self, $house) {
763 keys %{$house2cells {$self} {$house} || {}}
764 }
765  
766  
767 ################################################################################
768 #
769 # cells ($self)
770 #
771 # Return the names of all the cells in the sudoku.
772 #
773 # TESTS: 040-houses.t
774 #
775 ################################################################################
776  
777 sub cells ($self, $sorted = 0) {
778 my @cells = sort keys %{$cell2houses {$self}};
779 if ($sorted) {
780 state $CELL_NAME = 0;
781 state $IS_CLUE = $CELL_NAME + 1;
782 state $EVEN_ODD = $IS_CLUE + 1;
783 state $CLUES_SEEN = $EVEN_ODD + 1;
784 state $NR_OF_HOUSES = $CLUES_SEEN + 1;
785  
786 #
787 # For each cell, determine how many different clues it sees.
788 #
789 my %sees;
790 foreach my $cell1 (@cells) {
791 next if $self -> clue ($cell1); # Don't care about clues
792 foreach my $cell2 (@cells) {
793 if ($self -> clue ($cell2) &&
794 $self -> must_differ ($cell1, $cell2)) {
795 $sees {$cell1} {$self -> clue ($cell2)} = 1;
796 }
797 }
798 }
799  
800 @cells = map {$$_ [$CELL_NAME]}
801 sort {$$b [$IS_CLUE] <=> $$a [$IS_CLUE] ||
802 $$b [$EVEN_ODD] <=> $$a [$EVEN_ODD] ||
803 $$b [$CLUES_SEEN] <=> $$a [$CLUES_SEEN] ||
804 $$b [$NR_OF_HOUSES] <=> $$a [$NR_OF_HOUSES] ||
805 $$a [$CELL_NAME] cmp $$b [$CELL_NAME]}
806 map {my $r = [];
807 $$r [$CELL_NAME] = $_;
808 $$r [$IS_CLUE] = $self -> clue ($_) ? 1 : 0;
809 $$r [$EVEN_ODD] = $self -> is_even ($_) ||
810 $self -> is_odd ($_) ? 1 : 0;
811 $$r [$CLUES_SEEN] = keys (%{$sees {$_} || {}});
812 $$r [$NR_OF_HOUSES] = $self -> cell2houses ($_);
813 $r}
814 @cells;
815 }
816 @cells;
817 }
818  
819  
820 ################################################################################
821 #
822 # houses ($self)
823 #
824 # Return the names of all the houses in the sudoku.
825 #
826 # TESTS: 040-houses.t
827 #
828 ################################################################################
829  
830 sub houses ($self) {
831 keys %{$house2cells {$self}}
832 }
833  
834  
835 ################################################################################
836 #
837 # set_clues ($self, $args)
838 #
839 # Take the supplied clues (if any!), and return a structure which maps cell
840 # names to clue values.
841 #
842 # The clues could be one of:
843 # - A 2-d array, with false values indicating the cell doesn't have a clue.
844 # A "." will also be consider to be not a clue.
845 # - A string, newlines separating rows, and whitespace clues. A value
846 # of 0 or "." indicates no clue.
847 #
848 # We wil populate the clues attribute, mapping cell names to clue values.
849 # Cells without clues won't be set.
850 #
851 # TESTS: 080-set_clues.t
852 #
853 ################################################################################
854  
855 sub set_clues ($self, $in_clues) {
856 my $clues = {};
857 my $is_even = {};
858 my $is_odd = {};
859 #
860 # Turn a string into an array
861 #
862 if (!ref $in_clues) {
863 my @rows = grep {/\S/} split /\n/ => $in_clues;
864 $in_clues = [map {[split]} @rows];
865 }
866 foreach my $r (keys @$in_clues) {
867 foreach my $c (keys @{$$in_clues [$r]}) {
868 my $val = $$in_clues [$r] [$c];
869 next if !$val || $val eq ".";
870 my $cell = cell_name $r + 1, $c + 1;
871 if ($val eq 'e') {$$is_even {$cell} = 1}
872 elsif ($val eq 'o') {$$is_odd {$cell} = 1}
873 else {$$clues {$cell} = $val}
874 }
875 }
876 $clues {$self} = $clues;
877 $is_even {$self} = $is_even;
878 $is_odd {$self} = $is_odd;
879  
880 $self;
881 }
882  
883  
884 ################################################################################
885 #
886 # clues ($self)
887 #
888 # Return an hashref mapping cell names to clues.
889 #
890 # TESTS: 080-clues.t
891 #
892 ################################################################################
893  
894 sub clues ($self) {
895 $clues {$self};
896 }
897  
898  
899 ################################################################################
900 #
901 # clue ($self, $cell)
902 #
903 # Returns the clue in the given cell. If the cell does not have a clue,
904 # return false.
905 #
906 # TESTS: 080-clues.t
907 #
908 ################################################################################
909  
910 sub clue ($self , $cell) {
911 $clues {$self} {$cell}
912 }
913  
914  
915 ################################################################################
916 #
917 # is_even ($self, $cell)
918 # is_odd ($self, $cell)
919 #
920 # Returns wether the cell is given to be even/odd.
921 #
922 # TESTS: 081-is_even_odd.t
923 #
924 ################################################################################
925  
926 sub is_even ($self, $cell) {
927 $is_even {$self} {$cell}
928 }
929 sub is_odd ($self, $cell) {
930 $is_odd {$self} {$cell}
931 }
932  
933  
934 ################################################################################
935 #
936 # set_anti_knight_constraint ($self)
937 # set_anti_king_constraint ($self)
938 #
939 # Set the anti knigt/anti king constraints for the sudoku.
940 #
941 # TESTS: 151-must-differ.t
942 #
943 ################################################################################
944  
945 sub set_anti_knight_constraint ($self) {
946 $constraints {$self} {$ANTI_KNIGHT} = 1;
947 $self;
948 }
949  
950 sub set_anti_king_constraint ($self) {
951 $constraints {$self} {$ANTI_KING} = 1;
952 $self;
953 }
954  
955  
956 ################################################################################
957 #
958 # set_renban ($self, @cells)
959 #
960 # Initialize any renban lines/areas
961 #
962 # TESTS: 170-set_renban.t
963 #
964 ################################################################################
965  
966 sub set_renban ($self, @cells) {
967 if (@cells == 1 && "ARRAY" eq ref @cells) {
968 @cells = @{$cells [0]}
969 }
970  
971 my $name = "REN-" . (1 + keys %{$renban2cells {$self} || {}});
972  
973 foreach my $cell (@cells) {
974 $cell2renbans {$self} {$cell} {$name} = 1;
975 $renban2cells {$self} {$name} {$cell} = 1;
976 }
977  
978 $self;
979 }
980  
981 ################################################################################
982 #
983 # cell2renbans ($self, $cell)
984 #
985 # Return a list of renbans a cell belongs to.
986 #
987 # TESTS: 170-set_renban.t
988 #
989 ################################################################################
990  
991 sub cell2renbans ($self, $cell) {
992 keys %{$cell2renbans {$self} {$cell} || {}}
993 }
994  
995 ################################################################################
996 #
997 # renban2cells ($self, $cell)
998 #
999 # Return a list of cells in a renban.
1000 #
1001 # TESTS: 170-set_renban.t
1002 #
1003 ################################################################################
1004  
1005 sub renban2cells ($self, $renban) {
1006 keys %{$renban2cells {$self} {$renban} || {}}
1007 }
1008  
1009 ################################################################################
1010 #
1011 # same_renban ($self, $cell1, $cell2)
1012 #
1013 # Return a list of renbans to which both $cell1 and $cell2 belong.
1014 # In scalar context, returns the number of renbans the cells both belong.
1015 #
1016 # TESTS: 171-same_renban.t
1017 #
1018 ################################################################################
1019  
1020 sub same_renban ($self, $cell1, $cell2) {
1021 my %seen;
1022 $seen {$_} ++ for $self -> cell2renbans ($cell1),
1023 $self -> cell2renbans ($cell2);
1024 grep {$seen {$_} > 1} keys %seen;
1025 }
1026  
1027  
1028 ################################################################################
1029 #
1030 # init ($self, %args)
1031 #
1032 # Configure the Regexp::Sudoku object.
1033 #
1034 # TESTS: *.t
1035 #
1036 ################################################################################
1037  
1038  
1039 sub init ($self, %args) {
1040 my $args = {%args};
1041  
1042 $self -> init_sizes ($args)
1043 -> init_values ($args)
1044 -> init_houses ($args);
1045  
1046 if (keys %$args) {
1047 die "Unknown parameter(s) to init: " . join (", " => keys %$args)
1048 . "\n";
1049 }
1050  
1051 $self;
1052 }
1053  
1054  
1055 ################################################################################
1056 #
1057 # make_clue_statement ($self, $cell, $value)
1058 #
1059 # Given a cell name, and a value, return a sub subject, and sub pattern
1060 # which sets the capture '$cell' to '$value'
1061 #
1062 # TESTS: 110-make_clue_statement.t
1063 # 120-make_cell_statement.t
1064 #
1065 ################################################################################
1066  
1067 sub make_clue_statement ($self, $cell) {
1068 my $value = $self -> clue ($cell);
1069 my $subsub = $value;
1070 my $subpat = "(?<$cell>$value)";
1071  
1072 map {$_ . $SENTINEL} $subsub, $subpat;
1073 }
1074  
1075  
1076 ################################################################################
1077 #
1078 # make_empty_statement ($cell)
1079 #
1080 # Given a cell name, return a sub subject and a sub pattern allowing the
1081 # cell to pick up one of the values in the sudoku.
1082 #
1083 # TESTS: 100-make_empty_statement.t
1084 # 120-make_cell_statement.t
1085 #
1086 ################################################################################
1087  
1088 sub make_empty_statement ($self, $cell, $method = "values") {
1089 my $subsub = $self -> $method;
1090 my $range = $self -> values_range;
1091 my $subpat = "[$range]*(?<$cell>[$range])[$range]*";
1092  
1093 map {$_ . $SENTINEL} $subsub, $subpat;
1094 }
1095  
1096 sub make_any_statement ($self, $cell) {
1097 $self -> make_empty_statement ($cell, "values")
1098 }
1099 sub make_even_statement ($self, $cell) {
1100 $self -> make_empty_statement ($cell, "evens")
1101 }
1102 sub make_odd_statement ($self, $cell) {
1103 $self -> make_empty_statement ($cell, "odds")
1104 }
1105  
1106  
1107 ################################################################################
1108 #
1109 # make_cell_statement ($cell)
1110 #
1111 # Given a cell name, return a subsubject and subpattern to set a value for
1112 # this cell. Either the cell has a clue (and we dispatch to make_clue),
1113 # or not (and we dispatch to make_empty).
1114 #
1115 # TESTS: 120-make_cell_statement.t
1116 #
1117 ################################################################################
1118  
1119 sub make_cell_statement ($self, $cell) {
1120 my $clue = $self -> clue ($cell);
1121  
1122 $self -> clue ($cell) ? $self -> make_clue_statement ($cell)
1123 : $self -> is_even ($cell) ? $self -> make_even_statement ($cell)
1124 : $self -> is_odd ($cell) ? $self -> make_odd_statement ($cell)
1125 : $self -> make_any_statement ($cell)
1126 }
1127  
1128  
1129  
1130 ################################################################################
1131 #
1132 # semi_debruijn_seq
1133 #
1134 # Return, for the given values, a De Bruijn sequence of size 2 with
1135 # 1) Duplicates removed and
1136 # 2) The first character copied to the end
1137 #
1138 # TESTS: 130-semi_debruijn_seq.t
1139 #
1140 ################################################################################
1141  
1142 sub semi_debruijn_seq ($self, $values = $values {$self}) {
1143 state $cache;
1144 $$cache {$values} //= do {
1145 my $seq = debruijn ($values, 2);
1146 $seq .= substr $seq, 0, 1; # Copy first char to the end.
1147 $seq =~ s/(.)\g{1}/$1/g; # Remove duplicates.
1148 $seq;
1149 };
1150 }
1151  
1152  
1153  
1154 ################################################################################
1155 #
1156 # make_renban_statement ($self, $cell1, $cell2)
1157 #
1158 # Given two cell names, which are assumed to be in the same renban,
1159 # return a sub subject and a sub pattern, which makes iff the difference
1160 # between the cells is less than the size of the renban.
1161 #
1162 # For now, we assume no pair of different size renbans intersect more
1163 # than once.
1164 #
1165 # TESTS: 140-make_renban_statement.t
1166 #
1167 ################################################################################
1168  
1169 sub make_renban_statement ($self, $cell1, $cell2) {
1170 my ($name) = $self -> same_renban ($cell1, $cell2);
1171 my $size = $self -> renban2cells ($name);
1172 my @values = $self -> values;
1173 my $subsub = "";
1174 my $subpat = "";
1175  
1176 for (my $i = 0; $i < @values; $i ++) {
1177 my $d1 = $values [$i];
1178 for (my $j = max (0, $i - $size + 1);
1179 $j < min ($i + $size, scalar @values); $j ++) {
1180 next if $i == $j;
1181 my $d2 = $values [$j];
1182 $subsub .= "$d1$d2";
1183 }
1184 }
1185  
1186 my $range = $self -> values_range ();
1187 my $pair = "(?:[$range][$range])";
1188  
1189 $subpat = "$pair*\\g{$cell1}\\g{$cell2}$pair*";
1190  
1191 map {$_ . $SENTINEL} $subsub, $subpat;
1192 }
1193  
1194  
1195 ################################################################################
1196 #
1197 # make_diff_statement ($self, $cell1, $cell2)
1198 #
1199 # Given two cell names, return a sub subject and a sub pattern which matches
1200 # iff the values in the cell differ.
1201 #
1202 # TESTS: 140-make_diff_statement.t
1203 #
1204 ################################################################################
1205  
1206 sub make_diff_statement ($self, $cell1, $cell2) {
1207 my $subsub = "";
1208 my @values = $self -> values;
1209 my $range = $self -> values_range;
1210  
1211 my $seq = $self -> semi_debruijn_seq;
1212 my $pat = "[$range]*\\g{$cell1}\\g{$cell2}[$range]*";
1213  
1214 map {$_ . $SENTINEL} $seq, $pat;
1215 }
1216  
1217  
1218 ################################################################################
1219 #
1220 # must_differ ($self, $cell1, $cell2)
1221 #
1222 # Returns a true value if the two given cells must have different values.
1223 #
1224 # TESTS: 150-must_differ.t
1225 # 151-must_differ.t
1226 #
1227 ################################################################################
1228  
1229 sub must_differ ($self, $cell1, $cell2) {
1230 my %seen;
1231 $seen {$_} ++ for $self -> cell2houses ($cell1),
1232 $self -> cell2houses ($cell2);
1233  
1234 my $same_house = grep {$_ > 1} values %seen;
1235  
1236 my ($r1, $c1) = cell_row_column ($cell1);
1237 my ($r2, $c2) = cell_row_column ($cell2);
1238  
1239 my $d_rows = abs ($r1 - $r2);
1240 my $d_cols = abs ($c1 - $c2);
1241  
1242 my $constraints = $constraints {$self};
1243 return $same_house
1244 || $$constraints {$ANTI_KNIGHT} && (($d_rows == 1 && $d_cols == 2) ||
1245 ($d_rows == 2 && $d_cols == 1))
1246 || $$constraints {$ANTI_KING} && $d_rows == 1 && $d_cols == 1
1247 ? 1 : 0;
1248 }
1249  
1250  
1251 ################################################################################
1252 #
1253 # init_subject_and_pattern ($self)
1254 #
1255 # Create the subject we're going to match against, and the pattern
1256 # we use to match.
1257 #
1258 # TESTS: TODO
1259 #
1260 ################################################################################
1261  
1262 sub init_subject_and_pattern ($self) {
1263 return $self if $subject {$self} && $pattern {$self};
1264  
1265 my $subject = "";
1266 my $pattern = "";
1267  
1268 my @cells = $self -> cells (1);
1269  
1270 for my $i (keys @cells) {
1271 #
1272 # First the part which picks up a value for this cell
1273 #
1274 my $cell1 = $cells [$i];
1275  
1276 my ($subsub, $subpat) = $self -> make_cell_statement ($cell1);
1277 $subject .= $subsub;
1278 $pattern .= $subpat;
1279  
1280 #
1281 # Now, for all the previous cells, if there is a constraint
1282 # between them, add a clause for them.
1283 #
1284 for my $j (0 .. $i - 1) {
1285 my $cell2 = $cells [$j];
1286 #
1287 # If both cells are a clue, we don't need a restriction
1288 # between the cells.
1289 #
1290 next if $self -> clue ($cell1) && $self -> clue ($cell2);
1291  
1292 my ($subsub, $subpat);
1293  
1294 if (my @renbans = $self -> same_renban ($cell1, $cell2)) {
1295 ($subsub, $subpat) = $self -> make_renban_statement
1296 ($cell1, $cell2);
1297 }
1298 elsif ($self -> must_differ ($cell1, $cell2)) {
1299 ($subsub, $subpat) = $self -> make_diff_statement
1300 ($cell1, $cell2);
1301 }
1302  
1303 if ($subsub && $subpat) {
1304 $subject .= $subsub;
1305 $pattern .= $subpat;
1306 }
1307 }
1308 }
1309  
1310 $subject {$self} = $subject;
1311 $pattern {$self} = "^" . $pattern . '$';
1312  
1313 $self;
1314 }
1315  
1316  
1317 ################################################################################
1318 #
1319 # subject ($self)
1320 #
1321 # Return the subject we're matching against.
1322 #
1323 # TESTS: Test.pm
1324 #
1325 ################################################################################
1326  
1327 sub subject ($self) {
1328 $self -> init_subject_and_pattern;
1329 $subject {$self}
1330 }
1331  
1332  
1333 ################################################################################
1334 #
1335 # pattern ($self)
1336 #
1337 # Return the pattern we're matching with.
1338 #
1339 # TESTS: Test.pm
1340 #
1341 ################################################################################
1342  
1343 sub pattern ($self) {
1344 $self -> init_subject_and_pattern;
1345 $pattern {$self}
1346 }
1347  
1348 1;
1349  
1350 __END__