News for hackers. Stuff that matters.
Re:Jq Internals: Backtracking (2017) by brad0 on Wednesday October 05, 2022 @06:35PM (#33102067)
Does anyone know of a visual representation of backtracking? Either video or images, I'm not fussed.
Re:Jq Internals: Backtracking (2017) by roncesvalles on Thursday October 06, 2022 @02:03AM (#33104904)
Backtracking is a stone's throw from the mathematical concept of permutations so it might be better to look up visualizations of that and work from there. This one seems good: https://pebreo.github.io/combinations-visualization/

The number of permutations of n items is n!, because at every position you can place one item from all the items that haven't already been placed. Backtracking basically recursively produces all n! solutions (where every recursion depth is one position) similar to DFS brute force enumeration with the only difference that it also continuously evaluates partial solutions and short-circuits if it detects a partial solution that is guaranteed to make any complete solution containing it invalid.

E.g. if you want to enumerate the permutations of 4 people standing in a row, there are 4!=24 ways to do it. However, if you add the condition that Alice can't stand next to Bob, you can short-circuit the enumeration early as soon as you detect that Alice and Bob have been placed together (such as Alice-Bob-?-?)

You could also have more complex scenarios where every position has its own disjoint set of items to choose from.

What you do with the enumeration is up to you. Maybe you just want to enumerate and display all possible permutations. Maybe you just want to produce the best or k best as determined by some fitness function.

Re:Jq Internals: Backtracking (2017) by zwkrt on Wednesday October 05, 2022 @07:33PM (#33102552)
This blog post has a nice visualization of sudoku solving using backtracking. https://medium.com/analytics-vidhya/sudoku-backtracking-algo...

Although the case they use is almost perversely simple. Imagine in a 'real' sudoku that each number might need to be backtracked multiple times, such that the algorithm is regularly going almost back to the start.

Edit: here's a classic one trying to solve the 8 queens problem: https://commons.wikimedia.org/wiki/File:Eight-queens-animati...

Re:Jq Internals: Backtracking (2017) by brad0 on Wednesday October 05, 2022 @08:47PM (#33103032)
Thanks! I really liked this tree from the blog, it made it quite clear.

https://miro.medium.com/max/786/1*Q-DyKa25eozOeMdN5YQONA.png

Re:Jq Internals: Backtracking (2017) by lalwanivikas on Wednesday October 05, 2022 @08:56PM (#33103085)
Marty Stepp from Stanford had the best videos on this but they took it down from YouTube ¯\_(ツ)_/¯
Re:Jq Internals: Backtracking (2017) by djbusby on Wednesday October 05, 2022 @09:17PM (#33103217)
Re:Jq Internals: Backtracking (2017) by dkjaudyeqooe on Wednesday October 05, 2022 @09:44PM (#33103367)
Don't have one to hand, but it's basically walking a tree depth first, where sibling nodes are the choice points.