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.
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.
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.
Chaos at the Sky 
The Nurikabe paper mentions that Galaxies puzzles are NP-complete. I found this:
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=C7530265886EAAF0BD17B8F22A9873CF?doi=10.1.1.19.6267&rep=rep1&type=pdf
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.
Any link to the result?
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.
I suddenly got a thought. Isn’t KenKen (or let’s call TomTom) obviously NP-complete, by reduction from Latin Squares?
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.
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.
TITOL
~e_is_cool
Pingback: Puzzle 35 – Yajilin and | Jack Lance Puzzles