Bobitos

Title: Bobitos
Author: drakon
License: freeware
Website: http://www.cin.ufpe.br/~dfs2/jogos/AI.swf

Why does this little browser based shockwave game deserve its own blog entry? Shouldn't be mixed in with two other games like last week's entry? On its own, it does not deserve a whole entry. However, it came up at a party last weekend and caught my interest. Someone gave one of the puzzles from this game as a challenge, and it got me to write a program to solve Bobitos puzzles. You are probably thinking, "that sounds like one dull party."

The goal of a Bobitos puzzle is to get the king to the center square of the 5 by 5 gride. Helping him out are five slaves. You choose which piece to move and a direction. That piece keeps moving until another piece, king or slave, blocks it. If a piece reaches the side of the board, it falls off and you lose. There is no sacrificing of slaves.



The interface to Bobitos is a little clumsy. First you click on a piece to move. Then four large arrows appear, and you select the direction. There is no way unselect the piece other than restarting the level. Also, there are no undos; you have to restart. Another interface complaint is that the pieces move painfully slowly. Finally, you have to go through the introduction every time you start the game.

Bobitos contains 18 levels. They can be played in any order by selecting the tile in the lower left corner. The top tier are very easy, and they get harder as you work your way down. For me, the game did not keep track of completed levels between sessions. One other minor complaint, the game does not record the number of moves made. This is a shame because of the additional challenge of finding the minimal solution.

The level that came up at the party is the leftmost one in the bottom tier.

S . S . S
. . . . .
S . . . .
. . . . .
S . . . K

One party-goer threw it out there and said it can be done in 14 moves. He actually called the game by a different name, rambling robots or something. I had remembered playing Bobitos a while back. The next day, I wrote a quick and dirty search program to solve these puzzles and found that this position requires only 13 moves to be solved.

Interestingly, if a position can be solved, it can be solved in 14 moves. Here are nine positions, unique up to the symmetry of the square, which require 14 moves.

K . . . S    . . . . S    . . . . S
. . . . .    K . . . .   K . . . .
. . . . .    . . . . S   . . . . S
. . . . S    . . . . .   . S . . .
S . . S S    S . S S .   S . . S .
          
. S . . .    . S . . .   . . S . .
K . . . .    K . . . .   K S . . .
. . . . S    . . . . S   . . . . S
. . . . .    . . . . .   . . . . .
S . . S S    S . S . S   S . . S .
          
K . . . S    K . . . S   K . . . S
S . . . .    S . . . .   . S . . .
. . . . .    . . . . S   S . . . .
. . . . S    . . . . .   . . . . S
. . S . S    . . S . S   . . S . .

I could not come up with a mathematical argument for why no position takes more than 14 moves. All I have right now is that the computer says so. If you see why 14 suffices, let me know.