from Hacker News

N-queen puzzle in 4 lines of Scala

by pathikrit on 4/10/16, 10:41 AM with 94 comments

• by dkopi on 4/10/16, 12:16 PM

  While definitely great proof of: 1. The author knowing a lot of the language's functional features (permutations, mapping, zipping, filters) 2. How powerful functional programming is when solving problems

  I find this type of code an anti pattern of how good code should be. This solution has a high "cognitive load" imho: http://chrismm.com/blog/how-to-reduce-the-cognitive-load-of-...

  I'd much rather see a 15-20 line solution that's clear and readable, than a 4 line solution that I have to reverse engineer.

• by est on 4/10/16, 2:00 PM

  8-queen puzzle in 1 line of Python with pretty print

  _=[__import__('sys').stdout.write("\n".join('.' * i + 'Q' + '.' * (8-i-1) for i in vec) + "\n===\n") for vec in __import__('itertools').permutations(xrange(8)) if 8 == len(set(vec[i]+i for i in xrange(8))) == len(set(vec[i]-i for i in xrange(8)))]

• by todd8 on 4/10/16, 6:31 PM

  Here's my Python3 version (4 line nQueens function):

      from itertools import permutations
  
      def nQueens(n):
          return (p for p in permutations(range(n))
                  if (len(set(c+d for c,d in enumerate(p))) == n and 
                      len(set(c-d for c,d in enumerate(p))) == n))
  
      for num,solution in enumerate(nQueens(8)):
          print("Solution #", num+1)
          print("\n".join(("  ".join("Q" if i == col else "-" for i in range(8))) for col in solution))

• by pkolaczk on 4/10/16, 12:53 PM

  Honestly, I can see more than 4 lines of code there.

• by wslh on 4/10/16, 12:55 PM

  Not the shortest, but the most clear solving in Z3 because instead of an algorithm you define the solution: https://github.com/0vercl0k/z3-playground/blob/master/nqueen...

• by SagelyGuru on 4/10/16, 2:20 PM

  There is no search solution to N-queens, so any code doing search is poor and wasteful.

  I am not going to spoil the fun by giving you the details here, just the hint: start on the right square, depending on whether N is even or odd. Then place successive queens in a knight jump pattern.

  It is fascinating to me that whoever invented chess a long time ago may have been aware of these subtle complementary relationships between the different types of moves?

• by user2994cb on 4/10/16, 6:21 PM

  Well, here's a fairly compact Haskell function that should be reasonably efficient (no fancy stuff mind):

    queens n = q n n [[]] where
     q 0 m ss = ss
     q n m ss = q (n-1) m (concatMap (\s->(map (:s)(filter (f 1 s) [0..m-1]))) ss)
     f _ [] a = True
     f n (b:s) a = a /= b && a /= b+n && a /= b-n && f (n+1) s a
    main = print $ queens 8

• by brownbat on 4/10/16, 2:10 PM

  A fast algorithm that really isn't very complex:

  http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=4DC...

• by jxy on 4/10/16, 2:38 PM

  Another HN post becomes rosetta? Besides the poor search, it does not even try to remove duplications because of symmetry.

  Rosetta posts should always include a one liner from APL, so here is a link:

  https://dfns.dyalog.com/n_queens.htm

• by pmorici on 4/10/16, 2:16 PM

  Isn't the point of an n-queen solution to be fast? What does it matter how many new lines you have in the solution if it isn't fast?

• by edejong on 4/10/16, 3:51 PM

  Personally, I love this simple, readable, short implementation in the EcliPse solver: http://www.hakank.org/minizinc/queens_viz.mzn

• by dblock on 4/10/16, 3:48 PM

  If you want to get serious about solving queens fast here's an x86 assembly implementation from 1995 - https://github.com/dblock/reines :)

• by michaelaiello on 4/10/16, 12:10 PM

  This problem is also fun with perl regexes

  http://www.perlmonks.org/?node_id=297616

• by junke on 4/10/16, 2:42 PM

  If you want a fine challenge, try "Queens and Knights" (http://archive.vector.org.uk/art10003900). It has some interesting corner cases to consider.

• by digsmahler on 4/10/16, 3:06 PM

  Love it! That's a really clever use of the Set collection type to pair down non-solutions.

• by master_yoda_1 on 4/10/16, 2:36 PM

  Here is my 2 line solution to n-queen.

  #include <nqueensolver.h>

  int main(){int n=5;solve(n);}

  Please include the binaries for nqueen solver when compiling and running.

  The point I am trying to make is that, in such a high label language like scala, this kind of claim sounds foolish.

• by Bladtman on 4/10/16, 2:36 PM

  By someone who clearly cannot count to 4?