4 ms·
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-o
by utopcell 10y ago
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.
- taeric 10y agoI 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?")
- utopcell 10y agoI 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.''
- taeric 10y agoFunny, since my favorite solution to the N-Queens is from Knuth. http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color... He has an update of this in his book on Fun and Games.
- utopcell 10y agodancing links are awesome.