December 2008

Cracking TootSweet's Masyu Format

This post is not exactly well written; it’s more like a dump of my brain at the moment. I’m sorry, but I didn’t have time (or interest) to write it properly. It’s a lot of information and writing stuff isn’t quite my thing.

TootSweet Masyu: Masyu is played on a grid. It has a simple goal: to draw a single nonintersecting loop through all of the circles in the grid.

The masyu grid contains two kinds of circles. Each adds a constraint to the path of the loop.

Masyu is a type of logic puzzle designed by the same guys behind Sudoku. Needless to say, it’s very fun and extremely addicting. Especially when you play it on your iPoid, thanks to TootSweet:

Of course, I didn’t like the thought of all those beautiful, hand-made puzzles should be stuck on the iPod, so I wanted to see how they were stored. After SSH-ing to the iPod, a simple find /User/Applications/ -wholename *MasyuBug.app revealed where the files to MasyuBug were stored:

And there, right in Documents was a Puzzles.data. head -c 6 Puzzles.data revealed that it was a SQLite-file and only seconds later I got the schema:

CREATE TABLE properties ( 
  key text primary key,
  value text default null);

CREATE TABLE puzzles ( 
  id integer primary key autoincrement,
  puzzle text,
  name text default null, 
  size integer default 0,
  volume integer default 0,
  board text default null,
  checkpoint text default null,
  status integer default 0,
  solution_date default null);

The puzzles-database looks interesting. Let’s have a look:

sqlite> SELECT id,puzzle,name,board,status FROM puzzles LIMIT 3;
 id | puzzle     | name    | board | status
  1 | 4:4:AgAQAA | Ladybug | ww:gq | 2
  2 | 4:4:CCQQQA | Aphid   | AA:IC | 1
  3 | 4:4:gAAECA | Cicada  | AA:AA | 0    

After some testing with UPDATE-statements I assumed this:

The Puzzle

So I decided I wanted to crack the puzzle-field first and filled the field with various data:

Obviously, each letter represented three squares, but what do they mean? After 52 UPDATE’s I ended up with this table:

Can you spot how TootSweet’s converts letters to circles? It took me a while, but suddenly I realized it: it’s base-4. It’s in fact reversed base-4 where 0 and 3 = blank, 1 = white and 2 = white. Let me show you two examples:

The letter S is in the 18th position of our table (starting from zero), and 18 is 102 in base-4. Reverse it and you’ll get 201: One black, one blank and one white.

The letter X is in the 23th position, and 23 is 113 in base-4. Reverse it and you’ll get 311: One blank, two whites.

Ruby version:

ALPHA = ('A'..'Z').to_a + ('a'..'z').to_a
def letter(l)
  num = ALPHA.index(l)
  num.to_s(4).rjust(3, '0').reverse.split('').map{ |x| x.to_i % 3 }
end

The Lines

Let’s see how TootSweet’s stores the lines you’ve drawn. I started drawing lines in the app and watched how the board-field changed:

It made sense that each letter represented six lines. And, since I knew how TootSweet rolls, it made even more sense that it’s reversed base-2. I had to extend the ALPHA-list, since it needed 64 (2 ** 6) letters to represent every possibility from 000000 to 111111, through some more drawing on the iPod it turned out I just had to append 0 to 9 and + and /.

Example

0 is in the 52nd position of our new table (starting from zero), and 52 in base-2 is 110100. Reversed it’s 001011 and it would look like this (if we assumed that the 0 was in the first letter):

Ruby version:

ALPHA = ('A'..'Z').to_a + ('a'..'z').to_a + ('0'..'9').to_a + %w(+ /)
def line(l)
  num = ALPHA.index(l)
  num.to_s(2).rjust(6, '0').reverse.split('').map { |x| x.to_i }
end

Don’t be evil, please

I reengineered this just as a challenge. It was a lot of fun. However, if you ever want to write Masyu application, don’t steal TootSweet’s hand-made masyus. I’m sure they’ve spent a lot of time on this, and beside, it’s boring to solve the same puzzle twice.

What you could use this information to, is importing puzzles from people’s iPhones, so they can continue to solve the puzzle on their computer. Or, you can store your own puzzles in this format and this can end up as the standard way to store Masyu puzzles. Even though it’s a bit cryptic, the puzzles are quite small when they’re stored this way, and can then easily be shared over IRC and forums.

We’ll see if I ever will use this…