/Klotski

In this problem, you will solve a KLOTSKI number puzzle.

Primary LanguageJava

The Game

This project is a contribution for CodinGame, a solo game using the Game Engine Toolkit of CodinGame.

In this problem, you will solve a KLOTSKI number puzzle.

Rules

To win, you need to fully arrange the 4 x 4 board in the correct order by sliding the pieces.

The correct order:

Initialization Input

To input a 2D array A there will be 4 lines of input, each line consists of 4 integers.

The cth integer in the rth line, Ar,c, ranges from 0 to 15. A is guaranteed to include all integers from 0 to 15.

Game Turn

There are no inputs for a Game Turn.

In each turn, you must swap the number 0 with any adjacent number (in the up, down, left, right direction of number 0 without exceeding the border) in array A, or in other words, slide the block beside the empty spot.

Output

Each turn you should output two integers r and c, indicating you are sliding the block in the rth row and the cth column, in short (r,c).

While in the correct order, number 1 is at (0,0) and number 7 is at (1, 2).

Wrong Output

  • r<0 or r>3 or c<0 or c>3

  • Among existing Ar+1,c, Ar-1,c, Ar,c+1, Ar,c-1 there is no number 0.

Example

Input Output 
1 2 3 4
5 6 8 11
9 10 7 12
13 14 15 0

2 3
1 3
1 2
2 2
2 3
3 3

Expert Rules

Small reminder: there will be cases requiring hundreds of turns to solve, and after each turn A will change and your program should keep track of that :D

The common strat includes 3 steps:

  • put number 1 to 4 in their correct locations and never deal with the first line ever again.

  • Similarly, put number 5 to 8 in their correct locations and never deal with the second line ever again.

  • Arrange the last two lines (which is a bit hard).

Victory Conditions

  • After a game turn, the 2D array A equals to the following:
{
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12},
    {13, 14, 15, 0}
}
  • There is almost no need to minimize the total steps

Loss Conditions

  • Exceed the turn limit of 500.
  • Wrong input.

Constraints

$0 \leq $ Ar,c $ \leq 15$ for r ∈ [0, 3] and c ∈ [0, 3]