KenKen You Do It?

This problem asks you the number of possible ways to fill in a grid such that the numbers in the grid (sum,difference,multiply,quotient) to some given target.

The subtract/divide instance are easy, as they are limited to two squares, which means there only 81 possibilities. Just try them all

The sum/multiply instances are limited to 10 squares, which is a major hint that this is brute force. Obviously trying all possibilities gives us 9^10, which is too big. The graph will be heavily pruned, however. Since each square is guaranteed to share a side with one other box, we're already down to 9*8^9 (worst case is a zig zag and each box can be filled with anything but whatever the last value was), which is still slightly too big (1.2 billion).

We are, however, severely limited by the values we can put in our boxes while still being on track to sum/multiply to the target. For instance if our target is 81, and there are 10 boxes, and our first two selections are 9, then the max value in the rest of the boxes is 1.

That should be sufficient to get a fast enough runtime.

Note: that factoring the number would be helpful if this were just for multiplication, as it would restrict further the digits that could go in any box, but such an optimization does not aid addition.

The values in a current row and column can be stored as a mask in an array (one array for rows of 9 elements, and one for columns. Set box to "true" if you've placed that number in that column. Should be faster than hash map). A hash map may work as well, as it is also constant lookup.