Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
--]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.