Grid Puzzle Split Algorithm

Question

I want to generate a random partition of an $N\times N$ grid into $N$ connected groups having $N$ tiles each. How would I do this? Max grid size will be 10x10. Below is an example for a 5x5 grid.

Answer 1

A possible technique to generate random tilings is:

• Represent all possible solutions as a Zero Suppressed BDD (see for example The Art of Computer Programming volume 4, chapter 7.1.4, or this page). Every way to place any piece on the board corresponds to a variable in the ZDD. The constraints are that every tile is covered exactly once, which can be done by making an "exactly once"-ZDD for every tile, and then intersecting all those ZDDs. An "exactly once"-ZDD is easy to make, it's a single chain of nodes where a constrained variable (a piece-placement that covers this tile) corresponds to a node with a HI branch to TOP and a LO branch to the next node, and an unconstrained variable has both LO and HI going to the next node.
• For each node in the ZDD, count how many solutions it leads to. Runs in time proportional to the size of the ZDD (not the number of solutions) if memoization is used.
• Then, top down, randomly choose between the two children of a node using the ratio of solution counts as threshold. That would uniformly choose a random solution from the space of solutions. Runs in time proportional to the number of variables (depth of the ZDD).

Answer 2

One approach is to write a SAT formula to represent valid solutions, and then find a random satisfying assignment to this formula.

Introduce boolean variables $x_{i,j}$, if cell $i$ is covered by tile $j$. Then you can write boolean constraints (clauses) on these variables that express that they correspond to a valid solution. Let $\varphi(x)$ denote the formula that contains the conjunction of these clauses.

Now we want to find a random satisfying assignment to $\varphi(x)$. One standard method is to choose a simple hash function $h$, and a random value $y$, and then use a SAT solver find a satisfying assignment to the formula $\varphi(x) \land (h(x)=r)$. (If there is no satisfying assignment, choose a new $h,r$ and try again until you find one.) One concrete way to do this that might suffice is to choose $h$ so that each bit of $h(x)$ is the xor of three randomly chosen variables $x_{i,j}$. Ideally, you want to choose the size of the output of $h$ to be approximately $\log_2 N$ where $N$ is the number of satisfying assignments of $\varphi(x)$. Since you might not know that number, it's reasonable to use binary search to choose a length of $h$ so that a randomly chosen $r$ often makes $\varphi(x) \land (h(x)=r)$ satisfiable.