Ripple Effect is NP-complete. We reduce from 3-SAT.
Tag Archives: proof
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.
Puzzles!
Yeah, I will continue making puzzles, only not at the same rate as the one in my blog. Probably once every time I have the time. Maybe like betaveros and his one-month-a-puzzle schedule (though he starts deviating to less than a week per puzzle (who said I won’t either? (yay parentheses nesting))). If I can make the picture from this phone. >_<
Meanwhile, inspired from this blog entry, here’s a little puzzle for you to crack…
S01 – Slitherlink
This is a Slitherlink puzzle, with the All-Odd variation. All the odd numbers have been given to you; an empty cell indicates that its clue is not odd. Your task is not (only) to find the solution; your task is to prove that the solution is unique.
EDIT: Okay prove that there is no solution. Apparently you must make a loop.
Yeah it’s cruel. And whoa a post within a post.
Chaos at the Sky 
