Tag Archives: X3C

Generalized Instant Insanity

The last problem in the “Games and Puzzles” section comes from a commercial puzzle (though one based on a much older puzzle).  It’s cool how these sorts of things pop up- a toy or game comes out and then people analyze it mathematically and find some neat features about it.

The problem: Generalized Instant Insanity.  This is problem GP15 in the appendix.

The description: Given a set Q of cubes, and a set C of colors we paint on the sides of each cube (and where |Q| = |C|) is there a way to arrange the cubes in a stack such that each color in C appears exactly once on each side?

Example: The Wikipedia page for the Instant Insanity game has a good description of the game and an example of the solution when Q = 4.

Reduction: Roberson and Munro reduce from “Exact Cover”.  I don’t think I’ve done this problem, but it’s basically X3C where the sizes of the sets can be any size.  (So it’s a trivial reduction from X3C).

They start by designing a graph representation of the puzzle, similar to the one shown on the Wikipedia page. Vertices correspond to colors, an edge connects two vertices if they are on opposite sides of the came cube, and the edges are labeled with the name of the cube.  The puzzle has a solution if and only if we can find two edge disjoint cycles that touch each vertex and edge label exactly once.  The two cycles correspond to the two sets of opposite faces we can see (since 2 sides of each cube are hidden by the stack).  Again, go look at the graphs in the Wikipedia article– they show this pretty nicely.

So, to perform the reduction, we’re given a set S {s1..sm} and a collection T of subsets of S, and need to make a graph (which corresponds to a puzzle).  Each element in S will become a vertex in the graph.  Each of these vertices will have a self-loop and be labeled ζi (So each vertex is a different color, and each self-loop is part of a different cube- so each cube has one color on opposite sides).

Each element si inside a set Th of T will also have a vertex: vi,h. This vertex has an edge with the next largest level sj within Th, wrapping around if we’re at the last element of Th. These edges are labeled ϒh,j.  We also have an edge from sjto vh,j if sj is in Th labeled with δh,j.  We also have 2 copies of self-loops from each vh,j to itself labeled ϒh,j.

They then add some extra edges to give the graph the properties:

  • One of the self-loops from vh,i to itself has to be in one of the two cycle sets.
  • If the edge from vh,i to sj (labeled ϒh,j) is in the other cycle set, then the edge from sj to vh,j (labeled δh,j) is also in that cycle set
  • The ζi edge label has to be used, and so will have to be used on an si vertex the cycle that uses that vertex will also have to have the labels ϒh,j and δh,j for some h.
  • The loops (labeled ζj and ϒh,j) are in one cycle set and the paths (labeled ϒh,j and δh,j) are in the other.

With these properties, then solving the puzzle means we have to find h1 through hm that correspond to sets Th in T, but also where there is a path ϒh,jh,j in the graph for each sj in Th_i.  We make sure no elements in S are repeated by making sure the puzzle only uses each sj vertex once.

Difficulty: 8.  I glossed over a lot of the construction, especially the definition of a “p-selector”, which is a subgraph that helps set up a lot of the properties above.  That definition is very hard for me to follow.

Crossword Puzzle Construction

Closing in on the end of the section, this is a “private communication” problem that I think I figured out myself.

The problem: Crossword Puzzle Construction.  This is problem GP14 in the appendix.

The description: Given a set W of words (strings over some finite alphabet Σ), and an n x n matrix A, where each element is 0 (or “clear”) or 1 (or “filled”).  Can we fill the 0’s of A with the words in W?  Words can be horizontal or vertical, and can cross just like crossword puzzles do, but each maximally contiguous horizontal or vertical segment of the puzzle has to form a word.

Example: Here’s a small grid.  *’s are 1, dashes are 0:

* *
 –  –  –
 –
* * *
* * * *

Suppose our words were: {SEW, BEGIN, EAGLE, S, OLD, SEA, EGGO, WILLS, BE, SEA, NED}.  (Notice the lone “S” is a word.  That’s different from what you’d see in a normal crossword puzzle)

We can fill the puzzle as follows:

* S E W *
B E G I N
E A G L E
* * O L D
* * * S *

Notice that we can’t use the first two letters of “BEGIN” as our “BE”, because the word continues along.  That’s what the “maximally contiguous” part of the definition is saying.

Reduction: From X3C. We’re given a set X with 3q elements, and a collection C of 3-element subsets of X.  We’re going to build a 3q x q puzzle with no black squares. (We’ll get back to making this a square in a minute)  Each word in W will be a bitvectorof length 3q, with a 0 in each position that does not have an element, and a 1 in the positions that do.  So, if X was {1,2,3,4,5,6,7,8,9} the set {1,3,5} would be 101010000

We also add to A the 3q bitvectors that have exactly one 1 (and 0’s everywhere else). The goal is to find a subset of C across the “rows” of the puzzle, such that the “columns” of the puzzle form one of the bitvectors.  If we can form each of the bitvectors, we have found a solution to X3C.  If we have a solution to X3C, we can use the elements in C’ and place them in the rows of the 3q x q puzzle block to come up with a legal crossword puzzle.

We’re left with 2 additional problems:  The grid needs to be a square, instead of a 3q x q rectangle, and the legal crossword puzzle solution needs to use all of the words in W, not the the ones that give us a C’.  We can solve both by padding the grid with blank squares.  Spaced out through the blank spaces are 1 x 3q sections of empty space surrounded by black squares.  We can put any word in C-C’ in any of these sections, and that’s where we’ll put the words that are not used.

(This also means we’ll have to add 3x|(C’-C)| 1’s and (3q-3)|(C’-C)| 0’s to our word list for all of the 1-length words in those  columns.)  Then we add enough blank spaces around the grid to make it a square.

Difficulty: 5 if I’m right, mainly because of the extra work you have to do at the end.  The comments in G&J say that the problem is NP-Complete “even if all entries in A are 0”, which is usually a hint that the “actual” reduction used an empty square grid.  I wonder if that reduction doesn’t have my hacky stuff at the end.

Protected: K-Relevancy

This content is password protected. To view it please enter your password below:

Protected: Minimum Weight Solution to Linear Equations

This content is password protected. To view it please enter your password below:

Protected: Staff Scheduling

This content is password protected. To view it please enter your password below:

Protected: Expected Component Sum

This content is password protected. To view it please enter your password below:

Protected: Subset Product

This content is password protected. To view it please enter your password below:

Protected: Minimum Cover

This content is password protected. To view it please enter your password below:

Protected: Minimum Edge-Cost Flow

This content is password protected. To view it please enter your password below:

Protected: Geometric Traveling Salesman

This content is password protected. To view it please enter your password below: