Puzzle 75: TomTom is NP-complete

This post has two puzzles!

Latin Square Put an integer between 1 and the length of the grid (5) inclusive such that each row/column has each number exactly once.

Expected difficulty Easy • Answer • Comment/E-mail if you want a solution to be published

Puzzle 75: TomTom is NP-complete
Latin Square

TomTom Put an integer between 1 and the length of the grid (10) inclusive such that each row/column has each number exactly once. The number at the top-left of each region indicates the value of a mathematical operation (addition, subtraction, multiplication, division) applied successively to all digits in the cage, starting with the largest digit for subtraction and division (e.g. 1,2,4 with subtraction is a 1- clue as 4-2-1 = 1). (Description from Grandmaster Puzzles)

Expected difficulty Easy • Answer • Comment/E-mail if you want a solution to be published

Puzzle 75: TomTom is NP-complete
TomTom

I guess the two puzzles above prove that TomTom is NP-complete. We can see a trivial polynomial transformation from a Latin Square to a TomTom, and Latin Square is NP-complete.

So, sorry for Jacob Lance.

Puzzle 18: TomTom

TomTom. Put the required numbers in the grid so each number appears exactly once in every row and column. Additionally, for every bold region, the arithmetic operation and target number must be fulfilled; that is, starting from the largest number and applying the designated operation to each of the other number must produce the required target number. (E.g. If you have 9+, you can have 2,3,4 in it since 4+2+3=9, and if you have 2-, you can have 2,2,6 in it since 6-2-2=2.) This one would be easy-medium.

Puzzle 18: TomTom

Yep. If you know what Thomas Synder aka motris did three years ago, I’m using the same phrasing of the rules. But that comes up redundant because I only used addition and multiplication 😛

EDIT (8 March 2013): Yes, I even changed its name from KenKen to TomTom because KenKen has 1-n number range and no modified subtraction/division operations.

A first try in TomTom. Since I hate 5 without the existence of 10 (hence buffing the power of multiplication), I changed it to 6 instead. Maybe if I have a 6×6 TomTom, I’ll use 1,2,3,4,6,9 as the numbers for more confusion over multiplication. But that buffs addition a bit. Oh well, whatever.

12 hours to Puzzle 19. So I’ll tell you…it’s a Skyscrapers.