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 EasyAnswerComment/E-mail if you want a solution to be published

Puzzle 75a: Latin Square

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 EasyAnswerComment/E-mail if you want a solution to be published

Puzzle 75b: TomTom

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.

Advertisements

3 thoughts on “Puzzle 75: TomTom is NP-complete

  1. Sigh… -_-
    Well, it will still look like a good project, my science teacher doesn’t have to know about this…

    I was planning on posting my NP-complete TomTom on Friday, and I guess I still will, its just very anti-climactic now

    Reply
  2. Pingback: Puzzle 35 – Yajilin and | Jack Lance Puzzles

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s