3 ms·

Show HN: NQueens problem solved using backtracking in Elixir lang

taeric 11y ago
It would be interesting to see timing results of this implementation. Similarly, comparisons to other implementations/algorithms. I will have to fire up erlang when I get home this evening. I am basically a broken record on this topic, but I do like sending more people to see the Dancing Links algorithms solving this (and other related problems, such as sudoku.)[1] The techniques in DLX cut the search space for the 8-queens down to just 1,048 board states. (For 13, the number of boards is up to 1,046,318) [1] http://taeric.github.io/DancingLinks.html http://taeric.github.io/DancingLinks.html
- tacticiankerala 11y ago
  8-queens : 0.19s user 0.09s system 127% cpu 0.222 total 12-queens : 0.21s user 0.11s system 129% cpu 0.244 total 16-queens : 0.29s user 0.10s system 119% cpu 0.325 total 20-queens : 2.79s user 0.10s system 102% cpu 2.826 total 24-queens : 7.50s user 0.10s system 100% cpu 7.533 total Thanks a lot for sharing the Dancing links algorithm. It looks really interesting. I wanted to try sudoku with backtracking,but now I would like to give dancing link a try!
  - taeric 11y ago
    Are those times for finding a solution, or for all solutions? If all, that is truly impressive! Dancing links is a backtracking algorithm, just a nice way to optimize the backtracking.
    - tacticiankerala 11y ago
      It is for finding the first solution. Sorry that I didn't mention it.
      - taeric 11y ago
        No worries. I could have guessed, if I'd paid attention to how large of an N you looked at. :) Also, I should explicitly say thanks for sharing! It is fun reading solutions to this puzzle. Also fun to read Erlang.
HugoDias 11y ago
A solution for doing the same thing in Ruby: https://gist.github.com/hugodias/cf89ba138b986ddb3e7d https://gist.github.com/hugodias/cf89ba138b986ddb3e7d Time spent processing for 12 queens: 3.59 seconds
- tacticiankerala 11y ago
  Here is the benchmarking for 12-queens 12-queens : 0.21s user 0.11s system 129% cpu 0.244 total But, I see that you are finding all the solution. My program only finds the first solution.

It would be interesting to see timing results of this implementation. Similarly, comparisons to other implementations/algorithms. I will have to fire up erlang when I get home this evening. I am basically a broken record on this topic, but I do like sending more people to see the Dancing Links algorithms solving this (and other related problems, such as sudoku.)[1] The techniques in DLX cut the search space for the 8-queens down to just 1,048 board states. (For 13, the number of boards is up to 1,046,318) [1] http://taeric.github.io/DancingLinks.html http://taeric.github.io/DancingLinks.html

tacticiankerala 11y ago
8-queens : 0.19s user 0.09s system 127% cpu 0.222 total 12-queens : 0.21s user 0.11s system 129% cpu 0.244 total 16-queens : 0.29s user 0.10s system 119% cpu 0.325 total 20-queens : 2.79s user 0.10s system 102% cpu 2.826 total 24-queens : 7.50s user 0.10s system 100% cpu 7.533 total Thanks a lot for sharing the Dancing links algorithm. It looks really interesting. I wanted to try sudoku with backtracking,but now I would like to give dancing link a try!
- taeric 11y ago
  Are those times for finding a solution, or for all solutions? If all, that is truly impressive! Dancing links is a backtracking algorithm, just a nice way to optimize the backtracking.
  - tacticiankerala 11y ago
    It is for finding the first solution. Sorry that I didn't mention it.
    - taeric 11y ago
      No worries. I could have guessed, if I'd paid attention to how large of an N you looked at. :) Also, I should explicitly say thanks for sharing! It is fun reading solutions to this puzzle. Also fun to read Erlang.

HugoDias 11y ago

A solution for doing the same thing in Ruby: https://gist.github.com/hugodias/cf89ba138b986ddb3e7d https://gist.github.com/hugodias/cf89ba138b986ddb3e7d Time spent processing for 12 queens: 3.59 seconds

tacticiankerala 11y ago
Here is the benchmarking for 12-queens 12-queens : 0.21s user 0.11s system 129% cpu 0.244 total But, I see that you are finding all the solution. My program only finds the first solution.