Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

NP Complete Puzzle game

  1. Aug 9, 2006 #1

    -Job-

    User Avatar
    Science Advisor

    There's a variety of NP-Complete problems like the Clique problem, the Hamiltonian cycle problem, Satisfiability, etc.
    Recently i discovered a simple puzzle problem that is NP-Complete (the proof involves a straightforward reduction of the Clique problem).

    Anyway, i built the actual puzzle game, using flash and i think it's cool because it illustrates the difficulty of solving NP-Complete problems and why, in all likelihood, P != NP.

    http://www.bloo.us/blog/?blogger=4&pid=13

    I'm thinking of putting together a site with NP-Complete puzzle games. :smile: I can think of a couple of others.
     
  2. jcsd
  3. Aug 10, 2006 #2

    0rthodontist

    User Avatar
    Science Advisor

    What is the reduction?
     
  4. Aug 10, 2006 #3

    -Job-

    User Avatar
    Science Advisor

    It's a simple reduction. Consider a graph of n nodes. The clique problem asks for the size of the biggest clique in the graph, that is, the largest subset of the n nodes with the property that every node in that subset is connected to every other node in that subset.

    We can transform the clique problem into the "Grid" problem (that's what i'm calling it i guess) by making use of an n*n sized grid. For each box in the grid, at some position (x, y), let it be black if the x-th node in the graph is connected to the y-th node in the graph. We'll treat each node in the graph as if it were connected to itself, so that the box at position (k, k) is black.

    It follows that a graph with a clique of size C will have a C*C sized square block of black boxes in its corresponding grid. Naturally, the block will only be immediatly visible if the nodes that form the clique are consecutive (for example, nodes 4, 5, 6 and 7). If the nodes are not consecutive then the block will be spread out through the grid, but you'll always be able to make it visible by reordering the rows and columns.
    Hence, it follows that if you can create a C*C sized block of dark boxes on the grid, then the corresponding graph must have a clique of size C.
    Thus, the problem of determining the size of the biggest clique within a graph reduces to the problem of determining the size of the biggest block that you can put together in the grid, by reordering the rows and columns.

    This is a polynomial time reduction, O(n^2) steps, so a polynomial-time solution to the Grid problem implies a polynomial-time solution to the Clique problem, an NP-Complete problem. Hence the Grid problem is NP-Complete.
     
    Last edited: Aug 10, 2006
  5. Aug 11, 2006 #4
    I've written a puzzle based on the NP complete problem of Boolean Formula Satisfiability (SAT3) at http://www.chronon.org/applets/sat.html , together with the option to automatically find a solution. What surprised me was how fast the algorithm is in most cases. Typically it takes 100 - 200 steps, a lot less than an exhaustive search of 2^26 steps.
     
    Last edited: Aug 11, 2006
  6. Aug 11, 2006 #5

    -Job-

    User Avatar
    Science Advisor

    That's cool. The most i saw was ~150 steps.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: NP Complete Puzzle game
  1. SAT is NP-complete (?) (Replies: 10)

  2. Problems in NP (Replies: 5)

  3. P vs NP and factoring (Replies: 3)

Loading...