Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
The most common mistake I make when solving KenKen puzzles is that I fail to enumerate all the correct combinations that could fill a cage. It can be tedious (and hence error-prone) to think up all the combinations for larger addition and multiplication cages.

This is not intended to be part of a complete puzzle solver. I just want to use it to "check my math" after I realize I made a mistake while working on a puzzle.

Since I don't have tests for the code, there could be bugs. One limitation is that it does not account for the shape of a cage. Depending on the shape, some cages forbid the same number appearing more than once, while others allow one or more numbers to appear multiple times. There is an option to control the number of duplicates to some degree.

Here is an example output for a 9x9 grid with a cage size of 5, and the numbers adding up to 29:

kenken -c 5 -n 29 -r 2 Grid size: 9 Cage size: 5 Operator : a Number : 29 Reject : 2 29+ = 1 + 4 + 7 + 8 + 9 29+ = 1 + 5 + 6 + 8 + 9 29+ = 2 + 3 + 7 + 8 + 9 29+ = 2 + 4 + 6 + 8 + 9 29+ = 2 + 5 + 6 + 7 + 9 29+ = 3 + 4 + 5 + 8 + 9 29+ = 3 + 4 + 6 + 7 + 9 29+ = 3 + 5 + 6 + 7 + 8 Combinations = 8

For this run, I rejected all duplicates. If I rerun allowing numbers to appear twice, the number of combinations jumps up to 48.

I was surprised at how little of my own code I had to write because it leverages so heavily on CPAN and Core modules.

use warnings FATAL => 'all'; use strict; use Getopt::Long qw(GetOptions); use Pod::Usage qw(pod2usage); use List::Util qw(sum uniq reduce max); use List::MoreUtils qw(frequency); use Math::Factor::XS qw(factors); use Algorithm::Combinatorics qw(combinations_with_repetition); my @combos; my %opt; parse_args(); print <<"EOF"; Grid size: $opt{grid} Cage size: $opt{cage} Operator : $opt{operator} Number : $opt{num} Reject : $opt{reject} EOF if ($opt{operator} eq 'a') { addition (); } elsif ($opt{operator} eq 's') { subtraction (); } elsif ($opt{operator} eq 'm') { multiplication (); } elsif ($opt{operator} eq 'd') { division (); } show_results(); exit; sub subtraction { die "ERROR: Number must be less than grid size.\n" if $opt{num} >= + $opt{grid}; die "ERROR: Number must be greater than 0.\n" if $opt{num} < 1; for my $i (($opt{num}+1) .. $opt{grid}) { push @combos, [$i, ($i - $opt{num})]; } } sub division { die "ERROR: Number must be <= grid size.\n" if $opt{num} > $opt{gr +id}; die "ERROR: Number must be greater than 1.\n" if $opt{num} < 2; for my $i (1 .. $opt{grid}) { my $mult = $i * $opt{num}; last if $mult > $opt{grid}; push @combos, [$mult, $i]; } } sub addition { die "ERROR: Number must be greater than 2.\n" if $opt{num} < 3; my @nums = 1 .. $opt{grid}; for my $aref (combinations_with_repetition(\@nums, $opt{cage})) { my @nums = @{ $aref }; if (sum(@nums) == $opt{num}) { push @combos, [@nums]; } } } sub multiplication { die "ERROR: Number must be greater than 1.\n" if $opt{num} < 2; my @factors = grep { $_ <= $opt{grid} } (1, factors($opt{num}), $o +pt{num}); for my $aref (combinations_with_repetition(\@factors, $opt{cage})) + { my @nums = @{ $aref }; my $prod = reduce { $a * $b } @nums; if ($prod == $opt{num}) { push @combos, [@nums]; } } } sub show_results { my %char = (a => '+', m => 'x', s => '-', d => '/'); my $oper = $char{$opt{operator}}; my $cnt = 0; for my $aref (@combos) { my @nums = @{ $aref }; if (uniq(@nums) > 1) { # Make sure all numbers are not the sam +e my %freq = frequency(@nums); my $max = max(values %freq); if ($max < $opt{reject}) { print "$opt{num}$oper = ", join(" $oper ", @nums), "\n +"; $cnt++; } } } if ($cnt) { print "\nCombinations = $cnt\n\n"; } else { die "ERROR: No combinations found.\n"; } } sub parse_args { %opt = ( operator => 'a', grid => 9, cage => 2, num => 8, reject => 9, ); GetOptions(\%opt, qw( help operator=s grid=i cage=i num=i reject=i )) or pod2usage(); $opt{operator} = lc substr $opt{operator}, 0, 1; die "ERROR: operator must be one of [amsd]\n" unless $opt{operato +r} =~ /[asmd]/; die "ERROR: grid must be in range 3-9\n" if ($opt{grid} < 3) or ($ +opt{grid} > 9); die "ERROR: cage size must be greater than 1\n" if $opt{cage} < 2; die "ERROR: cage size must be less than 10\n" if $opt{cage} > 9; die "ERROR: reject must be greater than 1\n" if $opt{reject} < 2; die "ERROR: unsupported args: @ARGV\n" if @ARGV; # Force cage size to 2 for subtraction/division $opt{cage} = 2 if $opt{operator} =~ /[sd]/; pod2usage(-verbose => 2) if $opt{help}; } =head1 NAME B<kenken> - Helper for KenKen puzzle =head1 SYNOPSIS kenken [options] Options: -help Verbose help -operator str Operator [asmd] (default=a) -grid int Size of grid [3-9] (default=9): 9 means 9x9 -cage int Size of cage (default=2) -num int Number shown in cage next to the operator (def +ault=8) -reject int Reject duplicate numbers =head1 DESCRIPTION Helper for KenKen puzzle. Find all possible combinations of numbers w +hich could be in a single cage. This does not account for the shape of the + cage; therefore, some combinations might not be legal. =head1 OPTIONS All options can be abbreviated. =over 4 =item B<-operator> The operator must be one of the following: a for addition s for subtraction m for multiplication d for division By default, the operator is "a" for addition. To choose a different operator, such as multiplication, use the C<-operator> option. kenken -operator m =item B<-grid> By default, the grid is assumed to be 9x9. Supported grid sizes are 3 +x3 to 9x9. To choose another grid size, use the C<-grid> option. kenken -grid 3 =item B<-cage> By default, the cage size is assumed to be 2. To choose another cage size, use the C<-cage> option. kenken -cage 4 =item B<-num> By default, the number shown in the cage next to the operator is 8 To choose another number, use the C<-num> option. kenken -num 25 =item B<-reject> By default, any amount of duplicate numbers are allowed within a cage. To control the maximum number of duplicates within a cage, use the C<-reject> option. For example, if a cage has 5 cells, reject all combinations which have the same number at least 3 times: kenken -reject 3 =item B<-help> Show verbose usage information. =back =head1 EXAMPLES 8x8 grid, 3 cells in a cage, multiplication operator, number=24, only show unique numbers in cells: kenken -grid 8 -cage 3 -operator m -num 24 -reject 2 Use all defaults: 9x9 grid, 2 cells in a cage, addition operator, numb +er=8: kenken =head1 SEE ALSO L<https://en.wikipedia.org/wiki/KenKen> =cut

In reply to KenKen puzzle helper by toolic

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others studying the Monastery: (6)
As of 2024-03-28 16:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found