# User File #3117552187364601

#### #3117552187364601 - PolariumSolverV6.0.1

PolariumSolverV6.lua
Game: Polarium ( DS, see all files )
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

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)
--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
--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)

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
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()

--ERROR: this should have been detected earlier
--There must be something wrong in the code
elseif possible_directions == 1 then
--print("dead end at " .. y .. ","..x)
end

end

end end end

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
-- same height, choose the left one
if
)
then
end
end

print("FATAL ERROR: solution was detected as unsolvable. marked as bad starting point")
printpuzzle(current)
error()
end

if bestscore ~= nil and current.score >= bestscore then
end

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
end
printpuzzle(current)
print("is this one unsolvable for sure? " .. tostring(unsolvable))
print("is this one needlessly complicated? " .. tostring(needlessly_complicated))
print()
end

--only continue the current path if a solution is actually possible.
if unsolvable then

unsolvable_counter = unsolvable_counter + 1

--printpuzzle(current)

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
``````