4 ms·
For the lulz a while back, I did a rough implementation of the DLX algorithm for the N-Queens problem. For the 4-Queens problem, it only looks at 12 possible c
by taeric 12y ago
For the lulz a while back, I did a rough implementation of the DLX algorithm for the N-Queens problem. For the 4-Queens problem, it only looks at 12 possible configurations. (Visualization here: http://taeric.github.io/DancingLinks.html http://taeric.github.io/DancingLinks.html)
The same algorithm works for the likes of Sudoku. Is quite impressive to see how quickly it can solve some problems.
- TheLoneWolfling 12y agoFor the N-queens problem, especially as N grows large, there is an interesting probabilistic solution that generally is (absurdly) fast. Put the N queens randomly on the board. Then repeatedly pick the queen that is attacked by the most other queens (if/when there are multiple, pick randomly), and place it in the spot where it is attacked by the least other queens (if/when there are multiple, pick randomly). Repeat until you have a solution.
- taeric 12y agoIf you are just looking for a solution, DLX is already absurdly fast. Granted, as N grows exceptionally large, it may be that it is also absurdly memory hungry. :) Also note, that it isn't even the best algorithm around. Just pretty good.