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
      • 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. 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