%Micah Modell
%Project2.pl
%Artificial Intelligence
%David Cox

go:-
	goal( Solution),
	start( InitialState),
	solve( InitialState, Solution ).

%goal( state( 1, 2, 3, 4, 5, 6, 7, 8, b) ).
%start( state( 1, b, 3, 4, 5, 6, 7, 8, 2) ).

%Begin the search
solve( Start, Solution):-
	breadthfirst( [ [ Start ] ] , Solution).

%Implement my breadth first search here.
breadthfirst( [ [ Node | Path] | _ ] , Node):- !,
	goal( Node),
	printIt( [Node | Path] ).

breadthfirst( [ Path | Paths], Solution):-
	extend( Path, NewPaths),
	conc( Paths, NewPaths, Paths1),
	breadthfirst( Paths1, Solution).

%Add new members to the end of the list
extend( [ Node | Path ], NewPaths):-
	bagof( [ NewNode, Node | Path],
		( move( Node, NewNode), not member( NewNode, [ Node | Path] ) ),
		NewPaths),
	!.
extend(  _ , [ ] ).

%Add to the beginning of a list
conc( [ ], List, List).
conc( [ X | List1 ], List2, [ X | List3] ) :-
	conc( List1, List2, List3).

%List the hypothetical legal moves
move( state( b, T2, T3, T4, T5, T6, T7, T8, T9 ),
	state(T2, b, T3, T4, T5, T6, T7, T8, T9 ) ).
move( state( b, T2, T3, T4, T5, T6, T7, T8, T9 ),
	state( T4, T2, T3, b, T5, T6, T7, T8, T9 ) ).

move( state( T1, b , T3, T4, T5, T6, T7, T8, T9 ),
	state( b, T1, T3, T4, T5, T6, T7, T8, T9 ) ).
move( state( T1, b , T3, T4, T5, T6, T7, T8, T9 ),
	state( T1, T3, b, T4, T5, T6, T7, T8, T9 ) ).
move( state( T1, b , T3, T4, T5, T6, T7, T8, T9 ),
	state( T1, T5, T3, T4, b, T6, T7, T8, T9 ) ).

move( state( T1, T2, b, T4, T5, T6, T7, T8, T9 ),
	state( T1, b, T2, T4, T5, T6, T7, T8, T9 ) ).
move( state( T1, T2, b, T4, T5, T6, T7, T8, T9 ),
	state( T1, T2, T6, T4, T5, b, T7, T8, T9 ) ).

move( state( T1, T2, T3, b, T5, T6, T7, T8, T9 ),
	state( b, T2, T3, T1, T5, T6, T7, T8, T9 ) ).
move( state( T1, T2, T3, b, T5, T6, T7, T8, T9 ),
	state( T1, T2, T3, T5, b, T6, T7, T8, T9 ) ).
move( state( T1, T2, T3, b, T5, T6, T7, T8, T9 ),
	state( T1, T2, T3, T7, T5, T6, b, T8, T9 ) ).

move( state( T1, T2, T3, T4, b, T6, T7, T8, T9),
	state( T1, b, T3, T4, T2, T6, T7, T8, T9) ).
move( state( T1, T2, T3, T4, b, T6, T7, T8, T9),
	state( T1, T2, T3, b, T4, T6, T7, T8, T9) ).
move( state( T1, T2, T3, T4, b, T6, T7, T8, T9),
	state( T1, T2, T3, T4, T6, b, T7, T8, T9) ).
move( state( T1, T2, T3, T4, b, T6, T7, T8, T9),
	state( T1, T2, T3, T4, T8, T6, T7, b, T9) ).

move( state( T1, T2, T3, T4, T5, b, T7, T8, T9),
	state( T1, T2, b, T4, T5, T3, T7, T8, T9) ).
move( state( T1, T2, T3, T4, T5, b, T7, T8, T9),
	state( T1, T2, T3, T4,  b, T5, T7, T8, T9) ).
move( state( T1, T2, T3, T4, T5, b, T7, T8, T9),
	state( T1, T2, T3, T4, T5, T9, T7, T8, b) ).

move( state( T1, T2, T3, T4, T5, T6, b, T8, T9),
	state( T1, T2, T3, b, T5, T6, T4, T8, T9) ).
move( state( T1, T2, T3, T4, T5, T6, b, T8, T9),
	state( T1, T2, T3, T4, T5, T6, T8, b, T9) ).

move( state( T1, T2, T3, T4, T5, T6, T7, b, T9),
	state( T1, T2, T3, T4, b, T6, T7, T5, T9) ).
move( state( T1, T2, T3, T4, T5, T6, T7, b, T9),
	state( T1, T2, T3, T4, T5, T6, b, T7, T9) ).
move( state( T1, T2, T3, T4, T5, T6, T7, b, T9),
	state( T1, T2, T3, T4, T5, T6, T7, T9, b) ).

move( state( T1, T2, T3, T4, T5, T6, T7, T8, b),
	state( T1, T2, T3, T4, T5, b, T7, T8, T6) ).
move( state( T1, T2, T3, T4, T5, T6, T7, T8, b),
	state( T1, T2, T3, T4, T5, T6, T7, b, T8) ).

%Print all the states in order
printIt([]).

printIt([Head | Tail]):-
    printIt(Tail),
    printBox(Head), nl.     

%Format the printout
printBox( state(T1, T2, T3, T4, T5, T6, T7, T8, T9) ):-
	write( T1), write( ' ' ), write( T2), write( ' ' ), write(T3), write( ' ' ), 
	write( T4), write( ' ' ), write( T5), write( ' ' ), write(T6), write( ' ' ), 
	write( T7), write( ' ' ), write( T8), write( ' ' ), write(T9).