Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun getNextStates(num: String): List<String> {
    val result = mutableListOf<String>()
    val digits = num.toCharArray()
    
    if (digits[0] != '9') {
        val newNum = digits.copyOf()
        newNum[0] = digits[0] + 1
        result.add(newNum.joinToString(""))
    }
    
    if (digits[3] != '1') {
        val newNum = digits.copyOf()
        newNum[3] = digits[3] - 1
        result.add(newNum.joinToString(""))
    }
    
    result.add("${digits[3]}${digits[0]}${digits[1]}${digits[2]}")
    result.add("${digits[1]}${digits[2]}${digits[3]}${digits[0]}")
    
    return result
}

fun findPath(start: String, end: String): List<String> {
    val queue = ArrayDeque<String>()
    val visited = mutableMapOf<String, String>()
    queue.add(start)
    visited[start] = ""
    
    while (queue.isNotEmpty()) {
        val current = queue.removeFirst()
        if (current == end) {
            val path = mutableListOf<String>()
            var num = end
            while (num != "") {
                path.add(num)
                num = visited[num]!!
            }
            return path.reversed()
        }
        
        for (next in getNextStates(current)) {
            if (next !in visited) {
                visited[next] = current
                queue.add(next)
            }
        }
    }
    return emptyList()
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))
    
    val start = reader.readLine()
    val end = reader.readLine()
    
    val path = findPath(start, end)
    for (num in path) {
        writer.write(num)
        writer.newLine()
    }
    
    reader.close()
    writer.close()
}