10
$\begingroup$

The playing board for this puzzle is a short list of digits; there is one rule governing possible moves: The 1 may swap with a digit one place to the right; the 2 may swap with a digit two places to the right, and so on.

For example, in the list 1,3,7,2,6,5,4, you can swap 3 and 6, because the latter is 3 places to the right of 3:

┌─┐
┷ ▼
1,3,7,2,6,5,4     →     3,1,7,2,6,5,4

The only other legal moves from this position are to swap 1 and 3 (yielding 3,1,7,2,6,5,4) or to swap 2 and 5 (yielding 1,6,7,5,3,2,4):

  ┌─────┐
  ┷     ▼
1,3,7,2,6,5,4     →     1,6,7,2,3,5,4

      ┌───┐
      ┷   ▼
1,3,7,2,6,5,4     →     1,3,7,5,6,2,4

Here is a graph of all possible states reachable from 1,2,3:

123 → 213 → 312 → 321
       ↓     ↑
      231 → 132

(For lists of few digits, let's just omit the separating commas).

For the 24 states reachable from 1,2,3,4, the corresponding graph can be drawn. Do so, and make sure to avoid crossing lines!

Bonus points for symmetries, aesthetics, and for using ASCII-art (or Unicode text ).

If you need to omit the arrowheads, or the labels that distinguish the nodes, that's okay as long as the nodes are recognizable. Maybe mark the 1234 and 4321 nodes.

Is there a cycle (some sequence of two or more moves, after which the board state is the same in the beginning) for any permutation of the numbers 1,2,...,n, any n?

$\endgroup$
  • $\begingroup$ I think your second example should be 1372654 -> 1375624? $\endgroup$ – El-Guest May 21 at 18:57
  • 1
    $\begingroup$ El-Guest, yes! Thank you. $\endgroup$ – retzler May 21 at 21:24
  • $\begingroup$ 🛈 I have no proof that this graph is cycle-free, so I've asked on math.SE.—Someone is pondering a codegolf question based on this. $\endgroup$ – retzler May 26 at 2:22
13
$\begingroup$

The fact that flipping all sequences flips all the arrows makes for some very nice graph symmetries:

enter image description here

Anyone with way too much time on their hands is free to play with the length-5 version here.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I'd be surprised if the length-5 version could be drawn without crossing lines, though! $\endgroup$ – retzler May 25 at 0:12
  • $\begingroup$ Of course, but maybe it has lower crossing number than it appears... $\endgroup$ – AxiomaticSystem May 25 at 6:16
7
$\begingroup$

ASCII art rendering of completed graph:

 .------------------------------------.
 |                                    |
 |    .---------->4321<-----------.   |
 |    |                           |   |
 |    |                           |   |
 |  4312<--4132<--1432<--1234   2341  |
 |    ^      ^             |      ^   |
 |    |      |             v      |   |
 '->4213-->4231          2134-->2314  |
      ^                    |      |   |
      |                    v      v   |
 .->4123<----------------3124<--1324  |
 |    ^                    |          |
 |    |                    v          |
 |  1423<--3421<--3412<--3214---------'
 |    ^      ^      ^      |
 |    |      |      |      v
 |  2413-->2431     |    3241-->1243--.
 |    ^             |      |      |   |
 |    |             |      |      v   |
 '--2143<---------3142<----'    1342  |
      ^             |             |   |
      |             '-------------'   |
      |                               |
      '-------------------------------'

| improve this answer | |
$\endgroup$
  • $\begingroup$ Opinion poll: Should I add more vertical spacing? $\endgroup$ – Daniel Mathias May 21 at 23:08
  • $\begingroup$ Beautiful layout! One survey respondent says: "yes please for vertical | stems on up/down arrow heads." It would make their directions quicker to see. By the way, . periods and ` ' apostrophes can work well at corners (where \\ /slashes are at present). ASCII-affectionately $\endgroup$ – humn May 21 at 23:41
4
$\begingroup$

I think this works, without crossing lines:

planar graph v3

I’d imagine the answer to the second question is

No. Consider a string of length n, with elements i=1,...,n and positions j=1,...,n. Once element n is moved away from position n, it can never return to its initial position. This is because moving from position j, j != n, to position n requires an element of at most n-1. So we conclude that element i=n must stay in place in order for this sequence to work. This is then equivalent to creating a cycle from a string of length n-1, with elements i=1,...,n-1 and positions j=1,...,n-1. We see that, by similar logic to the above, element i=n-1 must also stay in place (moving from position j, j != n-1, to position n-1 requires an element of at most n-2). By induction it follows that the starting position can not be arrived at after any moves have been made.

| improve this answer | |
$\endgroup$
  • $\begingroup$ You are missing 2341 $\endgroup$ – Daniel Mathias May 21 at 22:49
  • $\begingroup$ Shoot, it was in my original diagram and forgot to transcribe — thanks $\endgroup$ – El-Guest May 21 at 23:22
3
$\begingroup$

Hint:

Explore paths from 3124 to 4213 first.

Here's my own answer using unicode line-drawing characters (without arrowheads) - different lines for swaps depending on their offset:

      ┌─────────────────────────────────────────2341
     2314═══1324                                  ║
      │      │                                    ║
     2134═══3124───────────────────────┐          ║
      │      ┃   ┏━━━━━━━━━━━━3241───3214━━┓      ║
      │      ┃   ┃              ║      ║   ┃   ▃▃▃║▃▃
      │      ┃  1243═══1342───3142───3412  ┃   ▉4321▉
      │      ┃   │┏━━━━━━━━━━━━━┛     ┃│   ┃   ▀▀▀│▀▀
    ▃▃│▃▃▃   ┃   │┃     ┏━━━━━━━━━━━━━┛│   ┃      │
    ▉1234▉   ┃  2143───2413───2431═══3421  ┃      │
    ▀▀║▀▀▀   ┃   ║      ║              ┃   ┃      │
      ║      ┗━━4123───1423━━━━━━━━━━━━┛   ┃      │
      ║          └───────────────────────4213═══4312
      ║                                    │      │
      ║                                  4231═══4132
     1432 ────────────────────────────────────────┘

Unicode within <pre> within a spoiler was a puzzle of its own. Kudos to Daniel!

| improve this answer | |
$\endgroup$
  • $\begingroup$ Wait, why does 3412 connect to 4213 directly? Doesn’t it need to connect 3412 > 3214 > 4213? $\endgroup$ – El-Guest May 22 at 0:06
  • $\begingroup$ El-Guest, you're right! Corrected. $\endgroup$ – retzler May 22 at 0:12
  • $\begingroup$ Thank you! Also, why does 3412 not connect to 2413? $\endgroup$ – El-Guest May 22 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.