# NP-Complete Games and Puzzles

Now on its own page!

Advertisements

## 9 thoughts on “NP-Complete Games and Puzzles”

1. My school lets you do “math projects” for the science fair so I’m proving that Kenkens are reducible to 3-SAT and therefore NP-complete.

Reply
• Well, I’m doing it for my science project this year, so no result yet. But I have made:
Wires
Crossing
Splitting
Not Gates
Xor Gates (not really necessary but whatever)
All I need to prove is an AND or OR gate and then I’d be done. I’ll provide a link when I write up what I’ve done.

Reply
• I suddenly got a thought. Isn’t KenKen (or let’s call TomTom) obviously NP-complete, by reduction from Latin Squares?

Reply
• In order for this to be true, if my understanding is right, you would need a bunch of individual 1×1 boxes in the original grid. It is possible that these boxes would split the grid into two separate regions, and you would then need to give the sums of those regions.

If that isn’t the case, then…. well…. oh well. I just reduced it to 3-SAT for fun then.

Reply
• Make the KenKen double size, with every other row/column there just to allow the blocked off regions to come in contact with other cells. The problem is that this might allow unwanted solutions.

Reply
2. e_is_cool says:

TITOL
~e_is_cool

Reply