We represent the search state as (player_row, player_col, box_row, box_col).

You need to count only the number of pushes. Then inside of your BFS check if the box could be pushed (in any direction) given the current position of the player.