In an attempt to bolster my geek-fu and partially just out of curiosity, I’ve been learning the Microsoft functional programming language F#. It has been simultaneously frustrating and fun, as I struggle to bend my mind around functional concepts that are alien in the imperative world from which I hail.

As a fun project, I decided to implement a guessing strategy for the popular board game Clue, as proposed by Wired magazine in a recent article about teen “mathletes”:

The Task: Dr. Black has been murdered. Detective Jill must determine the murderer, crime scene, and weapon. There are six possible murderers (numbered 1 through 6, Professor Plum to Mrs. Peacock), 10 locations (1 through 10, ballroom to cellar), and six weapons (1 through 6, lead pipe to spanner). Detective Jill tries to guess the correct combination (there are 360 possibilities). Each guess is a theory. She asks her assistant, Jack, to confirm or refute each theory. When Jack refutes a theory, he reports that one of the guesses—murderer, location, or weapon—is wrong. The contestants are tasked with implementing a procedure that plays the role of Detective Jill. A brute-force program that tests all 360 theories earns a mere 50 points. An efficient program that tests no more than 20 theories earns an additional 50.

While I’m sure that my program is far from efficient, it was a good exercise for assembling the things I’ve been learning from the trivial examples in books and on the web.

It isn’t the shortest solution, but it would have earned the bonus 50 points because for any given theory, the program will only need to guess a *maximum* of ten times. The way I limit guesses is by walking through each combination of guesses in the form:

- guess1: suspect1, weapon1, room1
- guess2:
**suspect2**, weapon2, room2 (we’ve identified the suspect) - guess3:
**suspect2**,*weapon3*, room3 (we’ve identified the weapon) - guess4:
**suspect2**,*weapon3*, room4 - (etc.)

When the suspect, weapon, or room equals the suspect, weapon, or room of the theory, they “stick” and are used in each subsequent guess (see lines 38 and 25). Since there are more rooms (10) than suspects (6) or weapons (6), the number of rooms becomes the limiting factor on possible guesses.

If you’re a functional programmer, I’d love to hear your comments, suggestions, and criticisms, or maybe an implementation example in your language of choice.

**EDIT: **Just for clarity, in the code below “theory” represents the actual correct answer (I misread the instructions), while “guess” represents the current combination the program is testing. So when guess = theory, the program stops testing guesses.

module Clue open System //http://en.wikipedia.org/wiki/Cluedo let guess theory = let suspects = [| "Miss Scarlett"; "Colonel Mustard"; "Mrs. White"; "The Reverend Green"; "Mrs. Peacock"; "Professor Plum" |] let weapons = [| "Dagger"; "Candlestick"; "Revolver"; "Rope"; "Lead Pipe"; "Spanner" |] let rooms = [| "Kitchen"; "Ballroom"; "Conservatory"; "Dining Room"; "Cellar"; "Billiard Room"; "Library"; "Lounge"; "Hall"; "Study" |] let indexOf anArray anElement = Array.findIndex (fun e -> e = anElement) anArray let indicesOf aTheory = let (s, w, r) = aTheory ((indexOf suspects s), (indexOf weapons w), (indexOf rooms r)) let next g t = if g <> t then g + 1 else t let show guess = let s, w, r = guess printfn "%s with the %s in the %s" suspects.[s] weapons.[w] rooms.[r] let rec test guess theory = show guess if guess = theory then printfn "correct" else let (gs, gw, gr) = guess let (ts, tw, tr) = theory let newGuess = ((next gs ts), (next gw tw), (next gr tr)) test newGuess theory test (0, 0, 0) (indicesOf theory) //end guess let main = printfn "--------------------" let theory1 = ("Mrs. White", "Rope", "Kitchen") guess theory1 printfn "--------------------" let theory2 = ("Professor Plum", "Candlestick", "Lounge"); guess theory2 printfn "--------------------" let theory3 = ("The Reverend Green", "Spanner", "Ballroom"); guess theory3 printfn "--------------------" Console.ReadKey(true) |> ignore //end main main

Nice work. I don’t know that I have gone through all of your code quite right, but I thought that I would still share my thoughts. The first thing I thought when I heard about this was that this would be perfect for a Logic Programming system. To that end, the first thing I did was encode it into such a problem using Minikanren, which is a logic programming system in Scheme. Here’s the code:

(import (chezscheme) (minikanren definitions) (minikanren vanilla))

(define (listo lst . args)

(if (null? args)

(nullo lst)

(exist (t1)

(conso (car args) t1 lst)

(apply listo (cons t1 (cdr args))))))

(define (make-theory s w r)

(lambda (gs gw gr)

(exist ()

(== gs s)

(== gw w)

(== gr r))))

(define (solve-murder theoryo)

(run1 (x)

(exist (a b c suspects weapons rooms)

(== suspects

‘(miss-scarlett colonel-mustard mrs-white

the-reverend-green mrs-peacock professor-plum))

(== weapons

‘(dagger candlestick revolver rope lead-pipe spanner))

(== rooms

‘(kitchen ballroom conservatory dining-room cellar

billiard-room library lounge hall study))

(membero a suspects)

(membero b weapons)

(membero c rooms)

(listo x a b c)

(theoryo a b c))))

(define theoryo (make-theory ‘colonel-mustard ‘revolver ‘library))

(display (car (solve-murder theoryo)))

(newline)

Well that was a miserable failure. I’ll just post a link to it on my own blog: http://my.opera.com/arcfide/blog/minikanren-and-colonel-mustard.

Thanks Aaron! Now I guess I have to learn how to read all those parentheses 🙂

If you want to learn about Minikanren, then the following books are good to deal with:

“The Little Schemer”

“The Seasoned Schmer”

“The Reasoned Schemer”

Hope that you enjoy! I’m going to take a look at your code in more detail, I’m still playing around with the syntax myself. There’s no parentheses to help!

In each turn, we can know only one incorrect guess. You assume that we know all incorrect guesses in each round. Otherwise, we would have required a minimum of 22 checks I think