N Queens on an FPGA (2014) [pdf] | Hacker News Reader

N Queens on an FPGA (2014) [pdf]

doc.utwente.nl

48 pointsmerrier19 comments

Obligatory link to the highly approachable and all around amazing http://nand2tetris.org, which will get you to the level of FPGA knowledge necessary to tackle projects like this.

I am thinking that N Queens would make a great hobby FPGA learning project. Not the automatic math->HDL translation of the paper, but writing a solver directly in VHDL that would blink the solutions on an LED matrix.

It seems to me, at my level of VHDL knowledge, hard enough to be interesting but easy enough to be achievable. It's better than making 7 segment LEDs count, which was my last project.

I weep for the wasted computing power that has gone to solving this problem, considering it has a closed form solution.

Just wait until you hear how much power is being spent on finding multiples of 3 and 5!

When was a closed form found? Last I checked, there was none. (Quickly googling shows that this is still the case.)

Take a look at this 1969 paper: http://penguin.ewu.edu/~trolfe/QueenLasVegas/Hoffman.pdf

For a 2n x 2n grid, the queens can be placed on (k, 2k) and (2n+1-k, 2n+1-2k), k=1..n. For a (2n+1) x (2n+1) grid, an additional queen is placed on (2n+1, 2n+1).

The method described in what you linked will give you one solution (as in: one valid placement), not enumerate all of them, which is what is done in the submitted paper (although that information is needlessly buried for whatever reason).

It was needlessly buried because that is the assumption.

Anyone making something to "solve" the N-Queens is typically doing the difficult task of finding all solutions. Not the easier task of finding a solution.

That might have been a valid argument if it was coming from the authors of the paper. My point was that computation power is better spent solving problems that matter.

N queens is just an example for the technique, and it isn't much computation anyways. My guess is your computer spends orders of magnitude more cycles rounding the corners of rectangles or paging files in and out of disk than it would computing solutions to N queens.

Also consider that FPGAs use much less power than CPUs:

* Opening Hacker News to make your comment uses up enough power to solve N Queens thousands of times over.

* Driving to the store uses enough energy in gas to solve N Queens probably trillions of times at least.

* That time you opened a Ruby or Python interpreter and ended up closing it without doing anything? More energy than N Queens.

* That time you opened psql to the company database and had a setting to automatically start a transaction? It delayed vacuuming a table just long enough that the time spent processing unpruned records could've calculated an N Queens solution.

* I think my Basys 2 FPGA draws 2 milliamps, while my air conditioner peaks at 40 amps. My gut is that current can be used to compute an awful lot of N Queens.

Honestly, just complaining about the problem is wasting more energy than the problem.

Indeed N-queens is used as a case study, my point is that this is a horrible case study and by their admission, they don't even solve it better than the state-of-the-art. A classic example for a high-level synthesis system would have been to synthesize some component of a video/audio codec. This would have clearly demonstrated value.

On top of that, there are papers referenced from this paper that talk about spending 53 years of computation on a grid to solve N=25. There is (was?) even a nqueens@home project. None of this folding proteins on your GPUs nonsense, we need to know how to place queens on a board!

N-queens is a nice combinatorics problem but it's just that: Enumerating all its solutions (with custom hardware no less) is as meaningless as, say, enumerating all cyclic decompositions of permutations.

PS: nobody's complaining Michael, an opinion was politely stated. Clearly the reviewers of the prestigious "Open Channel Publishing Ltd." thought that this paper had enough value to be published, and I suppose you have the same mindset as they do.

I think we have different definitions of "politely stated."

Regardless, finding ways of running any recursive backtracking problem in faster execution environments has merit. Getting their method in the eyes of others may lead to someone else making substantial progress. May, of course. Nothing is guaranteed.

And the "toy" problem of N-Queens is a good one specifically because it is pedagogical. This is why we let people interested play with toys in the first place. (After all, why not "weep for the minds that are given these toy puzzles?")

I may disagree with you on the value of N-queens as a case study in this particular case, but your general statement is definitely fair: You never know where inspiration may come from.

Many years back, my PhD advisor told me the following story: Back in the 70s, he had come up with some sort of solution to the N-queens problem and had sent a (snail) mail to Don Knuth describing it. Knuth responded back with a single sentence: ``I am fed up with the N-queens problem.''

Funny, since my favorite solution to the N-Queens is from Knuth. http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color...

He has an update of this in his book on Fun and Games.

dancing links are awesome.

Just wait until I tell you about all the game consoles that only ever run less than five programs before being tossed

For an 8x8 board, n=4, we get

  (1,2) (2,4) (3,6) (4,8)
  (8,7) (7,5) (6,3) (5,1)

where for example (2,4) and (5,1) are queens on the same diagonal.

Yeah, the parent comment was oversimplifying things. That particular solution only works for values of n != 3λ+1 (λ = 0,1,2,...). If you read the paper, they provide a number of different constructions, each one covering a different subset of n.

For n=4, I believe you'd need to use construction B, which is (k, 1+((2(k-1)+n-1) % 2n)) and (2n+1-k, 2n-((2(k-1)+n-1) % 2n)). Your resulting coordinates then become:

  (1,4) (2,6) (3,8) (4,2)
  (8,5) (7,3) (6,1) (5,7)

I think that should be a valid solution.

that is correct; thanks for the clarification!

Reply on news.ycombinator.com