3 ms·

This is actually a rather poor way to solve n-queens. Consider those boards that have a queen in the first space of the first row and the second space of the se

This is actually a rather poor way to solve n-queens. Consider those boards that have a queen in the first space of the first row and the second space of the second row. These two queens can attack each other, so no such board is a solution. However, this method will still go through every such board. On the other hand, a backtracking style solution, which builds up the board row by row, will backtrack after the second queen, thus skipping all these boards.

candeira 15y ago
True, it's inefficient, but it's good for profiling Python interpreters, since it does a lot of work. It's also fast enough for low n (up to 8). Why write more code when you can get your result with less? Maybe the time he's saved with this approach can now be used writing a deduplicator (to cull out mirrored and rotated solutions). Maybe the point of the article was not only to show how fast PyPy is, but how convenient itertools.permutation() is. You can't show the convenience of itertools by not using it. However... You know what? When I was asked to write a n-queens solver recently, I also wrote a backtracker. It just doesn't mean I did it better than this guy.
- ggchappell 15y ago
  I know the point of this article is not to give the fastest n-queens algorithm. But what the heck; here is an iterative backtracking solution. On my machine, this code finds all solutions for the 10x10 board in about 1.2 sec, while the code from the article takes just under 18 sec. Using CPy 2.6.5, just like the article. Have not tried PyPy. Output is essentially the same format, except that my generator spits out lists instead of tuples. Yes, it's twice as long and harder to read. Improvements, anyone? def hit_last(p): x = p[-1] i = len(p)-1 for j in range(i): y = p[j] if x == y or i - j == abs(x - y): return True return False def n_queen(n): p = [0] while True: # Begin iter w/ board good, except maybe last Q full = len(p) == n hit = hit_last(p) if full or hit: # Will we backtrack? if not hit: # Found solution? yield p while len(p) > 0 and p[-1] == n-1: p.pop() if len(p) == 0: return p[-1] += 1 else: p.append(0)
  - kingkilr 15y ago
    Don't worry, PyPy beasts this as well, at ``n_queens(12)`` on my machine: alex@alex-gaynor-laptop:/tmp$ time python queens.py real 0m16.837s user 0m16.820s sys 0m0.000s alex@alex-gaynor-laptop:/tmp$ time pypy queens.py real 0m2.548s user 0m2.530s sys 0m0.010s

candeira 15y ago

True, it's inefficient, but it's good for profiling Python interpreters, since it does a lot of work. It's also fast enough for low n (up to 8). Why write more code when you can get your result with less? Maybe the time he's saved with this approach can now be used writing a deduplicator (to cull out mirrored and rotated solutions). Maybe the point of the article was not only to show how fast PyPy is, but how convenient itertools.permutation() is. You can't show the convenience of itertools by not using it. However... You know what? When I was asked to write a n-queens solver recently, I also wrote a backtracker. It just doesn't mean I did it better than this guy.

ggchappell 15y ago
I know the point of this article is not to give the fastest n-queens algorithm. But what the heck; here is an iterative backtracking solution. On my machine, this code finds all solutions for the 10x10 board in about 1.2 sec, while the code from the article takes just under 18 sec. Using CPy 2.6.5, just like the article. Have not tried PyPy. Output is essentially the same format, except that my generator spits out lists instead of tuples. Yes, it's twice as long and harder to read. Improvements, anyone? def hit_last(p): x = p[-1] i = len(p)-1 for j in range(i): y = p[j] if x == y or i - j == abs(x - y): return True return False def n_queen(n): p = [0] while True: # Begin iter w/ board good, except maybe last Q full = len(p) == n hit = hit_last(p) if full or hit: # Will we backtrack? if not hit: # Found solution? yield p while len(p) > 0 and p[-1] == n-1: p.pop() if len(p) == 0: return p[-1] += 1 else: p.append(0)
- kingkilr 15y ago
  Don't worry, PyPy beasts this as well, at ``n_queens(12)`` on my machine: alex@alex-gaynor-laptop:/tmp$ time python queens.py real 0m16.837s user 0m16.820s sys 0m0.000s alex@alex-gaynor-laptop:/tmp$ time pypy queens.py real 0m2.548s user 0m2.530s sys 0m0.010s