Is there such thing as an Availability Group failover trigger?

What are the out-of-universe reasons for the references to Toby Maguire-era Spider-Man in ITSV

8 Prisoners wearing hats

When the Haste spell ends on a creature, do attackers have advantage against that creature?

Using audio cues to encourage good posture

Can a party unilaterally change candidates in preparation for a General election?

Is it fair for a professor to grade us on the possession of past papers?

If a VARCHAR(MAX) column is included in an index, is the entire value always stored in the index page(s)?

Is there a kind of relay only consumes power when switching?

What do you call a floor made of glass so you can see through the floor?

How would a mousetrap for use in space work?

How to answer "Have you ever been terminated?"

What does "lightly crushed" mean for cardamon pods?

What font is "z" in "z-score"?

Maximum summed powersets with non-adjacent items

Should I use a zero-interest credit card for a large one-time purchase?

また usage in a dictionary

Do I really need recursive chmod to restrict access to a folder?

Using et al. for a last / senior author rather than for a first author

Can anything be seen from the center of the Boötes void? How dark would it be?

Why does the resolve message appear first?

How can I use the Python library networkx from Mathematica?

Is it common practice to audition new musicians 1-2-1 before rehearsing with the entire band?

When a candle burns, why does the top of wick glow if bottom of flame is hottest?

Uniqueness of spanning tree on a grid.

2

1

$begingroup$

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

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.)

combinatorics graph-theory puzzle trees

share|cite|improve this question

asked 5 hours ago

Peter KageyPeter Kagey

1,61772053

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This genre of logic puzzle is known originally as Netwalk.
  $endgroup$
  – Mike Earnest
  4 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @MikeEarnest, thanks for the reference. Based on this picture from this Reddit thread, it looks like (some versions of) Netwalk are on a torus instead of a grid—although that presents an interesting generalization of this question.
  $endgroup$
  – Peter Kagey
  4 hours ago
  
  
  

  
  
  
  

add a comment | 

2

1

$begingroup$

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

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.)

combinatorics graph-theory puzzle trees

share|cite|improve this question

asked 5 hours ago

Peter KageyPeter Kagey

1,61772053

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This genre of logic puzzle is known originally as Netwalk.
  $endgroup$
  – Mike Earnest
  4 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @MikeEarnest, thanks for the reference. Based on this picture from this Reddit thread, it looks like (some versions of) Netwalk are on a torus instead of a grid—although that presents an interesting generalization of this question.
  $endgroup$
  – Peter Kagey
  4 hours ago
  
  
  

  
  
  
  

add a comment | 

$begingroup$

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

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.)

combinatorics graph-theory puzzle trees

share|cite|improve this question

asked 5 hours ago

Peter KageyPeter Kagey

1,61772053

$endgroup$

share|cite|improve this question

asked 5 hours ago

Peter KageyPeter Kagey

1,61772053

share|cite|improve this question

asked 5 hours ago

Peter KageyPeter Kagey

1,61772053

asked 5 hours ago

Peter KageyPeter Kagey

1,61772053

asked 5 hours ago

Peter KageyPeter Kagey

1,61772053

1 Answer
1

active

oldest

votes

4

$begingroup$

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

┏━━━┓

┗┓╻╻┃

╺┫┣┛┃

┏┫┣╸┃

╹╹┗━┛

┏━━━┓

┗┓╻╻┃

╺┻┻┛┃

┏┳┳╸┃

╹╹┗━┛

share|cite|improve this answer

answered 3 hours ago

edderioferedderiofer

1561

New contributor

edderiofer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Based on the picture in the question, all three ends of the T shapes have to connect to an adjacent piece; you can't have one end of the T run directly into the flat side of a | piece.
  $endgroup$
  – Misha Lavrov
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It doesn't "run directly into the flat side of a | piece". There's actually a dead end "╸" piece in between, so this satisfies all the rules.
  $endgroup$
  – edderiofer
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Oh, I see. I couldn't quite read it in your answer, but it showed up when I highlighted it and now everything makes sense.
  $endgroup$
  – Misha Lavrov
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Here is an interactive illustration of the solution: chiark.greenend.org.uk/~sgtatham/puzzles/js/…
  $endgroup$
  – Mike Earnest
  2 hours ago
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3191645%2funiqueness-of-spanning-tree-on-a-grid%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

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

┏━━━┓

┗┓╻╻┃

╺┫┣┛┃

┏┫┣╸┃

╹╹┗━┛

┏━━━┓

┗┓╻╻┃

╺┻┻┛┃

┏┳┳╸┃

╹╹┗━┛

share|cite|improve this answer

answered 3 hours ago

edderioferedderiofer

1561

New contributor

edderiofer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Based on the picture in the question, all three ends of the T shapes have to connect to an adjacent piece; you can't have one end of the T run directly into the flat side of a | piece.
  $endgroup$
  – Misha Lavrov
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It doesn't "run directly into the flat side of a | piece". There's actually a dead end "╸" piece in between, so this satisfies all the rules.
  $endgroup$
  – edderiofer
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Oh, I see. I couldn't quite read it in your answer, but it showed up when I highlighted it and now everything makes sense.
  $endgroup$
  – Misha Lavrov
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Here is an interactive illustration of the solution: chiark.greenend.org.uk/~sgtatham/puzzles/js/…
  $endgroup$
  – Mike Earnest
  2 hours ago
  

  
  
  
  

add a comment | 

4

$begingroup$

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

┏━━━┓

┗┓╻╻┃

╺┫┣┛┃

┏┫┣╸┃

╹╹┗━┛

┏━━━┓

┗┓╻╻┃

╺┻┻┛┃

┏┳┳╸┃

╹╹┗━┛

share|cite|improve this answer

answered 3 hours ago

edderioferedderiofer

1561

New contributor

edderiofer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Based on the picture in the question, all three ends of the T shapes have to connect to an adjacent piece; you can't have one end of the T run directly into the flat side of a | piece.
  $endgroup$
  – Misha Lavrov
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It doesn't "run directly into the flat side of a | piece". There's actually a dead end "╸" piece in between, so this satisfies all the rules.
  $endgroup$
  – edderiofer
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Oh, I see. I couldn't quite read it in your answer, but it showed up when I highlighted it and now everything makes sense.
  $endgroup$
  – Misha Lavrov
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Here is an interactive illustration of the solution: chiark.greenend.org.uk/~sgtatham/puzzles/js/…
  $endgroup$
  – Mike Earnest
  2 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

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

┏━━━┓

┗┓╻╻┃

╺┫┣┛┃

┏┫┣╸┃

╹╹┗━┛

┏━━━┓

┗┓╻╻┃

╺┻┻┛┃

┏┳┳╸┃

╹╹┗━┛

share|cite|improve this answer

answered 3 hours ago

edderioferedderiofer

1561

New contributor

edderiofer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

┏━━━┓

┗┓╻╻┃

╺┫┣┛┃

┏┫┣╸┃

╹╹┗━┛

┏━━━┓

┗┓╻╻┃

╺┻┻┛┃

┏┳┳╸┃

╹╹┗━┛

share|cite|improve this answer

answered 3 hours ago

edderioferedderiofer

1561

New contributor

edderiofer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 3 hours ago

edderioferedderiofer

1561

New contributor

edderiofer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 3 hours ago

edderioferedderiofer

1561