Fill grid with Bs

Question

Here is a letter grid:

Here are the rules as to how to manipulate the letters in the grid:

• A marker starts at the first square.
• For each move you can move the marker one square either up, down, left or right without passing the boundaries of the grid.
• If the square you land on has an even letter (B, D, F, H, etc.) in it, the letter will be divided by 2.
• If the square you land on has an odd letter (A, C, E, G, etc.) in it, 1 will be added to that letter.

Below shows an example as to how a we control the marker up, down, left and right and how the letters change. The first one is me doing it at normal speed, and the second one is the time lapse. On that particular example I used 51 moves.

Is it possible to fill the grid with Bs in under 51 moves?

---

I programmed the app/tool/game in the above example, and here is the code so you can also have access to it.
Simply run the code. To control the marker, use the arrow keys.

import pygame

# You can change the numbers & size to whatever you like, as long as the numbers remain rectangular
numbers = [[25, 15, 21],
           [3, 1, 14],
           [23, 9, 14]]

size = 80

pygame.init()
pygame.font.init()
w, h = 600, 600
wn = pygame.display.set_mode((w, h))

class Marker():
    
    def __init__(self, x, y, color, size, line=6):
        self.x = x
        self.y = y
        self.size = size
        self.color = color
        self.line = line

    def go_up(self, distance):
        self.y -= distance

    def go_down(self, distance):
        self.y += distance
        
    def go_left(self, distance):
        self.x -= distance
        
    def go_right(self, distance):
        self.x += distance

    def draw(self):
        x, y, w, h = self.x+self.line//2, self.y+self.line//2, self.size-self.line, self.size-self.line
        pygame.draw.rect(wn, self.color, (x, y, w, h//6))
        pygame.draw.rect(wn, self.color, (x, y+h*5//6+1, w, h//6))
        pygame.draw.rect(wn, self.color, (x, y, w//6, h))
        pygame.draw.rect(wn, self.color, (x+w*5//6+1, y, w//6, h))

class Square():
    def __init__(self, x, y, w, h, num):
        self.x, self.y, self.w, self.h, self.num = x, y, w, h, num

    def draw(self):
        color = (255, 255, 150) if self.num % 2 else (150, 150, 255)
        pygame.draw.rect(wn, color, (self.x, self.y, self.w, self.h))


class Grid():
    def __init__(self, marker, x, y, size, line=6):
        self.numbers = []
        self.x = x
        self.y = y
        self.size = size
        self.line = line
        self.font = pygame.font.SysFont('Arial', size*2//3)
        self.marker = marker
        self.squares = []

    def add(self):
        for i, row in enumerate(self.numbers):
            for j, num in enumerate(row):
                x, y, w, h = self.x + j*self.size+self.line//2, self.y + i*self.size+self.line//2, self.size-self.line, self.size-self.line
                self.squares.append(Square(x, y, w, h, num))

    def draw(self):
        for square in self.squares:
            square.draw()
            wn.blit(self.font.render(chr(square.num+64), True, (0, 0, 0)), (square.x+self.size//3.3, square.y+self.size//20))

def show_moves(num, grid):
    moves = f'{num} move' if num == 1 else f'{num} moves'
    text = grid.font.render(moves, True, (255, 255, 255))
    wn.blit(text, (0, len(grid.numbers)*grid.size))

head = Marker(0, 0, (0, 255, 0), size)
grid = Grid(head, 0, 0, size)
grid.numbers = numbers
grid.add()
moves = 0
while True:
    grid.draw()
    head.draw()
    show_moves(moves, grid)
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
        elif event.type == pygame.KEYDOWN:
            moved = False
            if event.key == pygame.K_UP:
                if head.y > 0:
                    head.go_up(size)
                    moved = True
            elif event.key == pygame.K_DOWN:
                if head.y < head.size * (len(grid.numbers)-1):
                    head.go_down(size)
                    moved = True
            elif event.key == pygame.K_LEFT:
                if head.x > 0:
                    head.go_left(size)
                    moved = True
            elif event.key == pygame.K_RIGHT:
                if head.x < head.size * (len(grid.numbers[0])-1):
                    head.go_right(size)
                    moved = True
            if moved:
                moves += 1
                for square in grid.squares:
                    if (head.x, head.y) == (square.x-grid.line//2, square.y-grid.line//2):
                        if square.num % 2:
                            square.num += 1
                        else:
                            square.num = square.num // 2
    pygame.display.update()
    wn.fill((0, 0, 0))

The rules relates to the Collatz Conjecture (credits to @Moti for pointing that out!).

Answer 1

Proof that 51 moves is optimal

First let us look at each of the cells in isolation with the modified Collatz conjecture and ask what is the minimum number of moves required to reduce this cell to a B. For example, a Y reduces to a B in 7 moves as follows $$ Y \rightarrow Z \rightarrow M \rightarrow N \rightarrow G \rightarrow H \rightarrow D \rightarrow B $$ Now let us replace each cell in the grid with the minimum number of moves required to reduce this cell to a B. This will look like the following

 7 4 7

 2 1 4

 6 6 4

 

The procedure then simplifies to reducing the value by 1 each time we make a move into a new cell. If the cell has a 0 in it already then we change it to a 1 (because $B \rightarrow A \rightarrow B$).
Now let us imbue the grid with a chessboard pattern so that the corner and middle cells become black cells and the edge cells become white. Then each move consists of changing the colour of your cell. Notice that the sum of the entries in the black cells is $7+7+1+6+4 = 25$. This means we must visit the black cells at least $25$ times on our path.
Since the first visited cell will be a white cell, we must also visit the white cells at least $25$ times. However, because each of the white cells contains an even value ($4,4,2,6$) this means that we must visit the white cells an even number of times which implies that we must visit the white cells at least $26$ times.

Hence, overall, we must make $25 + 26 = 51$ moves and because we already know that this is achievable, this is the minimum.