# 'Eight Queens' Problem with Observable

14 Nov 2020@coolbutuseless has a great blog on solving the “Eight Queens” problem using R. To challenge myself in translating “R” code, I created an Observable notebook. See the final product here; read on to learn how I did it.

# Setdiff is Nonsymmetrical

This step makes sense; it eliminates diagonals movements that would take a piece *outside* the boundaries of the chessboard.
But it isn’t strictly necessary…

```
diags <- diags[diags > 0 & diags < 9]
```

… it isn’t necessary because we use `setdiff`

The `setdiff`

function will only remove items from the *first argument* (`.x`

), if they appear in the *second argument* (`.y`

); (in other words, the `setdiff`

function will not include any items from the *second argument*). That’s because the `setdiff`

function is not the *symmetric* difference…

```
possible_placements <- setdiff(possible_placements, diags)
```

… as described here:

the elements of setdiff(x,y) are

those elements in x but not in y.

**EDIT**
I noticed the author skipped the filtering step in the “compacted” solution:

```
f=function(q){L=length(q)
if(L==8){q}else{flatten(map(setdiff(v,c(q,q+L:1,q-L:1)),~f(c(q,.))))}}
```

# Tilde plus dot

I didn’t understand what this code was doing:

```
possible_placements %>%
map(~place_queen(c(queens, .x))) %>%
keep(~length(.x) > 0) %>%
flatten()
```

Specifically I didn’t understand what the tilde `~`

and dot operator `.`

were doing in this line:

```
map(~place_queen(c(queens, .x))) %>%
```

Turns out the tilde `~`

creates a simple lambda function, whose arguments are accessed via the dot `.`

, as explained here:

As MrFlick pointed out, these are two separate operators. Together, they provide a special mechanism that allows tidyverse packages to construct lambda functions on the fly. This is best described in ?purrr::as_mapper. Specifically,

If a formula, e.g. ~ .x + 2, it is converted to a function. There are three ways to refer to the arguments:

- For a single argument function, use
`.`

- For a two argument function, use
`.x`

and`.y`

- For more arguments, use
`..1`

,`..2`

,`..3`

etc

In this case, could replace the first argument of a single-argument function, so would this be equivalent (replace `.x`

with `.`

)?

```
map(~place_queen(c(queens, .))) %>%
```

In fact, if the inner function is `c(...)`

, then isn’t `c(., queens)`

the equivalent of `c(queens, .)`

; so we could use the “implicit” version: (do we need braces?)
No, this is for the *piping* dot operator, vs the *tilde-lambda* dot operator…

```
map(~place_queen(c(queens))) %>%
```

# Last statements of R functions are automatically returned

I didn’t understand how the recursive `place_queen`

R function would return a value; I saw a return statement once it found a solution, but I didn’t see a return statement at the end of the function, to return the `possible_placements`

once finished recursively searching all solutions and flattening them.

I learned that R functions will automatically return the last statement:

You can transmit a value back to the caller by explicitly calling return().

Without this call, the value of the last executed statement will be returned by default.For instance, consider the oddcount() example from Chapter 1:

# Recursive functions in Observable

Observable will complain about a “circular definition” unless we follow this approach; i.e. using the `function declaration`

, vs assigning a function to the block’s value.

`flatten()`

in Javascript

I struggled to figure out the equivalent of the ` %>% flatten()`.

In fact, the Javascript `Array.prototype.flat()`

is the equivalent of `flatten()`

When I first used `.flat()`

, my result was a single array of 736 numbers (that’s all 92 solutions x 8 positions per solution) - vs an array with 92 elements, each of which is an 8-element Array.

I realized my `.flat()`

was “over-flattening”, because my “solutions” were a normal Javascript array (i.e. my solutions were susceptible to being flattened!):

```
if (queens.length===8){
return queens;
}
```

This would be the equivalent to the R code, in the sense that it returns an object that *can be flattened*

```
return(queens)
```

So I changed my solutions to an object, with a `solution`

property and a `length`

property.

```
if (queens.length == 8) {
let result = { solution: queens, length: queens.length };
return result;
}
```

This is closer to the original R code, in the sense that it returns an object that *is not flattened*:

```
return(list(queens))
```

Notice the use of `unlist()`

later on (in the “compact” version of R code), and remember `flatten()`

is different than `unlist()`

as described here:

`flatten()`

removes a level hierarchy from a list. They are similar to`unlist()`

, butthey only ever remove a single layer of hierarchy and they are type-stable, so you always know what the type of the output is.

Notice that the “compact” version of R code

# ggplot requires `show()`

inside a function

I had to call `show()`

or `print()`

to see the `geom_tile`

visualization, as described here, and here.

You will, however, need to call

`print()`

explicitly if you want to draw a plot inside a function or for loop.

Notice that the plots are rotated 90 degrees, so they aren’t oriented the way I expect. The `queens_df`

should use `cols`

as the x-axis, not the `rows`

:

```
p <- ggplot(queens_df, aes(rows, cols)) + # ...
```

… so just swap the `rows`

, and `cols`

, then we get the right orientation:

```
p <- ggplot(queens_df, aes(cols, rows)) + # ...
```

# Code golf

The original blogpost compresses all the R code necessary to 1) find all solutions and 2) visualize all solutions, into < 160 characters (so it can fit in a tweet!)

# Visualizing Recursive solutions

Some links: