| 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__ |