Archive for Random experiments

Sudoku Goggles

A couple of my interests overlapped this morning when I found out that Google Goggles solves Sudoku.

(As an almost-related aside, I’m still tweaking my Go Sudoku solver. More on that later.)

So, after a bit of discussion, we decided to try to mess with it by feeding it invalid puzzles. Here’s one of the tests I tried – note the 4 in the upper-left block, which should be a 3.

Bad sudoku

What Goggles detected is below. Note that the 4 in question is there, but it’s missed a few numbers elsewhere in the puzzle.

Detected sudoku

It solves this version quite happily. At first I thought it was cheating by overwriting some of the original cells, until I noticed the gaps. I tried it again a few times, keeping the camera as steady as possible and cropping out other distractions; it detected a different subset of the numbers each time, so I started to think that the OCR was a bit flaky. But it always seemed to detect a valid puzzle… and when I tried it with the original valid puzzle, it detected everything.

It seems like Goggles doesn’t just recognise any old 9×9 grid of numbers as a Sudoku puzzle; it will only recognise a valid Sudoku puzzle as a Sudoku puzzle. My theory is that when it looks at the invalid Sudoku, its best match for it is a valid Sudoku with fewer numbers, plus some noise where its OCR thought there was probably a number but wasn’t quite as confident – as though, for example, there was some dust on the lens in front of those squares. (Most of the time it seemed to drop 1s, which have fewer obvious features than other numbers and are hard to distinguish from 2s.)

The interesting thing about this is that a na├»ve implementation (i.e. what I’d probably do) would OCR the grid first, set that in stone, then feed it into a Sudoku solver/validity-checker. Google’s implementation seems to tie more organically into however its recognition engine works (from this very limited set of tests anyway) – i.e. the space of objects it recognises includes all valid Sudoku puzzles. Somehow.

Leave a Comment

Kris Kringle

Our family is breaking with our old everyone-buys-a-gift-for-everyone tradition this year and doing Kris Kringle instead. There’s a bit of kerfuffle about how to select names and get word out to everyone; I mentioned to wifey that the cleanest way would be to write a short program to shuffle the names and send each person a private email. This probably isn’t going to happen at this stage, but I might suggest it for next year. (Should go down well.)

In the meantime, it got me thinking about how to deal with people drawing their own name, which anecdotally seems to happen at least once without fail. I brute-forced some statistics, and the probability of someone not drawing their own name in any given run seems to approach e-1:

 1:        0 of        1 = zero
 2:        1 of        2 = 1 in 2.000000000000
 3:        2 of        6 = 1 in 3.000000000000
 4:        9 of       24 = 1 in 2.666666666667
 5:       44 of      120 = 1 in 2.727272727273
 6:      265 of      720 = 1 in 2.716981132075
 7:     1854 of     5040 = 1 in 2.718446601942
 8:    14833 of    40320 = 1 in 2.718263331760
 9:   133496 of   362880 = 1 in 2.718283693893
10:  1334961 of  3628800 = 1 in 2.718281657666

In other words, there’s about a 63% chance that at least one person will pick their own name and have to redraw. (There’s a 1/n chance that it’ll be the last person, which really screws things up.)

One way to avoid this if we end up doing it programmatically – other than re-shuffling until it works – is to shuffle the list of names, then assign everyone to buy a gift for the person after them in the (cyclic) list. This guarantees nobody getting their own name (for n > 1), and also has the property that there are no disjoint sets of people – everyone is in one cycle, rather than, say, two people buying for each other, or some number of larger cycles.

That seems more festive somehow. Also, it’s an actual advantage of doing it the geek way, since I can’t think of a way of doing it manually; which means I might actually be able to convince everyone that it’s a good idea.

Okay, here’s how you’d do to do it manually. Shuffle some playing cards, one for each person. Everyone takes a card, remembers it (without showing anyone), and writes their name on the back. Take the cards back, shuffle them again, and lay them out in a circle, face up. Everyone goes out of the room. One at a time, each person comes into the room (with nobody else watching), finds their own card, picks up the card clockwise from it and reads the name on the back.

Of course, my way prevents cheating.

Comments (29)

n-queens Mexican Standoff

The first day back at work has proved fruitful in the form of someone coming up with the opposite of the traditional n-queens problem: the n-queens Mexican standoff. Instead of minimising the number of mutually attacking queens (to zero), the objective of the standoff version is to maximise the number of attacks.

We haven’t done an exhaustive search yet, but I’ve been running a simulated-annealing-ish script for a while, and it looks like the most attacks is 34 (17 pairs of mutual attacks), in two configurations:

QQ.    .QQ.
QQQ or QQQQ
QQQ    .QQ.

…either of which can be expanded by adding gaps between the queens, or rotating by multiples of 45 degrees.

Q.Q..   .Q.Q.   Q...Q..
.....   Q.Q.Q   .......
Q.Q.Q   .Q.Q.   ..Q...Q
.....   ..Q..   .......
Q.Q.Q           Q...Q..
                .......
                ..Q...Q
Q...Q...

Update: Python code below the fold.

» Continue reading “n-queens Mexican Standoff”

Leave a Comment

Fibonacci music

I spent most of today messing around with music based on the Fibonacci sequence. The result I’m happiest with has four voices, each using the Fibonacci sequence mod 12 to determine the pitch (in semitones), and using the sequence with other moduli (4, 5, 3 and 2 respectively) to determine the timing.

Fibonacci MIDI (9.8KB)

Fibonacci MP3 (3.0MB)

It could generously be described as “atonal crap”, but it sort of has moments of not-completely-awful-ness. Sort of.

Python code below the fold.

» Continue reading “Fibonacci music”

Leave a Comment