N-queen puzzle in 4 lines of Scala (opens in new tab)

Arggh, every single time someone posts an incredible cool small piece of code that solves a difficult problem, comments like this appear.

This whole HN attitude of pristine code is killing me. This is a piece of code in a GIST and solves the problem in three lines, it is clearly not intended for production use in a large code base.

Please stop searching for something wrong and enjoy what is presented in all of its glory.

Ironically, the article linked, "Writing good code: how to reduce the cognitive load of your code", itself has a high cognitive load. It's grammatically irksome. The opening sentence has no verb, "Low bug count, good performance, easy modification." Further it uses poor non-examples of the points the author is trying to make. For example, Yoda conditionals are quirky, but do not increase cognitive load. They were also called out as a good habit in Code Complete, the very book the author sites as the long form of what he's writing about.

OTOH, the gist has a low cognitive load provided one understands funtional notation. I can look at his four lines of code and see that this is a correct solution, because each atom of the function can be reasoned about separately and then composed into the whole. The same is much more difficult with the looping solutions that have been presented as peers to this comment. These solutions have a higher cognitive load because proving correctness requires a full trace of the algorithm, while keeping all of the variables in working memory as you go.

tl;dr; The OP presented a clear and clever solution. I'll allow it. ;)

This is honestly pretty clear to understand - there's hardly anything there other than those general functional features you listed.

I think there's a difference between the cognitive load of the solution and the cognitive load of the implementation. The cognitive load of the general solution for queens is somewhat high, but that's why it's a well-known puzzle. But this implementation is practically a description of the problem itself. It's literally selecting (filter) from all queen arrangements (permutations) where the queens aren't conflicting (described via map and zipWithIndex).

Such tight structures might be difficult to parse when the patterns used are still relatively unknown. However, once applied more widely, read more often and more familiar, you might start to think the longer version (which undoubtedly relies on ambiguous naming) becomes unreadable.

Said in other words: 15 line solutions cannot break into the higher-order pattern-recognition space, since these solutions rely on context specific naming.

Naming is one of the most difficult parts of software engineering, so we should try to rely on contextual patterns in order to minimize naming altogether.

Here's < 15 lines, clear, but not functional programming :)

  #!/usr/local/bin/perl
  #borrowed from Nick Holloway <alfie@dcs.warwick.ac.uk>, 27th May 1993.
  my $size=8;my @cols=(0..$size-1);
  sub nextq {
      (print( "@_\n" ),return) if @_ == $size;
      foreach my $col(@cols) {
          next if grep($_ == $col, @_);
          my $row=@_;next if grep ($_ == $col-$row--, @_);
          my $row=@_;next if grep ($_ == $col+$row--, @_);
          nextq(@_,$col);
      }
  }   
  nextq();

Not sure if it's slower or more resource intensive than the Scala solution. I'm sure it could be golfed down to be smaller than the Scala counterpart. It has fewer characters already, even with the comments intact.

Also, this is (I think, I'm not 100% up on Scala), insanely inefficient. Usually when people discuss the n-queens problem, they do a backtrack search, stopping as soon as some queen conflicts with an earlier queen.

You can of course then go on and get increasingly clever, but I think you should at least aim for backtracking.

Those are bread and butter of functional programming, like for loop, break and continue in imperative programming. There are really no advanced features here; not even a single monad!

For someone completely unfamiliar with FP, the cognitive load might be high. However, even basic familiarity with FP constructs is enough to understand and appreciate the code.

Maybe terse Scala solutions compare to longer C solution, like terse math equations compare to longer prose text? People who are not used to greek symbols, read equations in the same speed and mindset like english text and get confused quickly. Reading requires a different mode.

I would always prefer a map/fold to a for-loop. Removing the "i" and its book keeping reduces cognitive load. However, a Python list comprehension often becomes too big an expression if you use too much filtering. Extracting the filter into its own function an giving it a good name compartmentalizes the complexity, though. All in all, it is quite subjective.

If you are used to premutations, mapping, zipping, filters the code becomes quite readable. I'm pretty sure there is C code which confuses a Haskell programmer but would be considered "clear and readable" by the average C programmer.

This has nothing to do with functional programming. Here's an iterative Python solution that's almost a direct translation but uses explicit iteration and avoids `filter`/`map`/etc.

    from itertools import permutations

    def n_queens(n):
        for p in permutations(range(n)):
            if len({c + i for i, c in enumerate(p)}) == len({c - i for i, c in enumerate(p)}) == n:
                yield p

I think a more reasonable comparison is 4 lines of code you have to think hard to decipher but is correct, vs 40 lines of code that has a bunch of bugs and edge cases and is just as jibberish but 10x more code to decipher. Shorter solutions often encode the authors insight from thinking about the problem, and longer solutions encode are more of a history of the path an author took while just hammering on it without any particular insight until it worked good enough.

it is collections api which has always been very well documented, as opposed to some scary "functional features". Nothing too advanced and absolutely no hacks

Better yet: 4 lines of code + a few lines of comments.

permutation, mapping, zipping and filtering are all completely idiomatic scala.

There is next to no cognitive load in this 4-line solution. Brute-force attack on every permutation. I would say that anyone find there to be an excessive cognitive load would be someone that is not familiar with scala nor functional programming.

Yes, the knight is to the queen as the bishop is to the rook.

That may find some solutions, but does it find them all?

I tried to make that a little more readable, and converted it to py3 -- This one produces the same output with python3, as your one-liner with python2:

  #!/usr/bin/env python3

  from itertools import permutations as p

  for vec in p(range(8)):
    if 8 == len(set(vec[i]+i for i in range(8))) \
         == len(set(vec[i]-i for i in range(8))):
      print("\n".join( '.' * i + 'Q' + '.' * (8-i-1) for i in vec),
            end="\n===\n")

The string construction could/should probably also be refactored a bit, but at least this version I have a hope of following the logic... :-)

Ah! That's similar to the solution I used in 1980 to solve this problem for a Byte Magazine contest. Except I trimmed the search tree by aborting the permutation recursion each time the condition failed in a previous step.

It took 21 minutes to find and print all the solutions, if I remember right. But that was in Basic on a machine that ran at 10MHz.

nqueens is ~4, the rest is output

Actually, this is better (and no less clear):

  import Data.List
  queens n = q [] [0..n-1] where
   q s [] = [[]]
   q s as = concatMap (\a -> q (a:s) (delete a as)) (filter (f 1 s) as)
   f _ [] a = True
   f n (b:s) a = a /= b+n && a /= b-n && f (n+1) s a
  main = print $ length (queens 8)

Undoubtedly functional, the question is whether it is improved eg. by using folds instead of explicit recursion, or replacing concatMap with monadic join.

pare

And here is the solution using Picat, using the included sat library: http://picat-lang.org/exs/bqueens.pi

An even faster x86-64 Asm one that does it with no memory accesses - everything is in registers:

https://github.com/davidad/8queens/blob/1989666c45baa639f152...

I think many may take your response as a bit off-the-cuff, but I share this sentiment. You could even go so far as to write the longest C program you could dream of to solve it, then simply feed it into

   tr -d '\n'

and call it one line! Again, many will find this pedantic and unsatisfactory but programmers should really be more precise in what they mean by lines of code.

What I think most people are really referring to is information content. To achieve the same program in shorter length, the rest of the information has to lie somewhere else (in the scala implementation or nqeensolver.h). We can increase the density of the information needed to specify a program, but not decrease it.

I actually just wrote something about this concept yesterday:

https://aconz2.github.io/programming/2016/04/09/power_of_pl....

OP here. Sorry for the code-golfy post on HN. But, some clarifications:

1. Yes, it is O(n!) - it says so in the description but not on the title of the post on HN.

2. It is 4 lines of code for `nQueen` function. I did not include the printing code in the line count.

3. And no, I did not cheat by using semicolons in same lines - these are 4 legit lines IMO. You can put the `&` clause in 1 line to reduce it further.