Uniqueness of spanning tree on a grid.

183 Views Asked by At

When I was at the Graduate Student Combinatorics Conference earlier this month, someone introduced me to a puzzle game called Noodles!.

The game starts with a collection of "pipes" on a grid (centered on each vertex), clicking on a piece rotates it $90^\circ$, and a piece can be rotated any number of times. The goal is to turn the final configuration of pipes into a spanning tree (of the grid graph), as shown in the screenshots below.

Example

An example of Noodles!

Question

We left the conference with an unsolved question: Are solutions to this puzzle always unique? Or is it possible to come up with a starting configuration (on any size grid) that has multiple trees as solutions?

(The prevailing guess is that solutions are unique, but nobody could manage to prove it.)

1

There are 1 best solutions below

4
On BEST ANSWER

No, solutions are not unique. The four "T" shaped pieces in the grid below can be rotated into either of two configurations:

┏━━━┓
┗┓╻╻┃
╺┫┣┛┃
┏┫┣╸┃
╹╹┗━┛
┏━━━┓
┗┓╻╻┃
╺┻┻┛┃
┏┳┳╸┃
╹╹┗━┛