Rena and Minami International Programming Competition |Paiza Online Hackathon 5

[ Rena and Minami International Programming Competition ]
Problem

If you thought the other questions were too easy, here’s something for you…
It’s the International Programming Battle, launched at the same time as POH5! Go head-to-head with Rena and Minami!

The game proceeds by moving any tiles to adjacent empty space. For instance, the game may proceed as follows:

Write a program that slides the tiles and completes the play board. However, you don't need to solve the problem in minimum moves.

Hint
The board can be completed by repeatedly moving the tiles in a random fashion.
For instance, if you want to move tile 1 to the upper left corner, continue randomly moving tiles until tile 1 reaches that position. If you want to move tile 2 to the right of tile 1, continue randomly moving tiles until tile 2 reaches that position. When taking this step, tile 1 should be left untouched while the others are moved.
Also note that, when randomly moving tiles on a given grid, the probability of moving a certain tile to a specific location within 10,000 moves is over 99%.

Write a program that slides the tiles and completes the play board.

Expected input:

The initial state of the play board is given in the following format as input:

t_1 t_2 t_3 t_4
t_5 t_6 t_7 t_8
t_9 t_10 t_11 t_12
t_13 t_14 t_15 t_16

The grid is labeled starting from the upper left cell (t_1) and ending with the lower right cell (t_16).

Constraints

The input values have the following constraints for all test cases.

Input constraints:
Cell t_i (1 ≦ i ≦ 16) meet the following constraints.
If the tile exists, it must be a number between 1 and 15. If the tile does not exist, it is marked with an asterisk (*).
Each item for t_i should be different.
The given play board can always be solved.
A solved play board will never be given as input.
Output constraints:
Tiles that cannot physically be slid (tiles with no empty spaces around them) cannot be slid.
The puzzle must be completed within 1,000,000 mvoes.

Expected output:

Output the numbers of each sliding tile in each line.
At the end of moving, the board must be completed.
Please add a new line at the end, and do not include any unnecessary characters or empty lines.

Example 1(input): 1 2 3 4
5 6 7 8
9 10 * 11
13 14 15 12

Example 1(output): 11
12

Example 2(input): 2 3 4 *
1 5 6 7
10 11 12 8
9 13 14 15

Example 2(output): 4
3
2
1
5
6
7
8
12
11
10
9
13
14
15

Answer

Please enter and submit the code that solves the problem above using the text box below.
You can use the following languages: Java, PHP, Ruby, Perl, Python, C, C#, and C++.

To find out about methods for reading values from standard input, please refer to the sample codes shown in the pages below:

Select language

Code execution result

Nickname (Required)	You can use letters and numbers. This nickname may be displayed on our site when we publish your codes as sample solutions, or when we announce the prize winners.
email (Required)	Your registered e-mail address will not be used outside of Paiza Online Hackathon. Once you submit your code, we will e-mail your results page.
Country to represent （Required）

Workflow

		Write code
		Compile and test the code
		Submit
		Then, we will show your score!

*Submitted code with nickname is to be open to other challenger.

Event schedule, Prize

Schedule

Submission Period: April 14 (Thu) - May 19 (Thu)
Examination period: May 20 (Wed) - May 26 (Thu)
Result announcement: May 27 (Wed)

Prize

By lot from among the participants, 6 sets of Momoya of goods towards 3 person, and "Intel Edison Kit for Arduino" towards one person. Only Japanese residents are eligible for the prize.

Events Terms

　In this campaign, with problems open to the public, you can take the test without membership registration. However, when submitting, it is assumed that you are familiar with the following important points.
*Important Points*
(1) Membership registration is not required, but it is necessary to register an email address. However, this company will not use this email address for any other purposes outside of this campaign.
(2) Existing members may also take the test in this campaign, but as this has no effect on personal skill ranks, please note this in advance.
(3) The copyright for submitted code belongs to the examinee, but this company will make that code open to the public on our website, SNS, etc., and may use it freely. This complies fully with the rules of use, in Article 5, section 2.
(4) As there may the case that codes submitted may not be completely preserved, they should be backed personally based on the needs of the examinee, and we ask for the appropriate support.

Too Much Turmoil Over My Childhood and My Affianced One

[POH vol.5] Too Much Turmoil Over My Childhood and My Affianced One.

Country Summary

Country	Submit Count	Avg Step	Avg Time
日本	2844 Submit	1531.59 Step	1.15 Sec
United States	112 Submit	176.05 Step	1.32 Sec
China	163 Submit	78.09 Step	0.68 Sec
Korea	1 Submit	- Step	- Sec
Spain	7 Submit	- Step	- Sec
Indonesia	80 Submit	348.8 Step	0.17 Sec
Taiwan	60 Submit	58.86 Step	0.06 Sec
Netherlands	2 Submit	112.8 Step	0.08 Sec
Canada	22 Submit	2590.17 Step	0.26 Sec
Sweden	1 Submit	4260.4 Step	0.11 Sec
Singapore	2 Submit	- Step	- Sec
Philippines	27 Submit	112.8 Step	0.23 Sec
Hong Kong	231 Submit	60.72 Step	0.01 Sec
Estonia	2 Submit	- Step	- Sec
other	7 Submit	- Step	- Sec

（2015/05/20Sum Update）

Ranking

Ranking Description

Nickname	Avg Step	Avg Time	Programming Language
Place uwi	39.6 Step	2.39 Sec	Java
Place IL_k	39.6 Step	0.03 Sec	C#
Place hackByMikeCAT	39.6 Step	0.01 Sec	C
Place hiromi_ayase	39.6 Step	0.59 Sec	C#
Place lassie	39.6 Step	0.09 Sec	Ruby
Place carrotflakes	39.6 Step	0.01 Sec	C++
Place hogeover30	40.4 Step	0.85 Sec	C++
Place orisano	41.6 Step	0.85 Sec	C++
Place nus	41.6 Step	0.89 Sec	C++
Place aspen	42.8 Step	0.49 Sec	C#
Place holydc	43.2 Step	0.03 Sec	C++
Place y_mazun	43.2 Step	0.75 Sec	C++
Place siman	43.6 Step	0.9 Sec	C++
Place qaolwsik	44.4 Step	0.32 Sec	C#
Place romain_li	46.0 Step	1.27 Sec	Python2
Place r	46.0 Step	0.7 Sec	C++
Place iwata0303	46.0 Step	3.55 Sec	Python2
Place iwashi31	46.4 Step	0.19 Sec	C++
Place mayoko	46.4 Step	0.2 Sec	C++
Place y_uti	46.4 Step	0.04 Sec	PHP
Place ReiFNSK	46.8 Step	1.47 Sec	Java
Place ark214	46.8 Step	0.09 Sec	C#
Place quarter_moon	47.6 Step	1.26 Sec	Ruby
Place neko	48.4 Step	0.15 Sec	C++
Place ha2ne2	48.8 Step	1.81 Sec	Ruby
Place kurapan	48.8 Step	1.13 Sec	Python2
Place tekitouk	48.8 Step	0.38 Sec	C++
Place roiti46	49.6 Step	1.03 Sec	C++
Place heinetsu	49.6 Step	0.49 Sec	C#
Place DoG	50.0 Step	7.64 Sec	Ruby
Place kazekaoru	50.4 Step	0.2 Sec	C++
Place homulerdora	50.8 Step	0.92 Sec	Haskell(Beta)
Place Leonardone	51.6 Step	0.02 Sec	C++
Place MikeCAT	52.0 Step	0.56 Sec	C++
Place n_toriq	52.0 Step	0.42 Sec	C#
Place cozziekuns	52.8 Step	2.14 Sec	Ruby
Place chitose	53.2 Step	0.2 Sec	C++
Place chexq09	53.6 Step	0.67 Sec	C++
Place mugenen	54.4 Step	0.72 Sec	Python2
Place cozziechang	55.6 Step	1.17 Sec	Ruby
Place pkc	58.4 Step	0.85 Sec	C
Place cozykuns	58.4 Step	1.56 Sec	Ruby
Place Gasu	58.8 Step	2.33 Sec	Perl
Place Bruce	59.2 Step	0.01 Sec	C
Place hejob	61.2 Step	0.37 Sec	C++
Place Kay	64.0 Step	0.01 Sec	C++
Place 448	64.8 Step	0.22 Sec	C++
Place haraduka	66.0 Step	0.73 Sec	C++
Place kos	66.8 Step	1.33 Sec	C#
Place iicafiaxus	68.8 Step	0.54 Sec	D(Beta)