[Question]
  [
## The picture:
  
[![Dragon Curve 11th iteration (1455 squares)](https://i.stack.imgur.com/n1TkD.png)](https://i.stack.imgur.com/n1TkD.png)
  
Sick of the same old grid where the answer is simply a square pyramidal number?
Accept the challenge and write a program that given a positive integer \$n\$ counts how many squares are in the \$n^{\text{th}}\$ iteration of the [Harter-Heighway dragon](https://en.wikipedia.org/wiki/Dragon_curve#Heighway_dragon)!
* The sequence of squares of size **1** is [A003230](https://oeis.org/A003230)
* Your code must count all the squares of any size (the first of size **2** show up in \$7^{\text{th}}\$ iteration)
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'")
Here's the beginning of the resulting sequence:
```
0, 0, 0, 1, 4, 11, 30, 78, 205, 546, 1455, 4062, 11192, 31889, 88487, 254594
```
And my un-golfed [reference program](https://tio.run/##dVTbbhoxEH3nK0ZdKc3FtFnUp5JEoLapmhYpTSP1waKVAQNWFntjm2QR5dvTM96FJL2sEOudsWfOnDnjhYpzvVDRjNXDw/4hXc9VfBlIUeEiLZzXFN298pNAodR6QnGuLM1cMaXDg1arNfFq5uwlgsibn0N6e0p9Oyt0Muxfmtedg8MLNXYj8221GLlCtnNBV8rOtOz8uBkOBX13/sbY2aXXYxOMs9Q@o092aqyJq2GrBUQftdVeRc2gFqossZvcFEA05e1wu1QerqnzyWLbcU7jpb/Tr@jDnfYrKp2xkbwqsU3byFGWCE71Sa6iiTFQ5baGgZssCy3XJcqgU3paJCBHvShhXW8EVYJW@KkQYDj59esMHzBsUfGmjWgR0Xsn@YXn01TStYuqkBxdSjMcUpuaNVb5EIbTUwJR/bLUdnLtJGcUf@z5nxuuYbfJJdZG0BdtZ3HeY/dm51kDZbUBQD4rZUbdLvWLgl8d5N@j1z1aA0Jnsz1RYfM356OsdkH6IbixQWuAgTkQqbjPevWhMiGGr40xk7KTANcL7nANPflllu/8WOW7VbN1nSXjZotqVWd/TmjFvBwxL2CnqkkFh@tjQfmGewLwKRn7BGfrpnMDvRhpD6BMB7sS@3t7/3SkBE9ob7osmoR4/qYdbHG/GuKbEy2qlX0O0eok0qeKHLsly3Tu7iF3u6KRmc2032nqRUDLwguaercgnDIWip6aCrM5MZiiyEP0qOp3HG2r633UfHPyRlzpuPRWHjMNW62HW3D0dBRQKu4FQVbUkMAj15DW2NrIKtw2lcGUodT1ufEh9up/WNss5IGxWKOPjcxE6i1oqVvaxEA2BLnSZaHGuEEgtXfOhqhs7HuvVhLNrKPLLwp/4ZaVMlCV/DM0xMIzyOrJa@KfqwVw0hnzOGrIFI1davk4PBZg8i41X9/nBiztdAGsmJpcZPW09Ho92m9CorCsrusCV4/McOFxk4NmU5Z207UaMeeQSQZa@X3My9ppD/CZgJ2rImixhcBju2vG0dHW@g/VgexGcWkz9Ia7@tLjIpTPZJFD1Q8PvwE) in Mathematica.
  
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 96 bytes
```
Ｆ…¹Ｘ²Ｎ«Ｆ¬⁼ＫＫ#⊞υ⟦ⅉⅈ⟧##¿＆ι⊗＆ι±ι↷↶»↷≔⁰ζＦυ«Ｊ⊟ι⊟ι≔¹ηＷ⬤ur⁼№ＫＤ⊗η✳λ#⊗η≦⊕ηＦη¿κ«↗↗≧⁺⬤dl⁼№ＫＤ⊗κ✳λ#⊗κζ»»⎚Ｉζ
```
[Try it online!](https://tio.run/##jZFRS8MwFIWf118RupcbiKC@CO5pbj5M3ChDQREfsvauDc2SmiYbTPbba5J1DEXQvpR7OL33fKd5xU2uuey6tTYEllyVCFeMZHqHBq4ZmanG2YXbrPxI/UM@k0G0LrSF@w/HZQsZYg2UkXSYBkfm2gocI2@vQXwB@k5HySAzQllIh97jJ7EmcCfsTrQ4VgUIRqbarSQWP9QFltwiCBpvZ2Kr7VKUlQU6IihbPEqPuA5Kcki@OZJx24pSwSUjez/F2C4SPLhN86Qh041fHWjDO@Tqv/ANVGHcVUIigbGUkDqTMtITT7TzMIF7KgzmVmgFJ4DKLzyrkvbFnAmryDLnTX9spnKDG1QWi/5sTFpRElqqY@DBXG8Rbp@byBY8vymnlccCMulaRmL2Qv4ve/1X9poGLbQ5OPi6JxK5CU0f/@6Etxb2vsiuu@kutvIL "Charcoal – Try It Online") Link is to verbose version of code. Explaantion:
```
Ｆ…¹Ｘ²Ｎ«
```
Loop over all the turns of the nᵗʰ iteration of the dragon.
```
Ｆ¬⁼ＫＫ#⊞υ⟦ⅉⅈ⟧
```
If we haven't visited this cell yet then record its position.
```
##
```
Print a segment of the dragon.
```
¿＆ι⊗＆ι±ι↷↶
```
Rotate appropriately for the next segment.
```
»↷
```
At the end of the dragon, rotate back to horizontal. (`Clear()` doesn't do this; maybe it should?)
```
≔⁰ζ
```
Start counting squares.
```
Ｆυ«Ｊ⊟ι⊟ι
```
Loop over and jump to each visited cell.
```
≔¹η
```
Start searching for squares.
```
Ｗ⬤ur⁼№ＫＤ⊗η✳λ#⊗η≦⊕η
```
While there are enough `#`s in both the upwards and rightwards directions increase the size of square being searched for.
```
Ｆη¿κ«
```
Check all sizes of squares from 1 to the largest potential size found.
```
↗↗≧⁺⬤dl⁼№ＫＤ⊗κ✳λ#⊗κζ
```
Move diagonally up and right two cells, then check downwards and leftwards for the other two sides of the square of this size and keep a running total of squares found.
```
»»⎚Ｉζ
```
Once all potential squares have been checked clear the canvas and output the final number found.
[Answer]
# JavaScript (ES6), ~~272 ... 244~~ 239 bytes
This is quite slow for \$n>6\$ but was verified locally up to \$n=8\$.
```
k=>(b=[],k=1<<k,g=d=>k--?g(d+(g[b.push(n++,n++),x+=--d%2,y+=--d%2,[x-!d,y-(d>0)]]|=d&1||2,n&-n&n/2?1:3)&3):b.map(y=>b.map(x=>b.map(w=>o+=(h=d=>d--?g[[X=x-n/2+d,Y=y-n/2]]&g[[X,Y+w]]&2&&g[[X-=d,Y+=d]]&g[[X+w,Y]]&h(d):1)(++w))))|o)(n=x=y=o=0)
```
[Try it online!](https://tio.run/##NY/baoNAEIbv8xRbSJdZdtdGA70wjnmNigjRrIdWuysxrYr67HZtm4Hh/@bEz3yk32l3vb23d6mNytcC1xpDyDBORI1uENSiRIVhLeW5BMWhjDOn/eoq0JwLm0wMHKVUz54YHxAP8kmJUYIKDyxJZlTUnWdPaCo11S/e2fWPjB6ZnzmfaQsjhn8wPKDH0HCEanNWm3Mcv@Eg7SlXIsJxoyShW1tEvLfo0d9Kop1zVP9D3ovIYgWK@S4DzntmYzYMNA44osEDWwtzgya/E02QuCcrAZJXq/Y3Mu0IuRrdmSZ3GlPCJYX9pBdmV/dTAZotF3baLesP "JavaScript (Node.js) – Try It Online")
## Commented
### Step 1
We first build the grid.
```
k => (                             // k = input
  b = [],                          // initialize b[] to an empty array
  k = 1 << k,                      // turn k into 2 ** k
  g = d =>                         // g is a recursive function taking a direction d
    k-- ?                          //   decrement k; if it was not equal to 0:
      g(                           //     do a recursive call:
        d + (                      //       using the updated direction
          g[                       //
            b.push(n++, n++),      //       append n and n + 1 to b[]
            x += --d % 2,          //       add dx to x
            y += --d % 2,          //       add dy to y
            [x - !d, y - (d > 0)]  //       use either [x, y], [x-1, y] or [x, y-1]
          ] |=                     //       as a key to identify the cell
            d & 1                  //       that is updated with either a horizontal
            || 2,                  //       or a vertical border (using the two least
                                   //       significant bits as flags)
          n & -n & n / 2 ?         //       determine whether it's a left or right turn
            1                      //       and add either 1 or 3 to d
          :                        //
            3                      //
        ) & 3                      //       force d into [0 .. 3]
      )                            //     end of recursive call
    :                              //   else:
      ...                          //     stop the recursion and process step #2
)(n = x = y = o = 0)               // initial call to g
```
### Step 2
The array `b[]` is now filled with `[0, 1, ..., 2k-1]` and the underlying object of `g` describes the horizontal and vertical borders that are set for each cell in the grid.
```
b.map(y =>                         // for y = 0 to y = 2k-1:
  b.map(x =>                       //   for x = 0 to x = 2k-1:
    b.map(w =>                     //     for w = 0 to w = 2k-1:
      o +=                         //       update the output counter o:
        ( h = d =>                 //         h is a function taking a distance d
          d-- ?                    //           decrement d; if it was not equal to 0:
            g[[ X = x - n / 2 + d, //             test the vertical border at
                Y = y - n / 2      //             (x - n/2 + d, y - n/2)
            ]] &                   //
            g[[ X,                 //             test the vertical border at
                Y + w              //             (x - n/2 + d, y - n/2 + w)
            ]] & 2                 //
            &&                     //
            g[[ X -= d,            //             test the horizontal border at
                Y += d             //             (x - n/2, y - n/2 + d)
            ]] &                   //
            g[[ X + w,             //             test the horizontal border at
                Y                  //             (x - n/2 + w, y - n/2 + d)
            ]] &                   //
            h(d)                   //             and do a recursive call
          :                        //           else:
            1                      //             stop the recursion
        )(++w)                     //         increment w; initial call to h with d = w
    )                              //     end of map()
  )                                //   end of map()
) | o                              // end of map(); return o
```
]