Challenge: Game of 15

• (2 Pages)
• 1
• 2

19 Replies - 1516 Views - Last Post: 17 May 2020 - 12:20 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=419143&amp;s=3bcd1286c6882bdf89dcd6c4d4fb5b64&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 DK3250

• Pythonian

Reputation: 571
• Posts: 1,836
• Joined: 27-December 13

Challenge: Game of 15

Posted 03 May 2020 - 08:07 AM

Challenge: Game of 15

I guess you all know the small game of 15; the numbers 1-15 in a 4x4 square, each number movable up/down/left/right.

From a random configuration the target is to move the numbers around creating a fixed pattern. The target pattern is simply the number ordered in ascending order; see picture below.

The challenge here is to build a program that can solve this puzzle in as few moves as possible.
The code should be ‘universal’, i.e. able to handle larger squares, e.g. 10x10.
Please note that not all starting configurations are possible; your code will need to handle such situations if you create own random numbers.

For the sake of competition, I include a picture (above) of a starting position; using this we can compare solutions.

In the challenge I’ll offer three list of numbers. Each list represents a starting position. The (visual) numbers 1-15 is represented by the values 0-14; furthermore, a value of 15 is added in the end, this represents the blank position. The numbers go into the square like reading: Left to right, top to bottom. The first list represents the position shown in the picture. Similar lists for 6 x 6 and 10 x 10.

The output is simply a list of numbers namely the sequence of numbers moved into the blank in order to establish the solution.

My algorithm solves the 4 x 4 sample in 116 moves; the code is pretty standard, placing one tile at a time while ignoring possible benefits from movement of adjacent tiles in trains – I’m sure this is not optimal, improvements pending. I would love to see a solution using AI or recursive code – or any other clever algorithm you can think of.

In the real world you can move two or more tiles simultaneously – this is not allowed here, only one tile can move at a time.

I have placed the challenge here in the Python Discussion Lounge, but the challenge is open to all languages.

Oh, just to be clear: This is a friendly competition, no prizes – only honor and glory!

Happy Coding.

Start data:
4 x 4: (Note the values are one lower than the visual output - 15 in this list represents the blank field)
```[13, 1, 4, 9, 2, 5, 10, 14, 6, 11, 8, 0, 7, 12, 3, 15]
```

My algorithm solves this in 116 moves

6 x 6:
```[19, 33, 25, 1, 16, 14, 24, 4, 21, 28, 6, 0, 10, 3, 8, 12, 17, 32, 11, 34, 31, 22, 7, 15, 2, 13, 26, 30, 27, 23, 29, 9, 20, 5, 18, 35]
```

My algorithm solves this in 526 moves

10 X 10:
```[81, 13, 89, 95, 10, 21, 91, 59, 63, 12, 54, 58, 17, 22, 7, 85, 67, 29, 33, 94, 87, 56, 23, 19, 66, 74, 42, 86, 47, 52, 26, 28, 98, 43, 84, 27, 30, 6, 80, 24, 11, 3, 48, 69, 8, 72, 5, 82, 93, 45, 77, 18, 90, 71, 9, 15, 64, 4, 32, 16, 79, 65, 70, 96, 78, 68, 88, 14, 73, 53, 51, 31, 61, 40, 46, 83, 92, 36, 2, 35, 41, 37, 1, 49, 57, 0, 62, 50, 75, 55, 44, 97, 20, 76, 38, 60, 39, 25, 34, 99]
```

My algorithm solves this in 2692 moves

Is This A Good Question/Topic? 1

Replies To: Challenge: Game of 15

#2 modi123_1

• Suitor #2

Reputation: 15686
• Posts: 62,833
• Joined: 12-June 08

Re: Challenge: Game of 15

Posted 03 May 2020 - 09:21 PM

Quite the brain tickler.

#3 albert003

Reputation: 38
• Posts: 853
• Joined: 15-December 14

Re: Challenge: Game of 15

Posted 04 May 2020 - 10:40 PM

When you say more, do you mean each move to switch location of a letter? For example...
a = 3
b = 2
c = 1
temp = 0

temp = c
c = a
a = temp
a,b,c
1,2,3

So would that be counted as 3 moves?

#4 DK3250

• Pythonian

Reputation: 571
• Posts: 1,836
• Joined: 27-December 13

Re: Challenge: Game of 15

Posted 05 May 2020 - 02:21 AM

Hi albert003,
There are not many letters in this challenge

Every time a numbered tile moves to the blank field counts as a move.
No exceptions.

Moving a tile just a few places may require many more moves as you have to (repeatedly) move the blank into correct position first.

#5 Ornstein

Reputation: 99
• Posts: 193
• Joined: 13-May 15

Re: Challenge: Game of 15

Posted 05 May 2020 - 03:38 AM

Out of interest, how long does it take your algorithm to find the solution with the least moves? I threw together the quickest and easiest recursive algorithm I could think of - and while it can solve the problem almost immediately, it takes quite a while to find the optimum. (I do have a few ideas for more sophisticated algorithms - which I may implement when/if I have time.)

#6 DK3250

• Pythonian

Reputation: 571
• Posts: 1,836
• Joined: 27-December 13

Re: Challenge: Game of 15

Posted 05 May 2020 - 06:31 AM

My solution is build around graphics showing all the moves - thus some waiting time and overhead.
I just tried to comment out the call to the drawing function (but leaving the calculations). Even with this remaining overhead, the calculation ends in "a blink of the eye" i.e. fraction of a second.
But please note: This is absolutely not the optimal solution - my algorithm is quite simple, placing one tile at a time in sequential order. For a 4x4 square I usually get solutions in 100-150 moves. When I try same start configuration manually, I never use more then 100 moves.

#7 jon.kiparsky

• Beginner

Reputation: 11937
• Posts: 20,243
• Joined: 19-March 11

Re: Challenge: Game of 15

Posted 06 May 2020 - 07:08 AM

sounds like a refactor is called for... you'd like to be able to compute the solution without drawing it...

thanks for the challenge, it's an interesting one... chewing on it...

#8 DK3250

• Pythonian

Reputation: 571
• Posts: 1,836
• Joined: 27-December 13

Re: Challenge: Game of 15

Posted 06 May 2020 - 01:52 PM

@jon.kiparsky:
Oh, I can comment out the call to the draw() function. This is easy, just one place in the code.

But the objects has some graphics in the __init__() that I did not comment out.
Likewise the basic pygame.init() and display declarations I left in place.
This is spread over many more lines and I didn't bother to find all and also there might be some dependencies leading to an error.

This whole thing was originally not meant as a challenge - I did it just to amuse myself.
When I realized the full complexity I could see a nice challenge emerge.

Anyway, as always I'll take your advise and look it over with refactoring in mind.

#9 albert003

Reputation: 38
• Posts: 853
• Joined: 15-December 14

Re: Challenge: Game of 15

Posted 06 May 2020 - 07:11 PM

This is what I came up with to solve it. I think I'm on the right track.

a = [14,2,5,10]
b = [3,6,11,15]
c = [7,12,9,1]
d = [8,13,4]

a.sort()
b.sort()
c.sort()
d.sort()
a.extend( b )
a.extend( c )
a.extend( d )
a.sort()
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

This post has been edited by albert003: 06 May 2020 - 07:13 PM

#10 modi123_1

• Suitor #2

Reputation: 15686
• Posts: 62,833
• Joined: 12-June 08

Re: Challenge: Game of 15

Posted 06 May 2020 - 08:40 PM

@albert - I am not certain if that follows the legitimate rules of the game. You would swap one square to an empty square, then have to move other numbers around to get the empty square into the place where you need to move a number.

#11 DK3250

• Pythonian

Reputation: 571
• Posts: 1,836
• Joined: 27-December 13

Re: Challenge: Game of 15

Posted 06 May 2020 - 11:18 PM

LOL albert003, - this is the most fantastic misunderstanding I've seen in long time. I literally burst into a great laud laugh... /> /> />

The challenge 'emulates' a real-world game. Apparently, you don't know this game. I hope this picture from amazon will help:
Note the prize: \$3.88 - maybe you should buy one for practice before start coding.

#12 modi123_1

• Suitor #2

Reputation: 15686
• Posts: 62,833
• Joined: 12-June 08

Re: Challenge: Game of 15

Posted 07 May 2020 - 12:03 AM

Bro.. snap.

#13 albert003

Reputation: 38
• Posts: 853
• Joined: 15-December 14

Re: Challenge: Game of 15

Posted 07 May 2020 - 08:11 AM

Ooops I goofed I didn't think of it that way and Ill try again. I honestly didn't read the instructions carefully and will try it again.

#14 DK3250

• Pythonian

Reputation: 571
• Posts: 1,836
• Joined: 27-December 13

Re: Challenge: Game of 15

Posted 08 May 2020 - 03:00 AM

Dear all,

If you have tried to solve this, you have probably encountered some extra difficult start configurations (depending on your algorithm).

Your code should be able to handle this input (4x4 square):
```[0, 1, 3, 2, 8, 12, 9, 6, 7, 5, 14, 13, 4, 10, 11, 15]
```
In my view this is a little more difficult than the input set given in post #1. But again, it depends on your algorithm.

Happy coding.

#15 albert003

Reputation: 38
• Posts: 853
• Joined: 15-December 14

Re: Challenge: Game of 15

Posted 16 May 2020 - 11:20 PM

I'm still working on the challenge. I've never played with that before so I made squares on pieces of paper and I am writing down how I would move the boxes to put everything in order.