Show HN: NQueens problem solved using backtracking in Elixir lang
1–8 of 8 posts
Re: Show HN: NQueens problem solved using backtracking in Elixir lang
#2It 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)
Re: Show HN: NQueens problem solved using backtracking in Elixir lang
#3A solution for doing the same thing in Ruby: https://gist.github.com/hugodias/cf89ba138b986ddb3e7d
Time spent processing for 12 queens: 3.59 seconds
Re: Show HN: NQueens problem solved using backtracking in Elixir lang
#4It 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…
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!
Re: Show HN: NQueens problem solved using backtracking in Elixir lang
#5A solution for doing the same thing in Ruby: https://gist.github.com/hugodias/cf89ba138b986ddb3e7d Time spent processing for 12 queens: 3.59 seconds
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.
Re: Show HN: NQueens problem solved using backtracking in Elixir lang
#6It 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…
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 wo…
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.
Re: Show HN: NQueens problem solved using backtracking in Elixir lang
#7Earlier quoted context omitted.
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 wo…
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.
It is for finding the first solution. Sorry that I didn't mention it.
Re: Show HN: NQueens problem solved using backtracking in Elixir lang
#8Earlier quoted context omitted.
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.
It is for finding the first solution. Sorry that I didn't mention it.
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.