A proof of concept that uses the Sliding Puzzle crate to search for words.

Cargo.toml

[package]
name = "sliding_puzzle_message"
version = "0.1.0"
authors = ["Chris Patuzzo <[email protected]>"]
edition = "2018"

[dependencies]
sliding_puzzle = "*"
pathfinding = "*"

main.rs

use sliding_puzzle::*;
use pathfinding::directed::astar::astar;

type Puzzle = SlidingPuzzle<&'static str>;

fn main() {
    let start_puzzle = Puzzle::new(&[
        &["",  "N", "A", "K"],
        &["E", "D", "T", "H"],
        &["E", "H", "A", "G"],
        &["U", "E", "X", "X"],
    ]).unwrap();

    if let Some(solution) = astar(&start_puzzle, successors, heuristic, success) {
        print_solution(solution);
    } else {
        println!("There is no solution.");
    }
}

fn successors(puzzle: &Puzzle) -> Vec<(Puzzle, u32)> {
    puzzle.moves().iter().map(|d| (puzzle.slide(d).unwrap(), 1)).collect()
}

fn heuristic(puzzle: &Puzzle) -> u32 {
    let max_position = 16 - "DENHAAG".len();

    (0..=max_position).map(|p| manhattan_distance(puzzle, p)).min().unwrap()
}

fn success(puzzle: &Puzzle) -> bool {
    puzzle.tiles().iter().flatten()
        .map(|s| if *s == "" { "<BLANK>" } else { *s })
        .collect::<String>()
        .contains("DENHAAG")
}

fn manhattan_distance(puzzle: &Puzzle, word_position: usize) -> u32 {
    let total = distance(puzzle, "D", word_position + 0)
              + distance(puzzle, "E", word_position + 1)
              + distance(puzzle, "N", word_position + 2)
              + distance(puzzle, "H", word_position + 3)
              + distance(puzzle, "A", word_position + 4)
              + distance(puzzle, "A", word_position + 5)
              + distance(puzzle, "G", word_position + 6);

    total
}

fn distance(puzzle: &Puzzle, letter1: &str, letter_position: usize) -> u32 {
    let mut distance = 999;

    let y1 = letter_position as i32 / 4;
    let x1 = letter_position as i32 % 4;

    for (y2, row) in puzzle.tiles().iter().enumerate() {
        for (x2, letter2) in row.iter().enumerate() {
            if letter1 == *letter2 {
                let x_delta = (x1 - x2 as i32).abs();
                let y_delta = (y1 - y2 as i32).abs();

                distance = std::cmp::min(distance, x_delta + y_delta);
            }
        }
    }

    distance as u32
}

fn print_solution((solution, cost): (Vec<Puzzle>, u32)) {
    println!("The shortest solution requires {} moves:", cost);

    print_puzzle(&solution[0]);

    for pair in solution.windows(2) {
        let (prev, next) = (&pair[0], &pair[1]);

        for direction in prev.moves() {
            if prev.slide(&direction).unwrap() == *next {
                println!("Slide {:?}:", direction);
                print_puzzle(next);
            }
        }
    }
}

fn print_puzzle(puzzle: &Puzzle) {
    for row in puzzle.tiles() {
        for letter in row {
            print!("{:2} ", letter);
        }
        println!();
    }
    println!();
}

output.txt

The shortest solution requires 19 moves:
   N  A  K
E  D  T  H
E  H  A  G
U  E  X  X

Slide Up:
E  N  A  K
   D  T  H
E  H  A  G
U  E  X  X

Slide Left:
E  N  A  K
D     T  H
E  H  A  G
U  E  X  X

Slide Down:
E     A  K
D  N  T  H
E  H  A  G
U  E  X  X

Slide Left:
E  A     K
D  N  T  H
E  H  A  G
U  E  X  X

Slide Up:
E  A  T  K
D  N     H
E  H  A  G
U  E  X  X

Slide Right:
E  A  T  K
D     N  H
E  H  A  G
U  E  X  X

Slide Down:
E     T  K
D  A  N  H
E  H  A  G
U  E  X  X

Slide Right:
   E  T  K
D  A  N  H
E  H  A  G
U  E  X  X

Slide Up:
D  E  T  K
   A  N  H
E  H  A  G
U  E  X  X

Slide Left:
D  E  T  K
A     N  H
E  H  A  G
U  E  X  X

Slide Up:
D  E  T  K
A  H  N  H
E     A  G
U  E  X  X

Slide Right:
D  E  T  K
A  H  N  H
   E  A  G
U  E  X  X

Slide Down:
D  E  T  K
   H  N  H
A  E  A  G
U  E  X  X

Slide Down:
   E  T  K
D  H  N  H
A  E  A  G
U  E  X  X

Slide Left:
E     T  K
D  H  N  H
A  E  A  G
U  E  X  X

Slide Up:
E  H  T  K
D     N  H
A  E  A  G
U  E  X  X

Slide Up:
E  H  T  K
D  E  N  H
A     A  G
U  E  X  X

Slide Left:
E  H  T  K
D  E  N  H
A  A     G
U  E  X  X

Slide Left:
E  H  T  K
D  E  N  H
A  A  G
U  E  X  X