Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!decwrl!parc!ebert
From: ebert@parc.xerox.com (Robert Ebert)
Newsgroups: comp.sys.mac.games
Subject: Re: 3 in three clue? (CLUE, SEMI-SPOILER)
Summary: This one has the Outside In program
Message-ID: <1991Feb13.025319.22133@parc.xerox.com>
Date: 13 Feb 91 02:53:19 GMT
References: <Ebh5FuG00WBKM1cW8S@andrew.cmu.edu> <11032@pasteur.Berkeley.EDU> <1991Feb13.015916.21973@parc.xerox.com>
Sender: news@parc.xerox.com
Organization: Xerox PARC
Lines: 102

In article <1991Feb13.015916.21973@parc.xerox.com> ebert@parc.xerox.com (Robert Ebert) writes:
>In article <11032@pasteur.Berkeley.EDU> gousha@cory.Berkeley.EDUIn article <Ebh5FuG00WBKM1cW8S@andrew.cmu.edu> hm0i+@andrew.cmu.edu (H. Scott Matthews) writes: writes:
>>>    I'm having a few problems with the "Outside In" puzzle.  Actually,
>>>I'm having a lot of problems because I can't solve it!
>>
>P.S.  Hmm, I seem to have left the OutsideIn program at home.  (It's a Think C
>program)  Here's the SafetyInNumbers part-2 program...  I'll post the 
>OutsideIn program later tonight.

As promised, here's the outside in program.  Interpreting it may be almost as
hard as solving the puzzle for yourself, so I'll try to explain.  The legal
array contains information about which transition affects the outside door,
otherwise the outside doors are not represented.  1 indicates the outside
door changes when the inside door goes from closed to open, 0 indicates the
outside door changes when the inside door goes from open to closed.  The
changes array lists which inside doors are affected by the LEGAL transition
of a particular door.  That is, since legal[0] is 1, doors 0, 7, and 10 change
state when door 0 is clicked on in it's closed state.  The other transition
is not represented (as it will never yield an optimal solution.)

moves is an array, each element is set to 1 as the door is manipulated.  This
implement the "each door exactly once" constraint.  Checkmove is a recursive
routine which makes an available move.  If we ever reach level 12 (all doors
are manipulated) then we've reached a solution, so it's printed.  Note that
when printing, I print 1 for the upper-left inside door, but internally this
is represented as door 0.  Also note that the doors are numbered from left to
right, top to bottom.

#include    <stdio.h>           /* printf etc           */
#include    <strings.h>         /* strcat, strcpy, etc  */
#include    <ctype.h>           /* isalnum, etc         */

#define     DEBUG   0

int legal[12] = {
	1,1,0,0,
	1,1,1,0,
	0,1,1,0};

int changes[12][3] = {
	{0,7,10},	{1,5,8},	{2,4,11},	{3,5,10},
	{1,4,11},	{0,5,8},	{4,6,9},	{2,7,9},
	{1,6,8},	{0,2,9},	{1,7,10},	{1,6,11}};
	
int list[12];
long solutions = 0;
FILE *out;

int
checkmove(state, moves, level)
	int state[12];
	int moves[12];
	int level;
{
	int i, j;

	if (level == 12)
	{
		for (i=0; i<12; i++)
		  fprintf(out,"%d ",list[i]+1);
		fprintf(out,"\n");
		printf("*");
		if ((++solutions % 10) == 0)
		  printf("\n\n");
		return(1);
	};
	for (i = 0; i < 12; i++)
		if (!moves[i] && (state[i] == legal[i]))
		{
			int newstate[12];
			int newmoves[12];
			
			for (j = 0; j < 12; j++)
			{
				newstate[j] = state[j];
				newmoves[j] = moves[j];
			};
			newmoves[i] = 1;
			list[level] = i;
			
			for (j = 0; j < 3; j++)
				newstate[changes[i][j]] = !newstate[changes[i][j]]; 
			checkmove(newstate, newmoves, level+1);
		};
	return(0);
};


int
main()
{
	int state[12];
	int moves[12];
	int i;
	
	for (i = 0; i < 12; i++)
		state[i] = moves[i] = 0;
	out = fopen("Hard Disk:New Stuff:3Three solutions","w");
	checkmove(state, moves, 0);
	printf("\nDone.\n");
	fclose(out);
} /* MAIN */