Puzznic
Description
Puzznic is a famous logic game where the goal is to make all puzzle pieces disappear. The game presents the player with a playing area consisting of square cells. Each cell is either a wall, an empty cell, or a puzzle piece. Puzzle pieces have types, which are shared by at least one other piece. When two or more pieces of the same type touch, they vanish. A puzzle piece is considered to be falling if the cell below it is either an empty cell or another puzzle piece that is also falling. Falling pieces are not considered to be touching anything. Puzzle pieces can be moved horizontally across the playing area.
The game works in cycles of three steps:
On the first step, the player can either do nothing or choose a puzzle piece and move it one position to the left or right. The piece can only be moved if it is not falling, the destination cell is empty, and there are no adjacent matching pieces which are not falling.
On the second step, the game determines which pieces to vanish. All groups of adjacent matching pieces disappear.
On the third step, all falling pieces are shifted down by one position.
Given the initial configuration of the playing area, your task is to find a sequence of moves that will make all the puzzle pieces disappear.
The input contains the description of the playing area. Each character describes the type of the cell. The character "#" denotes a wall. A single digit from 1 to 9 determines the type of a puzzle piece. The character "." denotes an empty cell.
Both the width and height of the playing area do not exceed $7$. All lines have equal width. The playing area contains at least one puzzle piece. Each line contains at least one non-empty cell. It is guaranteed that initially no puzzle piece is falling and there are no adjacent matching pieces. The playing area is closed, meaning there is no path consisting of steps in the four cardinal directions which goes from the exterior of the playing area to any of the puzzle pieces.
Output the sequence of user actions necessary to achieve the goal of the game. If you choose to pass the current move, output "-". Otherwise, output three characters separated by spaces: the direction ('L" is for left and 'R" is for right), the row, and the column of the piece to move. The first row is the topmost and the first column is the leftmost.
It is guaranteed that at least one solution exists. If there are multiple solutions, you may output any one of them. The number of moves should not exceed $1000$.
Input
The input contains the description of the playing area. Each character describes the type of the cell. The character "#" denotes a wall. A single digit from 1 to 9 determines the type of a puzzle piece. The character "." denotes an empty cell.
Both the width and height of the playing area do not exceed $7$. All lines have equal width. The playing area contains at least one puzzle piece. Each line contains at least one non-empty cell. It is guaranteed that initially no puzzle piece is falling and there are no adjacent matching pieces. The playing area is closed, meaning there is no path consisting of steps in the four cardinal directions which goes from the exterior of the playing area to any of the puzzle pieces.
Output
Output the sequence of user actions necessary to achieve the goal of the game. If you choose to pass the current move, output "-". Otherwise, output three characters separated by spaces: the direction ('L" is for left and 'R" is for right), the row, and the column of the piece to move. The first row is the topmost and the first column is the leftmost.
It is guaranteed that at least one solution exists. If there are multiple solutions, you may output any one of them. The number of moves should not exceed $1000$.
#####
#.41#
#432#
#321#
#####
######
#1.###
##.###
#1..1#
##.###
######
#####
#.1.#
#.#.#
#1.1#
#####
####
#.1#
#.##
#..#
#..#
##1#
####
L 2 3
L 2 4
L 3 3
L 3 3
L 3 4
R 4 2
R 2 2
-
-
L 4 5
R 4 2
L 2 3
L 4 4
L 2 3
-
-
R 5 2