Instantly share code, notes, and snippets.

4 dots puzzle

# 4 dots puzzle

Initial position: There are 4 dots arranged as a square on a grid.

Move: The dots can be moved by reflecting them through any other three dots. So to move a point, draw a line segment from that dot to another dot, extend it to twice its length and move the first dot to the place where it terminates.

Question: Is it possible to transform the square into another square of a larger size?

This was a quick Lua program I wrote to brute force a solution. It systematically keeps taking moves in an Breath-first order until it reaches a given number of iterations.

Answer: No sequence of moves found in the first 100k BFS moves. Very likely, it is impossible to do.

 local T = require('table') -- All possible permutations of 4 points while keeping the last point constant local perms = { {1,2,3,4}, {2,1,3,4}, {3,2,1,4}, {2,3,1,4}, {3,1,2,4}, {1,3,2,4} } function sq_dist(pt1, pt2) -- Calculate the square distance between two points return ((pt1[1] - pt2[1]) ^ 2) + ((pt1[2] - pt2[2]) ^ 2); end function serialize_pt(pt) -- String representation of one point return '(' .. pt[1] .. ', ' .. pt[2] .. ')' end function serialize_pts(pts) -- String representation of the points local a, b, c, d = serialize_pt(pts[1]), serialize_pt(pts[2]), serialize_pt(pts[3]), serialize_pt(pts[4]) return '[' .. a .. ', ' .. b .. ', ' .. c .. ', ' .. d .. ']' end function cmp_pt(pt1, pt2) -- Compare two points by first comparing their x and then y coordinates if pt1[1] < pt2[1] then return true elseif pt1[1] > pt2[1] then return false elseif pt1[2] < pt2[2] then return true elseif pt1[2] > pt2[2] then return false else return false end end function normalize_pts(pts) -- Converts the points such that the lower most point is the origin -- TODO: If the scaling is also controlled here, then we may end up with -- a finite set of permutations only? Unlikely. T.sort(pts, cmp_pt) local origin_x = pts[1][1] local origin_y = pts[1][2] for i = 1, #pts do pts[i][1] = pts[i][1] - origin_x pts[i][2] = pts[i][2] - origin_y end end function is_square(pts) -- Calculates if looking at the points in any order makes them a square for ii = 1, #perms do local perm = perms[ii] if sq_dist(pts[perm[1]], pts[perm[2]]) == sq_dist(pts[perm[2]], pts[perm[3]]) and sq_dist(pts[perm[2]], pts[perm[3]]) == sq_dist(pts[perm[3]], pts[perm[4]]) and sq_dist(pts[perm[3]], pts[perm[4]]) == sq_dist(pts[perm[4]], pts[perm[1]]) then return true end end return false end function copy_pts(pts) -- Copy points into a new table return { {pts[1][1], pts[1][2]}, {pts[2][1], pts[2][2]}, {pts[3][1], pts[3][2]}, {pts[4][1], pts[4][2]} } end function reflect_all(pts) -- Creates all representations of pts created by mirroring them by local all_results = {} for i = 1, #pts do for j = 1, #pts do if i ~= j then -- Mirror pts[i] through pts[j] local new_pts = copy_pts(pts) new_pts[i][1] = new_pts[j][1] + (new_pts[j][1] - new_pts[i][1]) new_pts[i][2] = new_pts[j][2] + (new_pts[j][2] - new_pts[i][2]) -- normalize the new point before returning it normalize_pts(new_pts) T.insert(all_results, {moves={source=i, mirror=j}, pts=new_pts}) end end end return all_results end function serialize_moves(moves) -- Serializes moves as a sequence of mirrorings local moves_str = '' for i = 1, #moves do moves_str = moves_str .. '(' .. moves[i].source .. ' -> ' .. moves[i].mirror .. ') ' end return moves_str end pts_seen = {} pts_queue = {{moves={}, pts={{0, 0}, {0, 1}, {1, 0}, {1, 1}}}} -- The initial points are sorted. iters = 0 square_found = nil -- [[ while iters < 100000 and square_found == nil do iters = iters + 1 state = pts_queue[iters] pts = state.pts pts_seen[serialize_pts(pts)] = true reflected_pts = reflect_all(pts) for i = 1, #reflected_pts do if pts_seen[serialize_pts(reflected_pts[i].pts)] == nil then -- If we haven't seen this reflected point before pts_seen[serialize_pts(reflected_pts[i].pts)] = true -- Perform a BFS. local new_moves = {} for j = 1, #state.moves do T.insert(new_moves, state.moves[j]) end T.insert(new_moves, reflected_pts[i].moves) if is_square(reflected_pts[i].pts) then square_found = {moves=new_moves, pts=reflected_pts[i].pts} print('Found another square: ' .. serialize_pts(square_found.pts)) print('Moves needed: ' .. serialize_moves(square_found.moves)) break else T.insert(pts_queue, {moves=new_moves, pts=reflected_pts[i].pts}) end end if square_found ~= nil then break end end end --]]