Uniqueness of spanning tree on a grid. Unicorn Meta Zoo #1: Why another podcast? Announcing the arrival of Valued Associate #679: Cesar ManaraGraph - Minimum spanning treeCheapest spanning treeexistence of a spanning treeSpanning tree with unique paths.Euclidean Minimum Spanning Tree PropertyDirected spanning treeMinimum spanning tree for a weighted square gridGraph Theory(Spanning Tree)Spanning Tree Vs Minimum Spanning Treemaximum spanning tree
My admission is revoked after accepting the admission offer
What is the best way to deal with NPC-NPC combat?
PIC mathematical operations weird problem
Would reducing the reference voltage of an ADC have any effect on accuracy?
What *exactly* is electrical current, voltage, and resistance?
As an international instructor, should I openly talk about my accent?
Is Electric Central Heating worth it if using Solar Panels?
How long after the last departure shall the airport stay open for an emergency return?
What do you call the part of a novel that is not dialog?
Rolling Stones Sway guitar solo chord function
Israeli soda type drink
I preordered a game on my Xbox while on the home screen of my friend's account. Which of us owns the game?
Second order approximation of the loss function (Deep learning book, 7.33)
The art of proof summarizing. Are there known rules, or is it a purely common sense matter?
What’s with the clanks in Endgame?
Passing args from the bash script to the function in the script
Can you stand up from being prone using Skirmisher outside of your turn?
Do I need to protect SFP ports and optics from dust/contaminants? If so, how?
std::is_constructible on incomplete types
Suing a Police Officer Instead of the Police Department
How to translate "red flag" into Spanish?
How can I wire a 9-position switch so that each position turns on one more LED than the one before?
Mistake in years of experience in resume?
"Whatever a Russian does, they end up making the Kalashnikov gun"? Are there any similar proverbs in English?
Uniqueness of spanning tree on a grid.
Unicorn Meta Zoo #1: Why another podcast?
Announcing the arrival of Valued Associate #679: Cesar ManaraGraph - Minimum spanning treeCheapest spanning treeexistence of a spanning treeSpanning tree with unique paths.Euclidean Minimum Spanning Tree PropertyDirected spanning treeMinimum spanning tree for a weighted square gridGraph Theory(Spanning Tree)Spanning Tree Vs Minimum Spanning Treemaximum spanning tree
$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
asked Apr 17 at 21:07
Peter KageyPeter Kagey
1,55772053
$endgroup$
This question has an open bounty worth +100
reputation from Peter Kagey ending ending at 2019-04-28 21:42:17Z">in 4 days.
One or more of the answers is exemplary and worthy of an additional bounty.
Edderiofer’s answer was unexpectedly simple and nice!
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
asked Apr 17 at 21:07
Peter KageyPeter Kagey
1,55772053
$endgroup$
This question has an open bounty worth +100
reputation from Peter Kagey ending ending at 2019-04-28 21:42:17Z">in 4 days.
One or more of the answers is exemplary and worthy of an additional bounty.
Edderiofer’s answer was unexpectedly simple and nice!
1
$begingroup$
This genre of logic puzzle is known originally as Netwalk.
$endgroup$
– Mike Earnest
Apr 17 at 21:27
$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
Apr 17 at 21:36
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
asked Apr 17 at 21:07
Peter KageyPeter Kagey
1,55772053
$endgroup$
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
combinatorics graph-theory puzzle trees
asked Apr 17 at 21:07
Peter KageyPeter Kagey
1,55772053
asked Apr 17 at 21:07
Peter KageyPeter Kagey
1,55772053
asked Apr 17 at 21:07
Peter KageyPeter Kagey
1,55772053
asked Apr 17 at 21:07
Peter KageyPeter Kagey
1,55772053
asked Apr 17 at 21:07
Peter KageyPeter Kagey
1,55772053
1,55772053
This question has an open bounty worth +100
reputation from Peter Kagey ending ending at 2019-04-28 21:42:17Z">in 4 days.
One or more of the answers is exemplary and worthy of an additional bounty.
Edderiofer’s answer was unexpectedly simple and nice!
This question has an open bounty worth +100
reputation from Peter Kagey ending ending at 2019-04-28 21:42:17Z">in 4 days.
One or more of the answers is exemplary and worthy of an additional bounty.
Edderiofer’s answer was unexpectedly simple and nice!
1
$begingroup$
This genre of logic puzzle is known originally as Netwalk.
$endgroup$
– Mike Earnest
Apr 17 at 21:27
$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
Apr 17 at 21:36
add a comment |
1
$begingroup$
This genre of logic puzzle is known originally as Netwalk.
$endgroup$
– Mike Earnest
Apr 17 at 21:27
$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
Apr 17 at 21:36
1
1
$begingroup$
This genre of logic puzzle is known originally as Netwalk.
$endgroup$
– Mike Earnest
Apr 17 at 21:27
$begingroup$
This genre of logic puzzle is known originally as Netwalk.
$endgroup$
– Mike Earnest
Apr 17 at 21:27
$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
Apr 17 at 21:36
$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
Apr 17 at 21:36
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
No, solutions are not unique. The four "T" shaped pieces in the grid below can be rotated into either of two configurations:
┏━━━┓
┗┓╻╻┃
╺┫┣┛┃
┏┫┣╸┃
╹╹┗━┛
┏━━━┓
┗┓╻╻┃
╺┻┻┛┃
┏┳┳╸┃
╹╹┗━┛
answered Apr 17 at 22:53
edderioferedderiofer
1961
$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
Apr 17 at 23:01
$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
Apr 17 at 23:05
$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
Apr 17 at 23:28
5
$begingroup$
Here is an interactive illustration of the solution: chiark.greenend.org.uk/~sgtatham/puzzles/js/…
$endgroup$
– Mike Earnest
Apr 17 at 23:30
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
);
);
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
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
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
No, solutions are not unique. The four "T" shaped pieces in the grid below can be rotated into either of two configurations:
┏━━━┓
┗┓╻╻┃
╺┫┣┛┃
┏┫┣╸┃
╹╹┗━┛
┏━━━┓
┗┓╻╻┃
╺┻┻┛┃
┏┳┳╸┃
╹╹┗━┛
answered Apr 17 at 22:53
edderioferedderiofer
1961
$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
Apr 17 at 23:01
$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
Apr 17 at 23:05
$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
Apr 17 at 23:28
5
$begingroup$
Here is an interactive illustration of the solution: chiark.greenend.org.uk/~sgtatham/puzzles/js/…
$endgroup$
– Mike Earnest
Apr 17 at 23:30
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:
┏━━━┓
┗┓╻╻┃
╺┫┣┛┃
┏┫┣╸┃
╹╹┗━┛
┏━━━┓
┗┓╻╻┃
╺┻┻┛┃
┏┳┳╸┃
╹╹┗━┛
answered Apr 17 at 22:53
edderioferedderiofer
1961
$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
Apr 17 at 23:01
$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
Apr 17 at 23:05
$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
Apr 17 at 23:28
5
$begingroup$
Here is an interactive illustration of the solution: chiark.greenend.org.uk/~sgtatham/puzzles/js/…
$endgroup$
– Mike Earnest
Apr 17 at 23:30
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:
┏━━━┓
┗┓╻╻┃
╺┫┣┛┃
┏┫┣╸┃
╹╹┗━┛
┏━━━┓
┗┓╻╻┃
╺┻┻┛┃
┏┳┳╸┃
╹╹┗━┛
answered Apr 17 at 22:53
edderioferedderiofer
1961
$endgroup$
No, solutions are not unique. The four "T" shaped pieces in the grid below can be rotated into either of two configurations:
┏━━━┓
┗┓╻╻┃
╺┫┣┛┃
┏┫┣╸┃
╹╹┗━┛
┏━━━┓
┗┓╻╻┃
╺┻┻┛┃
┏┳┳╸┃
╹╹┗━┛
answered Apr 17 at 22:53
edderioferedderiofer
1961
answered Apr 17 at 22:53
edderioferedderiofer
1961
answered Apr 17 at 22:53
edderioferedderiofer
1961
answered Apr 17 at 22:53
edderioferedderiofer
1961
1961
$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
Apr 17 at 23:01
$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
Apr 17 at 23:05
$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
Apr 17 at 23:28
5
$begingroup$
Here is an interactive illustration of the solution: chiark.greenend.org.uk/~sgtatham/puzzles/js/…
$endgroup$
– Mike Earnest
Apr 17 at 23:30
add a comment |
$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
Apr 17 at 23:01
$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
Apr 17 at 23:05
$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
Apr 17 at 23:28
5
$begingroup$
Here is an interactive illustration of the solution: chiark.greenend.org.uk/~sgtatham/puzzles/js/…
$endgroup$
– Mike Earnest
Apr 17 at 23:30
$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
Apr 17 at 23:01
$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
Apr 17 at 23:01
$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
Apr 17 at 23:05
$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
Apr 17 at 23:05
$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
Apr 17 at 23:28
$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
Apr 17 at 23:28
5
5
$begingroup$
Here is an interactive illustration of the solution: chiark.greenend.org.uk/~sgtatham/puzzles/js/…
$endgroup$
– Mike Earnest
Apr 17 at 23:30
$begingroup$
Here is an interactive illustration of the solution: chiark.greenend.org.uk/~sgtatham/puzzles/js/…
$endgroup$
– Mike Earnest
Apr 17 at 23:30
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
This genre of logic puzzle is known originally as Netwalk.
$endgroup$
– Mike Earnest
Apr 17 at 21:27
$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
Apr 17 at 21:36