What is the connection between NP-Complete problems and this puzzle game?

[-Job-]

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. I can think of a couple of others.

 

[0rthodontist]

What is the reduction?

 

[-Job-]

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.

 

[chronon]

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.

 

[-Job-]

That's cool. The most i saw was ~150 steps.