User File #3117552187364601

Upload All User Files

#3117552187364601 - PolariumSolverV6.0.1

PolariumSolverV6.lua
Game: Polarium ( DS, see all files )
998 downloads
Uploaded 12/10/2012 9:09 AM by partyboy1a (see all 14)
This program does a brute-force search for solutions for Polarium. It uses some features to eliminate worthless solutions:
- "battle": is looking for solutions covering exactly the same tiles, having the same (current) endpoint, having the last two directions identical. Only keeps the lowest score.
- remove unsolvables: obvious, can be improved for sure.doesn't make use of parity for example.
- remove needlessly complicated: disallow wasting the border. currently missing the special case about edges.
- remove bad starting points: we can safely assume that the starting point always has a "better" row/col - position than the endpoint.
- remove too bad score: don't brute-force through the solutions if we already found the shortest solution, and the score of the current puzzle is bigger than the currently lowest score for a solution.
V6.0.1: bug fixed: program now also finds the shortest solution for stage 34, which involves doing the first step onto a row from outside.
--if you want to test if valid solutions are removed
--you can enable this by uncommenting the next line
--
--test for stage 09
--debug_solution = {start_y = 1, start_x = 3, path = {left, left, down, right, down, right, right, right, right, up, right, up, left, left}}

function deepcopy(orig)
    local orig_type = type(orig)
    local copy
    if orig_type == 'table' then
        copy = {}
        for orig_key, orig_value in pairs(orig) do
            copy[orig_key] = deepcopy(orig_value)
        end
    else -- number, string, boolean, etc
        copy = orig
    end
    return copy
end

function printpuzzle(p)
	local s = ""
	local puz = p.puzzle
	for y = 0, height + 1 do
		for x = 0, width + 1 do
			local c = puz[y][x]
			if c == nil then c = "i" end
			if p.solutionrequired[y] == nil or p.solutionrequired[y] == "*" then
				if c == true then
					s = s .. "    #"
				elseif c == false then
					s = s .. "    ."
				elseif type(c) == "number" then
					s = s .. string.format("%5u", c)
				else
					s = s .. "    " .. c
				end
			elseif p.solutionrequired[y] == true then
				if c == true then
					s = s .. "    +"
				elseif c == false then
					s = s .. "    -"
				elseif type(c) == "number" then
					s = s .. string.format("%5u", c)
				else
					s = s .. "    " .. c
				end
			elseif p.solutionrequired[y] == false then
				if c == false then
					s = s .. "    +"
				elseif c == true then
					s = s .. "    -"
				elseif type(c) == "number" then
					s = s .. string.format("%5u", c)
				else
					s = s .. "    " .. c
				end
			else
				s = s .. "!failure " .. y .. ";" .. x .. ";" .. tostring(c) .. ";" .. tostring(p.solutionrequired[y]) .. "("..type(p.solutionrequired[y])..")" .. "!"
			end
		end
		print(s)
		s = ""
		--if y < #puz then s = s .. "\n\n" end
	end
	--print(s)
end

-- used to identify
-- solutions which are practically identical
function signature(p)
	local s = tostring(p.y) .. ";" .. tostring(p.x) .. 	current.lastdirection .. tostring(current.changeddirection)
	local puz = p.puzzle
	for y = 0, #puz do
		s = s .. "\n"
		for x = 0, #puz[1] do
			if puz[y][x] == true or puz[y][x] == false or puz[y][x] == "*" then
				s = s .. "_"
			else
				s = s .. "X"
			end
		end
	end
	return s
end

function polarium_solver(puz)

	height = #puz
	width = #puz[1]
	
	puzzle = {}
	for y = 1, height do
		puzzle[y] = {}
		for x = 1, width do
			puzzle[y][x] = (puz[y][x] == 1)
	end end
	
	for y = 0, height + 1, height + 1 do
		puzzle[y] = {}
		for x = 0, width + 1 do
			puzzle[y][x] = "*"
		end
	end
	for y = 1, height do
		for x = 0, width + 1, width + 1 do
			puzzle[y][x] = "*"
		end
	end		

	fifo_first = 0
	fifo_last = 0
	fifo = {}
	current_battle = {}

	elementcount = 0
	maxelements = 0
	-- start an attempt for every starting point
	for y = 1, height do
		for x = 1, width do
			current = {
				puzzle = deepcopy(puzzle),
				x = x, y = y, step = 1,
				solutionrequired = {}
			}
			if debug_solution ~= nil then
				if y == debug_solution.start_y and x == debug_solution.start_x then
					current.must_solve = true
					print("Puzzle inserted: ")
					printpuzzle(current)
				end
			end
			
			current.solutionrequired[y] = puzzle[y][x]
			current.puzzle[y][x] = 1
			current.start_x = x
			current.start_y = y
			current.before_outside_x = x
			current.before_outside_y = y
			
			current.score = 3
			current.changeddirection = false
			current.lastdirection = "none"
			
			fifo_last = fifo_last + 1
			fifo[fifo_last] = current
			
			elementcount = elementcount + 1
			maxelements = math.max(maxelements, elementcount)
		end
	end

	counter = 1
	unsolvable_counter = 0
	needlessly_complicated_counter = 0
	bad_starting_point_counter = 0
	score_too_bad_counter = 0
	
	fifo_first = fifo_first + 1
	current = fifo[fifo_first]
	fifo[fifo_first] = nil
	last_step = 1
	last_counter = 0
	lost_battle_count = 0
	battle = true
	
	function enqueue_partial_solution(p)
		--check if we already know
		--a better partial solution
				
		if p.must_solve then
			print("going to test: ")
			printpuzzle(p)
			
			if p.lastdirection ~= debug_solution.path[p.step - 1] then
				p.must_solve = nil	
				return
			else
				print("solution is still around in step "..p.step)
			end
		end
		
		--do we already know a puzzle which
		--   - has the same endpoint
		--   - the same direction
		--   - the same covered tiles?
		local sig = signature(p)
		if not battle or current_battle[sig] == nil then
			--no? then just add the new puzzle
			fifo_last = fifo_last + 1
			fifo[fifo_last] = p
		
			if battle then
				current_battle[sig] = {
					index = fifo_last,
					score = p.score
				}
			end
		else
			--yes? fine, we only need to
			--keep the best one!
			local scoretobeat = current_battle[sig].score
			
			if p.score < scoretobeat then
				--overwrite the obsoleted element
				fifo[current_battle[sig].index] = p
				current_battle[sig].score = p.score
			else
				--this one is definitely worse
				--than another already known
				--partial solution
				if p.must_solve then
					print("ERROR: removed for being suboptimal")
					error()
				end
				return false
			end
		end
		
		return true
	end
	found_forced_solve = false
	
	while(current) do
	
	if current.must_solve then
		print("solution exists! ")
		printpuzzle(current)
		found_forced_solve = true
	end
	if current.step > last_step then
		print("one more tile covered! step: " .. last_step .. "; elements: " .. counter - last_counter)
		
		if debug_solution and not found_forced_solve and debug_solution[last_step] ~= nil then
			print("FATAL error! solution was lost in step " .. last_step)
			exit()
		end
		
		found_forced_solve = false
		--print(signature(current))
		last_counter = counter
		last_step = current.step		
		current_battle = {}
	end
	
	--check if this one solves the maze
	solved = false
	validvalues = 0
	for y = 1, height do
		for x = 1, width do
			if		type(current.puzzle[y][x]) == "number"
				or	(
						current.solutionrequired[y] ~= nil
					and current.puzzle[y][x] ~= current.solutionrequired[y]
				)
			then
				validvalues = validvalues + 1
			end
		end
	end
	if validvalues == height * width then
		if current.must_solve then
			print("success! score: "..current.score)
		end
		if shortest == nil then
			print("counter: ".. counter .. "; elements: " .. elementcount .. "; max: " .. maxelements .. "; unsolvables removed: " .. unsolvable_counter)
			printpuzzle(current)
			print("!! shortest solution found !! score: " .. current.score)
			shortest = current
			fastest = current
			bestscore = current.score
		else
			if bestscore > current.score then
				print("lower score found: " .. current.score)
				printpuzzle(current)
				fastest = current
				bestscore = current.score
			else
				if current.must_solve then
					print("ERROR: score too high! it is " .. current.score)
					exit()
				end
			end
		end
		solved = true
	end
	
	if not solved then
	
		--check if this maze is unsolvable
		--first: mark all already visited fields
		visited = {}
		for y = 0, height + 1 do
			visited[y] = {}
			for x = 0, width + 1 do
				if type(current.puzzle[y][x]) == "number" then
					visited[y][x] = true
				else
					visited[y][x] = false
				end
			end
		end
		
		--second: check if all fields which must be stepped on can actually be reached
		fifo_u = {{x = current.x, y = current.y, step = current.step}}
		pos = table.remove(fifo_u, 1)
		while pos do
			--check if we can visit the field to our left
			if 		--field limit hasn't been reached
					(pos.x >= 1)
				and	--field hasn't already been visited
					(not visited[pos.y][pos.x-1])
				and	--field is of the same colour or outside
					(
						--field to step on is outside
						(pos.x == 1)
					or	(pos.y == 0)
					or	(pos.y == height + 1)
					or	(	--we may have moved up or down into an "unexplored" row
							--in an unexplored row, all puzzle fields are either true or false or "*" (outside)
							--we can only go left if both fields are true or if both fields are false
							--(we checked that we won't move to the outside already)
								(current.solutionrequired[pos.y] == nil)
							and (	--either both fields need to have the same colour
									(current.puzzle[pos.y][pos.x - 1] == current.puzzle[pos.y][pos.x])
									--or we come from outside from the right
								or	(pos.x == width + 1)
								)
						)
					or	(	--we visited at least one place of this row
							--we just have to make sure we visit the right colour
							--(we checked that we won't move to the outside already)
								(current.solutionrequired[pos.y] ~= nil)
							and (current.solutionrequired[pos.y] == current.puzzle[pos.y][pos.x - 1])
						)
					)
			then
				visited[pos.y][pos.x-1] = pos.step + 1
				table.insert(fifo_u, {x = pos.x - 1, y = pos.y, step = pos.step + 1})
			end
			
			--check if we can visit the field to our right
			if		--field limit hasn't been reached
					(pos.x <= width)
				and	--field hasn't already been visited
					(not visited[pos.y][pos.x + 1])
				and	--field is of the same colour or outside
					(
						--field to step on is outside
						(pos.x == width)
					or	(pos.y == 0)
					or	(pos.y == height + 1)
					or	(	--we may have moved up or down into an "unexplored" row
							--in an unexplored row, all puzzle fields are either true or false or "*" (outside)
							--we can only go left if both fields are true or if both fields are false
							--(we checked that we won't move to the outside already)
								(current.solutionrequired[pos.y] == nil)
							and (	--either both fields need to have the same colour
									(current.puzzle[pos.y][pos.x + 1] == current.puzzle[pos.y][pos.x])
									--or we come from the outside from the left
								or	(pos.x == 0)
								)
						)
					or	(	--we visited at least one place of this row
							--we just have to make sure we visit the right colour
							--(we checked that we won't move to the outside already)
								(current.solutionrequired[pos.y] ~= nil)
							and (current.solutionrequired[pos.y] == current.puzzle[pos.y][pos.x + 1])
						)
					)
			then
				visited[pos.y][pos.x + 1] = pos.step + 1
				table.insert(fifo_u, {x = pos.x + 1, y = pos.y, step = pos.step + 1})
			end
			
			--check if we can visit the field to our top
			if		--field limit hasn't been reached
					(pos.y >= 1)
				and	--field hasn't already been visited
					(not visited[pos.y - 1][pos.x])
				and	--field is of the required colour or outside
					(	--field is outside
						(pos.y == 1)
					or	(pos.x == 0)
					or	(pos.x == width + 1)
					or	(		--no field has been stepped on in this row
								(current.solutionrequired[pos.y - 1] == nil)
								--we step on a field of the right colour
							or	(current.puzzle[pos.y - 1][pos.x] == current.solutionrequired[pos.y - 1])
						)
					)
			then
				visited[pos.y - 1][pos.x] = pos.step + 1
				table.insert(fifo_u, {x = pos.x, y = pos.y - 1, step = pos.step + 1})
			end
			
			--check if we can visit the field to our bottom
			if		--field limit hasn't been reached
					(pos.y <= height)
				and	--field hasn't already been visited
					(not visited[pos.y + 1][pos.x])
				and	--field is of the required colour or outside
					(	--field is outside
						(pos.y == height)
					or	(pos.x == 0)
					or	(pos.x == width + 1)
					or	(		--no field has been stepped on in this row
								(current.solutionrequired[pos.y + 1] == nil)
								--we step on a field of the right colour
							or	(current.puzzle[pos.y + 1][pos.x] == current.solutionrequired[pos.y + 1])
						)
					)
			then
				visited[pos.y + 1][pos.x] = pos.step + 1
				table.insert(fifo_u, {x = pos.x, y = pos.y + 1, step = pos.step + 1})
			end
			
			pos = table.remove(fifo_u, 1)
		end
		
		--third: now do the check!
		unsolvable = false
		for y = 1, height do
			if current.solutionrequired[y] ~= nil then
				for x = 1, width do
					if		--this field must be visited
							(current.solutionrequired[y] == current.puzzle[y][x])
						and	--this field can't be reached
							(not visited[y][x])
					then
						--there can't exist any path solving the maze
						unsolvable = true
					end
				end
			else
				--check if all fields of one colour could be visited
				all_false_were_visited = true
				all_true_were_visited = true
				for x = 1, width do
					if		--this field must be visited
							current.puzzle[y][x] == false
						and	--this field can't be reached
							(not visited[y][x])
					then
						--there can't exist any path solving the maze
						all_false_were_visited = false
					end
					
					if		--this field must be visited
							current.puzzle[y][x] == true
						and	--this field can't be reached
							(not visited[y][x])
					then
						--there can't exist any path solving the maze
						all_true_were_visited = false
					end
				end
				
				if		all_false_were_visited == false
					and	all_true_were_visited == false
				then
					unsolvable = true
				end
			end
		end
		
		if unsolvable and current.must_solve then
			print("FATAL ERROR: solution was detected as unsolvable. Not all visited")
			printpuzzle(current)
			error()
		end
		
		--fourth: check if there are multiple dead ends
		deadends = 0
		if not unsolvable then for y = 1, height do for x = 1, width do
		
			if
					(type(current.puzzle[y][x]) == "boolean")
				and	(current.solutionrequired[y] == current.puzzle[y][x])
			then
				possible_directions = 0
				--check if we can come here from the left
				if
						(visited[y][x-1])
					and (
							(
								(type(current.puzzle[y][x-1]) == "number")
							and (current.puzzle[y][x-1] == current.step)
							)
						or	(
								(type(current.puzzle[y][x-1]) == "boolean")
							and	(current.puzzle[y][x-1] == current.puzzle[y][x])
							)
						or	(current.puzzle[y][x-1] == "*")
						)
				then
					possible_directions = possible_directions + 1
				end
				
				--check if we can come here from the right
				if
						(visited[y][x+1])
					and (
							(
								(type(current.puzzle[y][x+1]) == "number")
							and (current.puzzle[y][x+1] == current.step)
							)
						or	(
								(type(current.puzzle[y][x+1]) == "boolean")
							and	(current.puzzle[y][x+1] == current.puzzle[y][x])
							)
						or	(current.puzzle[y][x+1] == "*")
						)
				then
					possible_directions = possible_directions + 1
				end
				
				if
						(visited[y + 1][x])
					and not(
							type(current.puzzle[y + 1][x]) == "number"
						and current.puzzle[y + 1][x] < current.step
						)
				then
					possible_directions = possible_directions + 1
				end
				
				if
						(visited[y - 1][x])
					and not(
							type(current.puzzle[y - 1][x]) == "number"
						and current.puzzle[y - 1][x] < current.step
						)
				then
					possible_directions = possible_directions + 1
				end
				
				if possible_directions == 0 then
					print("totally dead end at " .. y .. ","..x.."; SOMETHING MUST HAVE GONE WRONG!")
					printpuzzle(current)
					exit()
					--deadends = deadends + 2
					
					--ERROR: this should have been detected earlier
					--There must be something wrong in the code
					deadends = 0
				elseif possible_directions == 1 then
					--print("dead end at " .. y .. ","..x)
					deadends = deadends + 1
					deadend_x = x
					deadend_y = y
				end
				
			end
			
		end end end
		
		if deadends > 1 then
			unsolvable = true
		end
		
		if unsolvable and current.must_solve then
			print("FATAL ERROR: solution was detected as unsolvable. Not all visited")
			printpuzzle(current)
			error()
		end
		
		-- if two ends are available: only keep the path which starts
		-- from the higher position, or if they start with the
		-- same height, choose the left one
		bad_starting_point = false
		if deadends >= 1 then
			if
					current.start_y > deadend_y
				or (	current.start_y == deadend_y
					and current.start_x > deadend_x
					)
			then
				bad_starting_point = true
			end
		end

		if bad_starting_point and current.must_solve then
			print("FATAL ERROR: solution was detected as unsolvable. marked as bad starting point")
			printpuzzle(current)
			error()
		end
		
		score_too_bad = false
		if bestscore ~= nil and current.score >= bestscore then
			score_too_bad = true
		end
		
		if score_too_bad and current.must_solve then
			print("FATAL ERROR: solution was detected as unsolvable. score too bad.")
			printpuzzle(current)
			error()
		end
		
		-- printing a lot severely slows down the process
		if counter % 1000 == 0 then
			print("counter: ".. counter .. "; elements: " .. elementcount .. "; max: " .. maxelements .. "; unsolvables removed: " .. unsolvable_counter)
			print("needlessly_complicated removed: " .. needlessly_complicated_counter)
			print("bad starting points removed: " .. bad_starting_point_counter .."; lost battles: " .. lost_battle_count)
			if bestscore ~= nil then
				print("score too bad: " .. score_too_bad_counter)
			end
			printpuzzle(current)
			print("is this one unsolvable for sure? " .. tostring(unsolvable))
			print("is this one needlessly complicated? " .. tostring(needlessly_complicated))
			print("bad starting point? " .. tostring(bad_starting_point))
			print()
		end
		
		--only continue the current path if a solution is actually possible.
		if unsolvable then
			
			unsolvable_counter = unsolvable_counter + 1
			
		elseif bad_starting_point then
			
			bad_starting_point_counter = bad_starting_point_counter + 1
			--print("bad starting point: start = " .. current.start_y .. "/" .. current.start_x .. "; deadend = " .. deadend_y .. "/"..deadend_x)
			--printpuzzle(current)
		elseif score_too_bad then
		
			score_too_bad_counter = score_too_bad_counter + 1
			
		else
		
			--check if it is possible to go one step up
			if		--field limit hasn't been reached
					(current.y >= 1)
				and --we didn't already visit this place
					(type(current.puzzle[current.y-1][current.x]) ~= "number")
				and --visiting this place is allowed
					(	--place can be visited if it is on the outside
							(current.x == 0 or current.x == width + 1 or current.y == 1)
							--we didn't visit any field on this row
						or	(current.solutionrequired[current.y - 1] == nil)
							--we visit a field of the same colour
						or	(current.solutionrequired[current.y - 1] == current.puzzle[current.y-1][current.x])
					)
			then
				newpuzzle = deepcopy(current)
				newpuzzle.step = newpuzzle.step + 1
				newpuzzle.y = newpuzzle.y - 1
				if newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] ~= "*" then
					newpuzzle.solutionrequired[newpuzzle.y] = newpuzzle.puzzle[newpuzzle.y][newpuzzle.x]
				end
								
				needlessly_complicated = false
				if 	--we might have stepped from outside to inside
					newpuzzle.y == height
				then
					if	--we stepped from outside to inside
							newpuzzle.x ~= 0
						and newpuzzle.x ~= width + 1
						and (	math.abs(newpuzzle.x - newpuzzle.before_outside_x)
							+	math.abs(newpuzzle.y - newpuzzle.before_outside_y)
							==	1)
					then
						needlessly_complicated = true
						if current.must_solve then
							print("ERROR: puzzle was detected as needlessly complicated!")
							printpuzzle(newpuzzle)
							exit()
						end
					end
				else
					if		newpuzzle.x ~= 0
						and	newpuzzle.x ~= width + 1
						and	newpuzzle.y ~= 0
						and	newpuzzle.y ~= height + 1
					then
						-- we were inside and stay inside
						newpuzzle.before_outside_x = newpuzzle.x
						newpuzzle.before_outside_y = newpuzzle.y
					end
				end
				newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step
				
				if newpuzzle.lastdirection ~= "up" then
					newpuzzle.score = newpuzzle.score + 3
					newpuzzle.changeddirection = true
					newpuzzle.lastdirection = "up"
				else
					if newpuzzle.changeddirection == true then
						newpuzzle.score = newpuzzle.score + 1
					end
					newpuzzle.changeddirection = false
				end
				
				if not needlessly_complicated then
					success = enqueue_partial_solution(newpuzzle)
					if success then
						elementcount = elementcount + 1
						maxelements = math.max(maxelements, elementcount)
					else
						lost_battle_count = lost_battle_count + 1
					end
				else
					needlessly_complicated_counter = needlessly_complicated_counter + 1
					--print("REMOVED: pos = ".. newpuzzle.y .."; " ..  newpuzzle.x .. "; before_outside = " .. newpuzzle.before_outside_y .. "; " .. newpuzzle.before_outside_x)
					--printpuzzle(newpuzzle)
				end
			elseif current.must_solve and debug_solution[current.step] == "up" then
				print("ERROR: go up wasn't possible")
				error()
			end
			
			-- check if it is possible to go one step down
			if		--field limit hasn't been reached
					(current.y <= height)
				and --we didn't already visit this place
					(type(current.puzzle[current.y+1][current.x]) ~= "number")
				and --visiting this place is allowed
					(	--place can be visited if it is on the outside
							(current.x == 0 or current.x == width + 1 or current.y == height)
							--we didn't visit any field on this row
						or	(current.solutionrequired[current.y + 1] == nil)
							--we visit a field of the same colour
						or	(current.solutionrequired[current.y + 1] == current.puzzle[current.y+1][current.x])
					)
			then
				newpuzzle = deepcopy(current)
				newpuzzle.step = newpuzzle.step + 1
				newpuzzle.y = newpuzzle.y + 1
				if newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] ~= "*" then
					newpuzzle.solutionrequired[newpuzzle.y] = newpuzzle.puzzle[newpuzzle.y][newpuzzle.x]
				end
				needlessly_complicated = false
				if	--we might step from outside to inside
					newpuzzle.y == 1
				then
					if		--we get from outside to inside
							newpuzzle.x ~= 0
						and newpuzzle.x ~= width + 1
							--we go to a field which is right next
							--to the field where we leaved
						and (	math.abs(newpuzzle.x - newpuzzle.before_outside_x)
							+	math.abs(newpuzzle.y - newpuzzle.before_outside_y)
							==	1)
					then
						needlessly_complicated = true
						if current.must_solve then
							print("ERROR: puzzle was detected as needlessly complicated!")
							printpuzzle(newpuzzle)
							exit()
						end
					end
				else--we didn't step from outside to inside for sure
					if newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] ~= "*" then
						newpuzzle.solutionrequired[newpuzzle.y] = newpuzzle.puzzle[newpuzzle.y][newpuzzle.x]
					end
					if		newpuzzle.x ~= 0
						and	newpuzzle.x ~= width + 1
						and	newpuzzle.y ~= 0
						and	newpuzzle.y ~= height + 1
					then
						-- we were inside and stay inside
						newpuzzle.before_outside_x = newpuzzle.x
						newpuzzle.before_outside_y = newpuzzle.y
					end
				end
				newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step
				
				if newpuzzle.lastdirection ~= "down" then
					newpuzzle.score = newpuzzle.score + 3
					newpuzzle.changeddirection = true
					newpuzzle.lastdirection = "down"
				else
					if newpuzzle.changeddirection == true then
						newpuzzle.score = newpuzzle.score + 1
					end
					newpuzzle.changeddirection = false
				end
				if needlessly_complicated then
					needlessly_complicated_counter = needlessly_complicated_counter + 1
					--print("REMOVED: pos = ".. newpuzzle.y .."; " ..  newpuzzle.x .. "; before_outside = " .. newpuzzle.before_outside_y .. "; " .. newpuzzle.before_outside_x)
					--printpuzzle(newpuzzle)
				else
					success = enqueue_partial_solution(newpuzzle)
					if success then
						elementcount = elementcount + 1
						maxelements = math.max(maxelements, elementcount)
					else
						lost_battle_count = lost_battle_count + 1
					end
				end
			elseif current.must_solve and debug_solution[current.step] == "down" then
				print("ERROR: go down wasn't possible")
				error()
			end
			
			--check if it is possible to go one step left
			if		--field limit hasn't been reached
					(current.x >= 1)
				and --we didn't already visit this place
					(type(current.puzzle[current.y][current.x - 1]) ~= "number")
				and --visiting this place is allowed
					(	-- place can be visited if it is on the outside
							(current.y == 0 or current.y == height + 1 or current.x == 1)
						-- or if we visit a field of the same colour
						or	(current.solutionrequired[current.y] == current.puzzle[current.y][current.x - 1])
						-- or if we come from outside to inside, doing the first step on this row
						or	(	current.solutionrequired[current.y] ~= true
							and	current.solutionrequired[current.y] ~= false
							and	current.x == width + 1)
					)
			then
				newpuzzle = deepcopy(current)
				newpuzzle.step = newpuzzle.step + 1
				newpuzzle.x = newpuzzle.x - 1
				if newpuzzle.x ~= 0 then 
					newpuzzle.solutionrequired[newpuzzle.y] = newpuzzle.puzzle[newpuzzle.y][newpuzzle.x]
				end
				
				needlessly_complicated = false
				if 	--it is possible that we step from outside to inside
					newpuzzle.x == width
				then
					if		--we get from outside to inside
							newpuzzle.y ~= 0
						and newpuzzle.y ~= height + 1
							--we go to a field which is right next
							--to the field where we leaved
						and (	math.abs(newpuzzle.x - newpuzzle.before_outside_x)
							+	math.abs(newpuzzle.y - newpuzzle.before_outside_y)
							==	1)
					then
						needlessly_complicated = true
						if current.must_solve then
							print("ERROR: puzzle was detected as needlessly complicated!")
							printpuzzle(newpuzzle)
							exit()
						end
					end
				else
					if		newpuzzle.x ~= 0
						and	newpuzzle.x ~= width + 1
						and	newpuzzle.y ~= 0
						and	newpuzzle.y ~= height + 1
					then
						-- we were inside and stay inside
						newpuzzle.before_outside_x = newpuzzle.x
						newpuzzle.before_outside_y = newpuzzle.y
					end

				end
				newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step
				
				if newpuzzle.lastdirection ~= "left" then
					newpuzzle.score = newpuzzle.score + 3
					newpuzzle.changeddirection = true
					newpuzzle.lastdirection = "left"
				else
					if newpuzzle.changeddirection == true then
						newpuzzle.score = newpuzzle.score + 1
					end
					newpuzzle.changeddirection = false
				end
				
				if needlessly_complicated then
					needlessly_complicated_counter = needlessly_complicated_counter + 1
					--print("REMOVED: pos = ".. newpuzzle.y .."; " ..  newpuzzle.x .. "; before_outside = " .. newpuzzle.before_outside_y .. "; " .. newpuzzle.before_outside_x)
					--printpuzzle(newpuzzle)
				else
					success = enqueue_partial_solution(newpuzzle)
					if success then
						elementcount = elementcount + 1
						maxelements = math.max(maxelements, elementcount)
					else
						lost_battle_count = lost_battle_count + 1
					end
				end
			elseif current.must_solve and debug_solution[current.step] == "left" then
				print("ERROR: go left wasn't possible")
				error()
			end
			
			--check if it is possible to go one step right
			if		--field limit hasn't been reached
					(current.x <= width)
				and --we didn't already visit this place
					(type(current.puzzle[current.y][current.x + 1]) ~= "number")
				and --visiting this place is allowed
					(	-- place can be visited if it is on the outside
							(current.y == 0 or current.y == height + 1 or current.x == width)
						-- or if we visit a field of the same colour
						or	(current.solutionrequired[current.y] == current.puzzle[current.y][current.x + 1])
						-- or if we come from outside to inside, doing the first step on this row
						or	(	current.solutionrequired[current.y] ~= true
							and	current.solutionrequired[current.y] ~= false
							and	current.x == 0)
					)
			then
				newpuzzle = deepcopy(current)
				newpuzzle.step = newpuzzle.step + 1
				newpuzzle.x = newpuzzle.x + 1
				
				if newpuzzle.x ~= width + 1 then 
					newpuzzle.solutionrequired[newpuzzle.y] = newpuzzle.puzzle[newpuzzle.y][newpuzzle.x]
				end
				
				needlessly_complicated = false
				if --it is possible that we step from outside to inside
					newpuzzle.x == 1
				then
					if		--we get from outside to inside
							newpuzzle.y ~= 0
						and newpuzzle.y ~= height + 1
							--we go to a field which is right next
							--to the field where we leaved
						and (	math.abs(newpuzzle.x - newpuzzle.before_outside_x)
							+	math.abs(newpuzzle.y - newpuzzle.before_outside_y)
							==	1)
					then
						needlessly_complicated = true
						if current.must_solve then
							print("ERROR: puzzle was detected as needlessly complicated!")
							printpuzzle(newpuzzle)
							exit()
						end
					end
				else
					if		newpuzzle.x ~= 0
						and	newpuzzle.x ~= width + 1
						and	newpuzzle.y ~= 0
						and	newpuzzle.y ~= height + 1
					then
						-- we were inside and stay inside
						newpuzzle.before_outside_x = newpuzzle.x
						newpuzzle.before_outside_y = newpuzzle.y
					end
				end
				
				newpuzzle.puzzle[newpuzzle.y][newpuzzle.x] = newpuzzle.step
				if newpuzzle.lastdirection ~= "right" then
					newpuzzle.score = newpuzzle.score + 3
					newpuzzle.changeddirection = true
					newpuzzle.lastdirection = "right"
				else
					if newpuzzle.changeddirection == true then
						newpuzzle.score = newpuzzle.score + 1
					end
					newpuzzle.changeddirection = false
				end
				
				if needlessly_complicated then
					needlessly_complicated_counter = needlessly_complicated_counter + 1
					--print("REMOVED: pos = ".. newpuzzle.y .."; " ..  newpuzzle.x .. "; before_outside = " .. newpuzzle.before_outside_y .. "; " .. newpuzzle.before_outside_x)
					--printpuzzle(newpuzzle)
				else
					success = enqueue_partial_solution(newpuzzle)
					if success then
						elementcount = elementcount + 1
						maxelements = math.max(maxelements, elementcount)
					else
						lost_battle_count = lost_battle_count + 1
					end
				end
			elseif current.must_solve and debug_solution[current.step] == "right" then
				print("ERROR: go right wasn't possible")
				error()
			end
		
		end
	
	end -- solved
	
	fifo_first = fifo_first + 1
	current = fifo[fifo_first]
	fifo[fifo_first] = nil
	elementcount = elementcount - 1
	maxelements = math.max(maxelements, elementcount)
	
	counter = counter + 1
end

if shortest ~= nil then
	print("shortest solution: " .. shortest.score)
	printpuzzle(shortest)
	print("fastest solution: " .. fastest.score)
	printpuzzle(fastest)
else
	print("FATAL: no solution found!")
end

end