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