structure hw2 =
struct
(*	There are nine tiles, each with 4 ropes on them
	Store a tile by given the different rope positions
	1 = Blue; 2 = Green; 3 = Yellow; 4 = Red
	The tile will be a tuple as follows:
	(straight rope
		* same side as #1 rope, runs across it going from far point to far point
		* goes from two sides not with #2, near half on side with rope from #2
		* twisted crossing rope, on sides with #2, #3)
	These ropes start with the yellow on the left and work down and then right from the first block on
	http://www.geocities.com/jaapsch/puzzles/tangle.htm, under the Mini-Tangle heading
*)

val forwardTime = ref (Int.toLarge 0)
val ACTime = ref (Int.toLarge 0)

val miniTangleTiles =
	[
		(3,2,1,4),
		(3,1,2,4),
		(3,1,4,2),
		(4,2,1,3),
		(1,2,4,3),
		(2,4,3,1),
		(2,1,3,4),
		(2,4,1,3),
		(1,3,4,2)
	]

fun toColor x =
	case x of
		1 => "Blue"
		| 2 => "Green"
		| 3 => "Yellow"
		| 4 => "Red"


(* map a tile to its rope colors *)
fun toColors (a,b,c,d) =
	(toColor a, toColor b, toColor c, toColor d)

(*	Each side of the tile will be labeled 0-3 with 0 corresponding to the left side of the first tile from
	the webpage, and counting up going counter clockwise
	Each tile will then have a rotation from 0-3 with 0 being the first tile from the webpage, and each increment
	a 90 degree rotation clockwise
	The side facing left will then be <rotation>
	The side facing down will be (1 + <rotation>) % 4
	etc.
	Each side has 2 ropes, a tile facing it must have ropes of the same color in the opposite order
*)

(* takes a tile, its orientation, and what side of the tile we want, and generates a pair of ropes coming out from it *)
fun generateRopeColors (rope1,rope2,rope3,rope4) rotation side =
	let
		val whichSide = Int.mod((side + rotation),4)
	in
		case whichSide of
			0 => (rope1,rope2)
			| 1 => (rope3, rope4)
			| 2 => (rope3, rope1)
			| 3 => (rope2, rope4)
	end

val boardSize = 3

(* determine if tile 1 is above, below, etc of tile 2*)
fun findSide tile1Pos tile2Pos =
	if (Int.mod(tile1Pos,boardSize) - 1 = Int.mod(tile2Pos,boardSize)) andalso (tile1Pos - 1 = tile2Pos) then 0
		else if tile1Pos + boardSize = tile2Pos then 1
			else if (Int.mod(tile1Pos,boardSize) + 1 = Int.mod(tile2Pos, boardSize)) andalso (tile1Pos + 1 = tile2Pos) then 2
				else if tile1Pos - boardSize = tile2Pos then 3
					else 4

(* are the two tiles positioned properly *)
fun properPosition tile1 tile1Pos tile1Rotation tile2 tile2Pos tile2Rotation = 
	let
		(*val dummy = print (String.concat [Int.toString tile1Pos," ",Int.toString tile2Pos,"\n"])*)
		val tile1Side = findSide tile1Pos tile2Pos
		val tile2Side = (tile1Side + 2) mod 4
		val (tile1Rope1, tile1Rope2) = generateRopeColors tile1 tile1Rotation tile1Side
		val (tile2Rope1, tile2Rope2) = generateRopeColors tile2 tile2Rotation tile2Side
	in
		(not (tile1Pos = tile2Pos)) andalso (tile1Side = 4 orelse (tile1Rope1 = tile2Rope2 andalso tile1Rope2 = tile2Rope1))
	end

(* a list from 0 -> n *)
fun incrementedList ~1 = []
| incrementedList n = n::incrementedList (n - 1)
	
(* The domain for a variable is a list with entries of form (position,rotation) *)
val domain =
	List.foldl
		(fn (x,old) =>
			List.concat
				[List.map (fn y => (x,y)) (incrementedList 3),
				old])
		[]
		(incrementedList (boardSize*boardSize-1))
		
(*	The csp is merely a list of variables
	The variables are of the form (tile, domain)
	Every tile is constrained to every other by the fact that they must not be in the same position
*)
fun createCSP tiles =
	map (fn tile => (tile,domain)) tiles
	
(*	Assignments are represented by a list with entries of form (tile,position,orientation) *)

fun printAssignments [] = print "\n"			
| printAssignments ((tile, position, orientation)::rest) =
	let
		val colors = toColors tile
		val dummy = print (String.concat [#1 colors, " ", #2 colors, " ", #3 colors, " ", #4 colors, ":",Int.toString position," ", Int.toString orientation,"\n"])
	in
		printAssignments rest
	end

fun backtrackSimplify csp _ _ = csp

(* perform the forward propagation given the assignment *)
fun forwardSimplify csp (tile,position,rotation) _ =
	let
		val timer = Timer.startCPUTimer ()
		val csp =
			map
				(fn (currentTile,domain) =>
					(currentTile,
						(List.filter
							(fn (domainPosition, domainRotation) =>
								properPosition currentTile domainPosition domainRotation tile position rotation)
							domain)))
				csp
		val time = Timer.checkCPUTimer timer
		val dummy = forwardTime:= (!forwardTime) + (Time.toMilliseconds (#usr time))
	in
		csp
	end

(* perform the AC3 algorithm from the book *)
fun AC3 csp  =
	let
		val constraints =
			let
				fun loop [] = []
				| loop (tile1::rest1) =
					let
						fun loop2 [] = []
						| loop2 (tile2::rest2) =
							if not (tile1 = tile2) then
								(tile1,tile2)::(loop2 rest2)
								else loop2 rest2
					in
						List.concat [(loop2 rest1),loop rest1]
					end
			in
				loop csp
			end
		fun loop csp [] = csp
		| loop csp (((tile1,domain1),(tile2,domain2))::rest) =
			let
				val filteredDomain1 =
					List.filter
						(fn (position,rotation) =>
							List.exists
								(fn (position2,rotation2) => properPosition tile1 position rotation tile2 position2 rotation2)
								domain2)
						domain1
				val removed = not (List.length domain1 = List.length filteredDomain1)
				val queue =
					if removed then
						List.concat
							[rest,
								List.filter (fn ((tileA,_),(tileB,_)) => tileA=tile1 orelse tileB=tile1) constraints]
						else rest
			in
				loop
					((tile1,filteredDomain1)::(List.filter (fn (tile,_) => not (tile=tile1)) csp))
					(if removed then
						(map
							(fn ((tileA,domainA),(tileB,domainB)) =>
								((tileA, if tileA = tile1 then filteredDomain1 else domainA),
									(tileB, if tileB = tile1 then filteredDomain1 else domainB)))
							queue)
						else queue)
			end
		in
			loop csp constraints
		end
			
fun ACSimplify csp assignment assignments =
	let
		val timer = Timer.startCPUTimer ()
		val assignments = assignment::assignments
		val csp =
			(List.filter
				(fn (tile,domain) =>
					let	(*val dummy=print (String.concat [Int.toString (List.length domain)," "])*)
					in
					Bool.not
						(tile = (#1 assignment))
					end)
				csp)
		val csp =
			List.concat
				[csp,
					List.map (fn (tile,position,rotation) => (tile, [(position,rotation)])) assignments]
		val csp = AC3 csp
		val time = Timer.checkCPUTimer timer
		val dummy = ACTime:= (!ACTime) + (Time.toMilliseconds (#usr time))
	in
		csp
	end

(* the search -- simplifyCSP is a function that simplifies the domains according to forward propagation and arc consistency *)
fun backtrack assignments csp simplifyCSP =
	let
		(*val dummy = print (String.concat [Int.toString (List.length assignments), ":"])*)
		val csp =
			(List.filter
				(fn (tile,domain) =>
					let
						val (a,b,c,d) = toColors tile
						(*val dummy=print (String.concat ["(",a,",",b,",",c,",",d,"):",Int.toString (List.length domain)," "])*)
					in
					Bool.not
						(List.exists (fn (assignedTile,_,_) => assignedTile=tile) assignments)
					end)
				csp)
		fun backtrackLoop tile domain =
			if List.null domain then []
				else
					let
						val (position, rotation) = List.hd domain
					in
						if
							List.foldl
								(fn ((assignedTile, assignedPosition, assignedOrientation),old) =>
									old andalso (properPosition tile position rotation assignedTile assignedPosition assignedOrientation))
								true
							assignments
							then
								let
									val result = backtrack ((tile,position,rotation)::assignments) (simplifyCSP csp (tile,position,rotation) assignments) simplifyCSP
								in
									if List.null result then backtrackLoop tile (List.tl domain)
										else result
								end
								else
									backtrackLoop tile (List.tl domain)
					end
	in			
		if List.length assignments = boardSize*boardSize then assignments
		else
			let
				val (tile,domain,_) =
					(*List.hd
						(ListMergeSort.sort
							(fn ((_,domain1),(_,domain2)) => (List.length domain1) > (List.length domain2))
							csp)*)
					List.foldl
						(fn ((tile,domain),(oldTile,oldDomain,length)) => if ((List.length domain) < length) orelse length = ~1 then (tile,domain,List.length domain) else (oldTile,oldDomain,length))
						((1,1,1,1),[],~1)
						csp
				(*val dummy = print (String.concat [":",Int.toString (List.length domain),"\n"])*)
			in
				backtrackLoop tile domain
			end
	end
	
fun time csp simplifyCSP =
	let
		val timer = Timer.startCPUTimer ()
		val dummy = backtrack [] csp simplifyCSP
		val time = Timer.checkCPUTimer timer
	in
		Time.toMilliseconds (#usr time)
	end
	
val test = printAssignments (backtrack [] (createCSP miniTangleTiles) backtrackSimplify)
val test = printAssignments (backtrack [] (createCSP miniTangleTiles) forwardSimplify)
val test = printAssignments (backtrack [] (createCSP miniTangleTiles) ACSimplify)

val backtrackTime = time (createCSP miniTangleTiles) backtrackSimplify
val dummy = forwardTime := 0
val forTime = time (createCSP miniTangleTiles) forwardSimplify
val forPropTime = (!forwardTime)
val dummy = ACTime := 0
val AC3Time = time (createCSP miniTangleTiles) ACSimplify
val AC3PropTime = (!ACTime)

val results = (backtrackTime,forTime,forPropTime,AC3Time,AC3PropTime)



end