Prolog code to calculate the Bacon Number (or the "Six Degrees of Kevin Bacon" game)

bacon.pl

%% Kevin Bacon movies
cast(['Kevin Bacon', 'Lori Singer', 'John Lithgow', 'Dianne Wiest']). %% Footloose (1984)
cast(['Tom Cruise', 'Jack Nicholson', 'Demi Moore', 'Kevin Bacon']). %% A Few Good Men (1992)
cast(['Tom Hanks', 'Bill Paxton', 'Kevin Bacon', 'Gary Sinise']). %% Apollo 13 (1995)

%% Tom Cruise movies
cast(['Tom Cruise', 'Kelly McGillis', 'Val Kilmer', 'Anthony Edwards']). %% Top Gun (1985)
cast(['Tom Cruise', 'Cuba Gooding Jr.', 'Renée Zellweger', 'Kelly Preston']). %% Jerry Maguire (1996)
cast(['Tom Cruise', 'Rebecca De Mornay', 'Joe Pantoliano', 'Richard Masur']). %% Risky Business (1983)

%% Val Kilmer movies
cast(['Val Kilmer', 'Meg Ryan', 'Kyle MacLachlan', 'Frank Whaley']). %% The Doors (1991)
cast(['Val Kilmer', 'Tommy Lee Jones', 'Jim Carrey', 'Nicole Kidman']). %% Batman Forever (1995)

%% Renée Zellweger movies
cast(['Jim Carrey', 'Renée Zellweger', 'Anthony Anderson', 'Mongo Brownlee']). %% Me, Myself & Irene (2000)
cast(['Renée Zellweger', 'Gemma Jones', 'Celia Imrie', 'James Faulkner']). %% Bridget Jones's Diary (2001)

%% tells whether two actors starred together in some movie
co_starred(X, Y) :- cast(L), member(X, L), member(Y, L), X \== Y.

%% depth-first-search algorithm
next_node(C, N, P) :-
	co_starred(C, N),
	\+ member(N, P).

dfs(G, G, _, [G]).
dfs(S, G, V, [S|P]) :-
	next_node(S, NN, V),
	dfs(NN, G, [NN|V], P).

%% counts the edges in a path represented by a list
count_edges([_], 0).
count_edges([_|T], N) :-
	count_edges(T, N1), N is N1 + 1.

bacon_number(X, N) :-
	setof((L, P), (dfs('Kevin Bacon', X, [], P), length(P, L)), [(_, SP)|_]),
	count_edges(SP, N).