Digital Mayhem

[Griffin]

Here's the best answer to Digital Mayhem I have so far:
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/

7 8 9
4 5 6
1 2 3

one
7 8 9
4 5 6
2 1 3

two
7 8 9
3 5 6
2 1 4

three
6 8 9
3 5 7
2 1 4

four
6 9 8
3 5 7
2 1 4

five
4 9 8
3 5 7
2 1 6

six
4 9 2
3 5 7
8 1 6

[Jester]

4 9 2
3 5 7
8 1 6

you can do it in 5 steps.

[Wonko the Sane]

I agree that the solution is

8 1 6
3 5 7
4 9 2

However, the answer is 6 as was first stated. I wrote a test program that randomly choses numbers that are in the wrong place and puts them in the correct position. Not only is the fewest possible number of moves 6, no matter how many ways you try, so long as you make a valid move (i.e. don't move something that is already in the correct place) it will ALWAYS take 6 moves. Period. This was true for 100,000 trials, so chances are there were several repetitions of most possible switch patterns. I'm not going to try to write the program so that it will only make each possible switch pattern once because I think this is proof enough and it isn't worth the time it takes. I refuse to spend more than 5 minutes working on a program to test a grey labyrinth puzzle.

~Wonko the Sane

As a quick afterthought. If anyone ELSE cares to make that modification, here's the source code. Go ahead and add it. Sorry that the comments are bad, I just threw them in a second ago so this was postable. Sorry if it screws up the spacing, it's okay on my end, but you never know once this gets posted. Okay, the spacing will be screwed up, sorry about that.

//Some test program or another
//Author: Wonko the Sane
//Compiler: Who cares? It doesn't use anything that isn't universal
//include files
#include <iostream.h>
#include <time.h>
#include <stdlib.h>

bool eqpads(int *, int *); //compare two arrays
int findpos(int *, int); //find a number's position

//main function
main()
{
time_t t;
srand((unsigned) time(&t)); //set random seed
//various functions, most are iterators are placeholders, etc
int moveto,postry,numtries,nummoves,leastmoves=5000,mostmoves = 0,i,j,temp;
int keypad[9] = {8,1,6,3,5,7,4,9,2}, pad[9]; //arrays (keypad is the key)
cout << "How many tries would you like to use? ";
cin >> numtries; //get number of tries
for (i = 0; i < numtries; ++i)
{
nummoves = 0; //no moves made this loop
for (j = 0; j < 9; ++j)
pad[j] = j + 1; //reset first array to {1,2,3,4,5,6,7,8,9}
while (!eqpad(keypad,pad)) //until they match
{
postry = rand() % 9; //check a position
if (pad[postry] == keypad[postry]) continue;
//if it's already in the right position, get a new pos
moveto = findpos(keypad,pad[postry]); //find where it goes
temp = pad[postry]; //next 3 lines switch the numbers
pad[postry] = pad[moveto];
pad[moveto] = temp;
++nummoves; //add another move
}
//change flags if more or less moves than last time were made
if (nummoves < leastmoves) leastmoves = nummoves;
if (nummoves > mostmoves) mostmoves = nummoves;
}
//output
cout << "Least number of switches: " << leastmoves << endl;
cout << "Most moves taken: " << mostmoves << endl;
return 0; //all okay, quit
}

//compare the arrays (are they equal?)
bool
eqpads(int *a, int *b)
{
for (int i = 0; i < 9; ++i)
if (a[i] != b[i]) return false; //false if any pair fails
return true; //otherwise true
}

//find a number's position
int
findpos(int *pad, int pos)
{
for (int i = 0; i < 9; ++i)
if (pad[i] == pos) return i; //if i is the position, return i
}

[This message has been edited by Wonko the Sane (edited 02-05-2000).]

[This message has been edited by Wonko the Sane (edited 02-05-2000).]

[Richk]

I got 6 too.......

7 8 9
3 5 6 1. swap 3 and 4
1 2 4

7 8 9
6 5 3 2. swap 3 and 6
1 2 4

6 8 9
7 5 3 3. swap 7 and 6
1 2 4

6 9 8
7 5 3 4. swap 8 and 9
1 2 4

6 2 8
7 5 3 5. swap 2 and 9
1 9 4

6 1 8
7 5 3 6. swap 1 and 2
2 9 4



[This message has been edited by Richk (edited 02-05-2000).]

[Ghost Post]

I think the solution is 6.

but if keys swapped must have a same side, is it possible to find a solution with less than 8 moves ?

I found this one:

789
456
123

789
456
213 (1)

789
256
413 (2)

789
256
431 (3)

798
256
431 (4)

978
256
431 (5)

278
956
431 (6)

276
958
431 (7)

276
951
438 (8)

[markagain]

Everyone seems to like that 5 in the center.
How about: 924,573,168 ? The puzzle didn't say diagonals had to be equal as well.

[markagain]

Oops! sorry. I checked the puzzle and it did include diagonals. Never mind.

[Wonko the Sane]

You would be right that it must take 8, but it says nothing about the keys' relationship to each other, it simply says move only 2 keys at a time. It's 6.

[Ghost Post]

I know it ...
It was only to have a bite more to eat ...
(and happy to have the same solution...)

[This message has been edited by DGA (edited 02-09-2000).]

[Matt_Banham]

Hi all,

I was browsing the web and stumbled upon this site which I have to say is wicked! Anyway, I solved the first part of this problem really quickly (i.e. I found the magic square very quickly). What I wanted to know is whether a general algorithm exists for solving this problem when the order of the square is n (i.e. for 4X4, 5X5, .... nXn sided square)? I ask this as I solved it by first finding the magic number (which I did by taking the average of the numbers from 1 to 9 or alternatively you could take the average of the lowest possible n-number sum and the highest possible n-number sum). Then I realised that four of the sums had to involve the middle number and so I knew this had to be the magic number divided by n (where n is 3 in this case) i.e. this number is 5. However, a.) I can't prove this last sentence in the general case (when the size of the square is n and b.) if I were to use Gaussian-Jordan elimination, then I will end up with a system of n-1 equations and will have to guess one of the terms by up to n amount of times!!!!!

If anyone knows an analytical solution to this problem then I would be grateful.

Also, I have a little problem that some of you might want to try:-

If you take a regular polygon with the number of sides = n, and you call the distance from the centre of the polygon to any of its corners r, can you prove that if the area of the polygon is equal to its circumference, then as n tends to infinity, r = 2?