# Squaring the square algorithm in julia

**URL:** <https://discourse.julialang.org/t/squaring-the-square-algorithm-in-julia/30996>\
**Category:** General Usage\
**Tags:** question\
**Created:** [November 12, 2019, 9:16am UTC](https://discourse.julialang.org/t/squaring-the-square-algorithm-in-julia/30996 "2019-11-12T09:16:11Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![YongHee-Kim](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yonghee-kim/32/5965_2.png) [@YongHee-Kim](https://discourse.julialang.org/u/YongHee-Kim)\
**Post date:** [November 12, 2019, 9:16am UTC](https://discourse.julialang.org/t/squaring-the-square-algorithm-in-julia/30996/1 "2019-11-12T09:16:11Z")

</div>

I’m trying to solve [Squaring the square problem](https://en.wikipedia.org/wiki/Squaring_the_square) 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

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

---

<div class="post-metadata">

**Author:** ![Vasily\_Pisarev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_pisarev/32/7929_2.png) [@Vasily\_Pisarev](https://discourse.julialang.org/u/Vasily_Pisarev)\
**Post date:** [November 12, 2019, 7:02pm UTC](https://discourse.julialang.org/t/squaring-the-square-algorithm-in-julia/30996/2 "2019-11-12T19:02:27Z")

</div>

That sounds like an exact cover problem.  
A typical solution to that is using [Algorithm X](https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X) paired with the [dancing links](https://en.wikipedia.org/wiki/Dancing_Links) data structure.  
You can take an inspiration from [here](https://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html) (a simplistic implementation in Python using Dicts and Sets; might be not the best performance, but hey it works).

---

<div class="post-metadata">

**Author:** ![YongHee-Kim](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yonghee-kim/32/5965_2.png) [@YongHee-Kim](https://discourse.julialang.org/u/YongHee-Kim)\
**Post date:** [November 19, 2019, 9:41am UTC](https://discourse.julialang.org/t/squaring-the-square-algorithm-in-julia/30996/3 "2019-11-19T09:41:54Z")

</div>

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

[https://github.com/yongheekim-dev/DLX.jl](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 😄