BACKTRACKING ballet choreography (The Four Queens)

[@wearenakamas3428]

This is the reason I studied computer science

[@ZeroRiskAppetite]

Where was this during my Data Structures classes

[@RealChristopherRobin]

We want more!

[@hugoball4019]

this is so satisfyingly systematic

[@idoabelman1171]

"The Four Queens Ballet" really sounds like it could have been some classic ballet from the renaissance lol

[@tomi2592]

Beautiful! Amazing! For me it's the best of your newly uploaded videos, I just can't stop watching.

[@durvsh]

3 dancing queens were sacrificed during the making of this video.

[@melancholyRed]

4 dancing queens, actually.

[@abc-uz6bg]

Finest video I've seen. Thanks

[@FirstLast-fg5vh]

Recursion. Gezz One of the simplest concepts, and code, but g-damn so hard to do. I cooked my puter at 64 Queens. I mean it smoked. After 6 hours of 90% processer load.

[@dinohunter7176]

Superb, multumesc!

[@franciscorojas8025]

this is sooo bad ass.

[@shivangibalodia6601]

Hey you are doing an amazing job. Good luck to you. Looking forward to more such videos. :)

[@prathameshparulekar9247]

You all are awesome

[@caigner]

Hypnotic music!

[@Amitsa299]

good music and dance.

[@vpshastry]

I feel wierdly amused!! :D

[@sth128]

Maybe do a video on dancing links (Algorithm X - Donald Knuth) algorithm? It practically begs for it with that title... Though you might run out of dancers due to space complexity XD

[@cibisuren2334]

wow!

[@prathameshparulekar9247]

Amazing!

[@jennyjingxu1565]

awesome! want more!

[@dimitrisdimitriou6969]

This is amazing

[@letao12]

Nerdy boy with thick glasses walks into dance class. Girls: "Hi!" Boy: "I... um... do you want... I mean... I'm looking for... dancers for... uh... a class project" Girls: "Oh yeah? Which class?" Boy: "computer... science?"

[@letao12]

Girls: "Sounds fun, what do you need us to do?" Boy: "OK, so there's going to be this checkerboard, and you dance to the first square, and you dance to the next row, then you look at each other and you push her to the next square, then you look at each other again and you push her again, then look at each other again and wave, then you go to the third row and you look at her and she pushes you to the next square, then look at her again and wave, but then you look at her and she pushes you, so you go to the next square and look at her again and now she pushes you, then you go to the next square and she pushes you off the board, so then you stay off the board and she goes to the next square, and now you go to the third row, and you look at her..." Girls: "So, like solving the 4 queens problem using a backtracking algorithm?" Boy: "...... yes"

[@robertlozyniak3661]

The dancers must have a good amount of memorizing to do to keep the timing, etc., right in their heads, as there do not appear to be visual cues as to when they are to "wake up".

[@nydydn]

They don't need to memorize the timing. That's what the music is for, to keep the rhythm.

[@beeble2003]

@@nydydn They need to memorize the timing in the senses of remembering what part of the music they wake up at. Actually, though, I don't think they need that. When they're kneeling with their heads bowed, thyey can look behind them.

[@tmjcbs]

It's a good thing they didn't use Sudoku, another candidate for the backtracking algorithm...

[@viniciuskf1741]

Bah show de bola

[@The_Foreman]

Just a quick Question that'll never get answered. After the first fully queen checks her first 2 squares (half the board) I think any other possibilities would be mirrors of all previous answers. If it were to backtrack down to her, you can half the time by breaking if she goes over the halfway point.

[@yaroslavpanych2067]

Well yes, in this particular task there is 1 other solution, and it is mirrored to the first. But only in this. Depending on task, it is possible to run algo until 1st solution and quit, but usually it is coded to generate each and every possible solution (or reach state where no solution is possible). Especially when the best solution is required to be found. You must understand, there are 2 cases when algo can stop: 1) found solution(s), don't need anymore - as shown here 2) found all solutions, i.e. backtracked to state 'before-start', in our case, 1st queen explored all 4 cells, and backtracking can step back anymore. You cannot make conclusion during any other stage. If you know about certain properties of solutions, you can 'optimize' it, but it is task specific optimization, which cannot be applied to other tasks.

[@The_Foreman]

@@yaroslavpanych2067 I didn't mean that the only other solution would be the mirror, only that no matter the size of the board the first queen would only have to go halfway across before all possible answers would be found. At which point you can stop running the simulations. If we are changing the shape, or adding dimensions, no matter the situation rules would have to change. I was simply making note of an interesting aspect of the current board at play.

[@frechjo]

@@The_Foreman If you restrict the first queen to the fist half of the row, you eliminate all mirror solutions on one axis (from the two axis of symmetry and 4 rotations). But the point of the video is to show how a backtracking search algo works in general. It's a general technique applicable to many different kind of problems, not just this specific one, so any form of heuristic or optimization you could introduce to solve the n-queens problem would detract from the intention. If your intention is to just to solve an fixed sized n-queen problem, there'll be many variations that could be more efficient than a general backtracking method. For big n's, for instance, you could use constraint propagation.

[@paulschuler1459]

I was surprised you did not have the three dancers on the right get up again and move around over the top to the left. Eventually, the same result would have been achieved.

[@nydydn]

when backtracking is explained, a teacher would say that a candidate is abandoned after no suitable solution is found for that candidate. Of course, in a computer the candidate is just a bunch of bits (and not even that), and all the bits are still in your RAM, but this ballet follows strictly the explanation that is apparently most understandable by humans.

[@superniokas]

party pooper

[@KrzysiuNet]

"Needs more flanger" - The Bruce Dickinson. (but honestly, if they would ease a bit on flanger, it could be a pretty nice version of C&M)

[@Mojzesz66]

How can I find the soundtrack?

[@osztianpalmarozalia4947]

Prokofiev - Dance of the Knights

[@wun_zee3599]

@@osztianpalmarozalia4947 I find that funny concidering the name of the puzzle.

[@boy_with_thorn]

I still dont understand how to find all possible combinations using this

[@tonydekker7792]

Record the solutions you find, but just keep backtracking.

[@boy_with_thorn]

@@tonydekker7792 ohh, got it, thanks!

[@jakestuck0309]

I wonder how knapsack would look as a dance.

[@simonebertolucci5152]

This dance is popular but inefficient, as it takes 2^n steps. A less naïve approach could complete the dance in polynomial time.

[@mertaliyigit3288]

The problem is NP-complete

[@simonebertolucci5152]

@@mertaliyigit3288 I was convinced of that, too! But apparently, that is a common misconception. dl.acm.org/citation.cfm?id=101343

[@oooBASTIooo]

@@simonebertolucci5152 That is a probabilistic algorithm.. As it clearly states in the abstract.

[@xerxes8075]

Dimmu Borgir?

[@SmashhoofTheOriginal]

Me at 2am

[@LukasThiersch]

It's a bit slow... Is this Vista?

[@comofuncionaelmundo3895]

Ahora entiendo porque el problema de las mil reinas es NP Hard

[@Eu_Sunt_Dracul]

Bliss

[@4-7-5anhbao5]

Đã xem

[@ayamirisukahyejunghyuneuneun]

can upload sort algthm agn p,les

[@farche2]

That's more like brute force enumeration than backtracking.

[@nydydn]

"Backtracking" is a very well known name for the algorithm they're describing. Feel free to name it however you feel appropriate, but by convention backtracking is what they dance.

[@beeble2003]

No, it's backtracking. Brute-force enumeration would put queens at positions 1,1,1,1 and check for validity, then at 1,1,1,2. Backtracking never even considers those states, as it rejects anything beginning 1,1 without looking further.

[@garychap8384]

More fun at 2x speed ... ... but anyone that codes an n-queens solver like this, should probably switch career : / And if they also use call recursion, then they should be banned from using compilers for life XD

[@beeble2003]

No reason not to use recursion. It's natural, and the recursion depth is very limited.

[@bruvvereccles5847]

Pity you ruined the music with that clicky accompaniment.

[@ratlinggull2223]

I love how you called the high hats