Find a specific path on an n x n grid [duplicate]












3












$begingroup$



This question already has an answer here:




  • Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph

    1 answer



  • Can the rook pass every square just once?

    1 answer




Given a puzzle of the following form:



Find a path between the top left corner to the bottom right corner, visiting each spot (.) exactly once. You can only move horizontally or vertically.



x  .  .



.  .  .



.  .  x


For a 3 x 3 grid, this yields two solutions:



x--.--.

      |

.--.--.

|

.--.--x



x  .--.

|  |  |

.  .  .

|  |  |

.--.  x


There are mul olutions for a 5x5 grid, 7x7, and so on.



But for a 2x2, 4x4, 6x6, and higher n x n (where n is even), this does not seem to yield any solution.



How would you prove that this is the case? That there is no solution for n x n grids where n is even? (Is this even true?)






mathematics combinatorics







share|improve this question









New contributor




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







$endgroup$



marked as duplicate by Rand al'Thor, Alconja, deep thought, Rupert Morrish, Glorfindel yesterday


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


















  • $begingroup$
    This feels like a duplicate question.
    $endgroup$
    – Hugh
    yesterday










  • $begingroup$
    Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
    $endgroup$
    – Danny Yaroslavski
    yesterday








  • 1




    $begingroup$
    More specific duplicate might be Can the rook pass every square just once?
    $endgroup$
    – deep thought
    yesterday


















3












$begingroup$



This question already has an answer here:




  • Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph

    1 answer



  • Can the rook pass every square just once?

    1 answer




Given a puzzle of the following form:



Find a path between the top left corner to the bottom right corner, visiting each spot (.) exactly once. You can only move horizontally or vertically.



x  .  .



.  .  .



.  .  x


For a 3 x 3 grid, this yields two solutions:



x--.--.

      |

.--.--.

|

.--.--x



x  .--.

|  |  |

.  .  .

|  |  |

.--.  x


There are mul olutions for a 5x5 grid, 7x7, and so on.



But for a 2x2, 4x4, 6x6, and higher n x n (where n is even), this does not seem to yield any solution.



How would you prove that this is the case? That there is no solution for n x n grids where n is even? (Is this even true?)






mathematics combinatorics







share|improve this question









New contributor




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







$endgroup$



marked as duplicate by Rand al'Thor, Alconja, deep thought, Rupert Morrish, Glorfindel yesterday


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


















  • $begingroup$
    This feels like a duplicate question.
    $endgroup$
    – Hugh
    yesterday










  • $begingroup$
    Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
    $endgroup$
    – Danny Yaroslavski
    yesterday








  • 1




    $begingroup$
    More specific duplicate might be Can the rook pass every square just once?
    $endgroup$
    – deep thought
    yesterday
















3












3








3





$begingroup$



This question already has an answer here:




  • Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph

    1 answer



  • Can the rook pass every square just once?

    1 answer




Given a puzzle of the following form:



Find a path between the top left corner to the bottom right corner, visiting each spot (.) exactly once. You can only move horizontally or vertically.



x  .  .



.  .  .



.  .  x


For a 3 x 3 grid, this yields two solutions:



x--.--.

      |

.--.--.

|

.--.--x



x  .--.

|  |  |

.  .  .

|  |  |

.--.  x


There are mul olutions for a 5x5 grid, 7x7, and so on.



But for a 2x2, 4x4, 6x6, and higher n x n (where n is even), this does not seem to yield any solution.



How would you prove that this is the case? That there is no solution for n x n grids where n is even? (Is this even true?)






mathematics combinatorics







share|improve this question









New contributor




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







$endgroup$





This question already has an answer here:




  • Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph

    1 answer



  • Can the rook pass every square just once?

    1 answer




Given a puzzle of the following form:



Find a path between the top left corner to the bottom right corner, visiting each spot (.) exactly once. You can only move horizontally or vertically.



x  .  .



.  .  .



.  .  x


For a 3 x 3 grid, this yields two solutions:



x--.--.

      |

.--.--.

|

.--.--x



x  .--.

|  |  |

.  .  .

|  |  |

.--.  x


There are mul olutions for a 5x5 grid, 7x7, and so on.



But for a 2x2, 4x4, 6x6, and higher n x n (where n is even), this does not seem to yield any solution.



How would you prove that this is the case? That there is no solution for n x n grids where n is even? (Is this even true?)





This question already has an answer here:




  • Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph

    1 answer



  • Can the rook pass every square just once?

    1 answer







mathematics combinatorics




mathematics combinatorics






share|improve this question









New contributor




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











share|improve this question









New contributor




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









share|improve this question




share|improve this question








edited yesterday









JonMark Perry

18.5k63888




18.5k63888






New contributor




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









asked yesterday









Danny YaroslavskiDanny Yaroslavski

1183




1183




New contributor




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





New contributor





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






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




marked as duplicate by Rand al'Thor, Alconja, deep thought, Rupert Morrish, Glorfindel yesterday


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.









marked as duplicate by Rand al'Thor, Alconja, deep thought, Rupert Morrish, Glorfindel yesterday


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.














  • $begingroup$
    This feels like a duplicate question.
    $endgroup$
    – Hugh
    yesterday










  • $begingroup$
    Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
    $endgroup$
    – Danny Yaroslavski
    yesterday








  • 1




    $begingroup$
    More specific duplicate might be Can the rook pass every square just once?
    $endgroup$
    – deep thought
    yesterday




















  • $begingroup$
    This feels like a duplicate question.
    $endgroup$
    – Hugh
    yesterday










  • $begingroup$
    Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
    $endgroup$
    – Danny Yaroslavski
    yesterday








  • 1




    $begingroup$
    More specific duplicate might be Can the rook pass every square just once?
    $endgroup$
    – deep thought
    yesterday


















$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
yesterday




$begingroup$
This feels like a duplicate question.
$endgroup$
– Hugh
yesterday












$begingroup$
Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
$endgroup$
– Danny Yaroslavski
yesterday






$begingroup$
Upon further investigation this question is a subquestion of : puzzling.stackexchange.com/questions/6100/…, however @JonMark Perry has a good explanation in his answer below for why the checkerboard test works.
$endgroup$
– Danny Yaroslavski
yesterday






1




1




$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
yesterday






$begingroup$
More specific duplicate might be Can the rook pass every square just once?
$endgroup$
– deep thought
yesterday












1 Answer
1






active

oldest

votes


















5












$begingroup$


Imagine the grid as a chessboard. Then for a $2ktimes2k$ board, the two corners are the same colour, say white. Any path must travel $WBWBdots WBW$, which is always an odd number of moves, however we need to travel through an even number of squares, so the task is impossible.







share|improve this answer









$endgroup$













  • $begingroup$
    Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    well the simplest tree graphs disprove that
    $endgroup$
    – JonMark Perry
    yesterday












  • $begingroup$
    Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
    $endgroup$
    – JonMark Perry
    yesterday


















1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









5












$begingroup$


Imagine the grid as a chessboard. Then for a $2ktimes2k$ board, the two corners are the same colour, say white. Any path must travel $WBWBdots WBW$, which is always an odd number of moves, however we need to travel through an even number of squares, so the task is impossible.







share|improve this answer









$endgroup$













  • $begingroup$
    Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    well the simplest tree graphs disprove that
    $endgroup$
    – JonMark Perry
    yesterday












  • $begingroup$
    Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
    $endgroup$
    – JonMark Perry
    yesterday
















5












$begingroup$


Imagine the grid as a chessboard. Then for a $2ktimes2k$ board, the two corners are the same colour, say white. Any path must travel $WBWBdots WBW$, which is always an odd number of moves, however we need to travel through an even number of squares, so the task is impossible.







share|improve this answer









$endgroup$













  • $begingroup$
    Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    well the simplest tree graphs disprove that
    $endgroup$
    – JonMark Perry
    yesterday












  • $begingroup$
    Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
    $endgroup$
    – JonMark Perry
    yesterday














5












5








5





$begingroup$


Imagine the grid as a chessboard. Then for a $2ktimes2k$ board, the two corners are the same colour, say white. Any path must travel $WBWBdots WBW$, which is always an odd number of moves, however we need to travel through an even number of squares, so the task is impossible.







share|improve this answer









$endgroup$




Imagine the grid as a chessboard. Then for a $2ktimes2k$ board, the two corners are the same colour, say white. Any path must travel $WBWBdots WBW$, which is always an odd number of moves, however we need to travel through an even number of squares, so the task is impossible.








share|improve this answer












share|improve this answer



share|improve this answer










answered yesterday









JonMark PerryJonMark Perry

18.5k63888




18.5k63888












  • $begingroup$
    Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    well the simplest tree graphs disprove that
    $endgroup$
    – JonMark Perry
    yesterday












  • $begingroup$
    Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
    $endgroup$
    – JonMark Perry
    yesterday


















  • $begingroup$
    Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    well the simplest tree graphs disprove that
    $endgroup$
    – JonMark Perry
    yesterday












  • $begingroup$
    Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
    $endgroup$
    – Danny Yaroslavski
    yesterday












  • $begingroup$
    I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
    $endgroup$
    – JonMark Perry
    yesterday
















$begingroup$
Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
$endgroup$
– Danny Yaroslavski
yesterday






$begingroup$
Is there a way to extend this idea to non-grid graphs? A general heuristic that relates graph-coloring to the non-existence of a Hamiltonian path? (this is knowing that determining the existence of a Hamiltonian path is NP-Complete)
$endgroup$
– Danny Yaroslavski
yesterday














$begingroup$
I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
$endgroup$
– Danny Yaroslavski
yesterday






$begingroup$
I have a feeling something along the lines of: if a graph can be 2-colored and the number of vertices of one color is equal to the number of vertices of the other color -> there cannot exist a Hamiltonian path. Does that sound about right?
$endgroup$
– Danny Yaroslavski
yesterday














$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
yesterday






$begingroup$
well the simplest tree graphs disprove that
$endgroup$
– JonMark Perry
yesterday














$begingroup$
Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
$endgroup$
– Danny Yaroslavski
yesterday






$begingroup$
Right. Heck a simple line disproves that. Then what is it about a grid/lattice shape that makes this checkerboard heuristic work? Is there a characteristic that you can extend to more general graphs?
$endgroup$
– Danny Yaroslavski
yesterday














$begingroup$
I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
$endgroup$
– JonMark Perry
yesterday




$begingroup$
I think you might need another constraint in that you might wish to specify required start and end points to check for the existence of an HP between them.
$endgroup$
– JonMark Perry
yesterday



-

Popular posts from this blog

Olav Thon

Image
Olav Thon Fødd 29. juni 1923 Ål Yrke forretningsdrivande Olav Thon på Commons Olav Thon (fødd 29. juni 1923) er ein norsk, stort sett sjølvlært forretningsmann, fødd i Ål i Hallingdal, som har gjort store pengar på særleg kjøp, bygging og utvikling av fast eigedom, mellom anna kjøpesentre, hotell og restaurantar, i både Noreg og somme andre land. Han vart Ridder av 1. klasse av St. Olavs Orden i 2003, og er som ivrig friluftsmann æresmedlem i Den Norske Turistforening etter å ha ytt store økonomiske bidrag til foreininga sine hytter og ruter i fjellet. Han er kjend for alltid å gå med ei karakteristisk strikkelue. Olav Thon i samtale med Trond Helleland på sentralbanksjefens årstale i februar 2016 I ung alder reiste Olav Thon til Newcastle for å lære seg engelsk, og han var seinare ei tid i Sveits, der han gjorde forretningar i import og eksport. Deretter tok han til å kjøpe faste eigedomar i Noreg med stor økonomisk suksess, verksemda voks snøgt og v...
Read more

Waikiki

Image
Denne artikkelen kan ha godt av ein språkvask , som reinskar opp målføringa og/eller innfører same språkstilen overalt. Denne artikkelen kan ha godt av ei opprydding for å nå ein høgare standard og/eller for å verta i tråd med standardoppsettet. Sjå korleis du redigerer ei side og stilmanualen for hjelp. Waikiki Land   USA Stat Hawaii Stad Honolulu Wikimedia Commons: Waikiki Utsyn over Waikiki Waikīkī er ein bydel i Honolulu, sør på øya Oahu, som er ei av Hawaii-øyane. Waikīkīstranda er ein av dei meste berømte strendene i verda. Waikīkī strekkjer seg langs stillehavskysten og har ei rekkje velrenommerte hotell. Bydelen er Hawaii-turismens høyborg. På Waikīkī Beach står ei statue av den lokale sportsstjerna Duka Kahanamoku. Kjelder | Denne artikkelen bygger på «Waikiki» frå Wikipedia på bokmål, den 4. november 2018. Denne artikkelen manglar kjelder eller referansar . Hjelp Wikipedia med å finna truverdige kjelder...
Read more

Tårekanal

Image
Tåreapparatet ( a ) Tårekjertel ( b ) Øvre tårepunkt ( c ) Øvre tårekanalikkel ( d ) Tåresekk ( e ) Nedre tårepunkt ( f ) Nedre tårekanalikkel ( g ) Tårekanal Tårekanalen eller nase-tårekanalen (av latin ductus nasolacrimalis ) er ein ductus som frakter overflødige tårer frå tåresekken til nasehola. Opninga inn mot nedre nasegang er delvis tildekt av ei ufullstendig slimhinnefold kalla Hasners ventil. Overflødige tårer strøymer gjennom tårekanalen og trekker inn i nedre nasegang. Dette er grunnen til at ein kan få rennande nase når ein gret, og at ein somme gonger kan kjenne saltsmaken av tårer i munnen. Både tårekanalen og tåresekken er tekt med fleirlaga sylinderepitel som inneheld slimproduserande begerceller, og er begge omgjevne av bindevev. Dakryostenose (tårekanalstenose) er ei innsnevring av tårekanalen som fører til epifora, ei overflod av tårer. Medfødd dakryostenose kan føra til cystisk utviding av tårekanalen ved at det dannast ein dakryocystocele. Personar m...
Read more