Algorithm to insert words into a 2D Matrix

About
The following algorithm can be used to put some selected words to a matrix without a specific order. Initially the matrix will be empty. Once we put the selected words, we put random alphabets to the empty cells. So by doing this we can hide these words in random position. The same can be used to generate the Find Word puzzles

There are total eight possible directions possible, they are NORTH(0), NORTH-EAST(1), EAST(2), SOUTH-EAST(3), SOUTH(4), SOUTH-WEST(5), WEST(6), NORTH-WEST(7)

The algorithm is given below

global matrix[10, 10]

procedure insert_word_to_matrix(word)
  directions <- [0, 1, 2, 3, 4, 5, 6, 7]
  completed <- NO
  tries <- 5
  while not completed
    if tries reached 0
      exit this while loop
    (x_position, y_position) <- Locate an empty box randomly
    shuffle(directions)
    next_direction <- 0
    while next_direction is less than 8
      (x_increment, y_increment) <- get_direction_increment(directions[next_direction])
      if possible_to_insert((x_position, y_position), (x_increment, y_increment), word)
        do_insert_word((x_position, y_position), (x_increment, y_increment), word)
        completed <- YES
        exit this while loop
      next_direction <- next_direction + 1
    tries <- tries - 1
  if completed
    return YES
  return NO

procedure get_direction_increment(direction)
  if direction = 0 return (-1, 0)  
  else if direction = 1 return (-1, 1)
  else if direction = 2 return (0, 1)
  else if direction = 3 return (1, 1)
  else if direction = 4 return (1, 0)
  else if direction = 5 return (1, -1)
  else if direction = 6 return (0, -1)
  else if direction = 7 return (-1, -1)

procedure possible_to_insert((x_position, y_position), (x_increment, y_increment), word)
  word_length_counter <- 1
  while word_length_counter is less than length(word)
    (next_x_position, next_y_position) <- (x_position + x_increment, y_position + y_increment)
    if (next_x_position, y_position) is outside the matrix
      return NO
    else if matrix[next_x_position, next_y_position] have no value
      word_length_counter <- word_length_counter + 1
      continue while loop
    else if matrix[next_x_position, next_y_position] is not equal to word[word_length_counter]
      return NO
    word_length_counter <- word_length_counter + 1
    continue this while loop
 return YES

procedure do_insert_word((x_position, y_position), (x_increment, y_increment), word)
  word_length_counter <- 1
  matrix[x_position, y_position] <- word[0]
  while word_length_counter is less than length(word)
    (next_x_position, next_y_position) <- (x_position + x_increment, y_position + y_increment)
    matrix[next_x_position, next_y_position] <- word[word_length_counter]
    word_length_counter <- word_length_counter + 1
    continue this while loop

Note: Here we try to fit the word by taking each direction from the list for a selected position. This is some times time consuming. So we can try another method. First find the best fit directions (at least three) for the selected word using the matrix boundary and word length. Check if it is possible to fill in any of the selected direction.So by doing this we can improve the performance

Hope this tutorial was helpful 🙂

Thanks for Reading