Squaring the square algorithm in julia

General Usage
1

I’m trying to solve Squaring the square problem and hope to find a reference algorithm written in Julia. But couldn’t find one (probably because I don’t know where to look for)

I want to know if a given set of the square could be fit into a bigger square And if it could fit in, want to know it’s coordination.

Here is MWE

board1 = (6, 8)

set1 = [(2,2), (3,2)]
set2 = [(4,3), (5,4), (3,3)]

if is_fitin(set1, board1)
   internal_coordinate(set1, board1) # = [(1,1), (3,1)]
end

Any help with the direction or link to the right package would be much appreciated :slight_smile:

2

That sounds like an exact cover problem.
A typical solution to that is using Algorithm X paired with the dancing links data structure.
You can take an inspiration from here (a simplistic implementation in Python using Dicts and Sets; might be not the best performance, but hey it works).

3 Likes
3

I’ve made a simple package to use the dancing links algorithm.

https://github.com/yongheekim-dev/DLX.jl
It only works for squares, and probably very slow for a bigger square

but it will do for my task
Thank you for help :smile:

2 Likes