What kind of algorithm is this? ive been learning about some hill climbing and best first searches in university lectures about ai and i wanted to know how you would describe it
Exactly! This is a hill climbing algorithm. The algorithm starts at a random state and repeatedly improves upon it (or climbs the hill 😉). It does so by picking the best state it can reach by moving a single queen. There are many variations on hill climbing algorithms. In the end of the video we look at a technique which can sometimes be used to get better results. Thanks for watching 😃
Glad you like it 😀 It's not A*, it is a hill climbing algorithm. I can't share the code with you at the moment, sorry. Definitely read up on hill climbing algorithms - they are pretty simple to understand and implement. Best of luck and thanks for your comment 😊
That's a great question! When the program starts, you can generate a list containing all moves. Each move can be stored as a pair (r, c) where r is a row index and c is column index. The move (r, c) says "move the queen in row r to column c". For each step in the algorithm, you shuffle the list of moves and then generate the resulting states one by one. This approach will give you a truly random state generation order, but there is a problem with it. There are O(N^2) moves, so shuffling at every step is slow. Instead, I decided to use two arrays called rowOrder and colOrder. Both arrays contain the N integers from 0 to N-1 (in some random order). To generate the states, I loop over rowOrder, and for each row, try all columns in colOrder. This move ordering is not completely random, but it is much faster to shuffle these two arrays at every step. Hope this makes sense! 😀
Unfortunately not 😉. The algorithm used here appears to be quite efficient in practice but there is no theoretical guarantee about it's running time! Thanks for watching 😀
the N=NP is not about how many complexity you add to the problem i think, i mean, in this 1000 queens example is not important if its 1000, 1million or infinite queens, or the time you need every complet solution, the N=NP problem target is another thing related to this process, is easy to check the results but harder to produce that results, if the times it takes for check for every solution is the same than the time it takes to find that solution, thats it i think
This video was very well-made. You earned a new sub.
Thanks! I appreciate it ☺
Excellent explanation and the graphics really helped.
Thank you 😀
this video is super interesting!!
Thanks! 😊
Can I get access to the source code of this problem
in the fastest way how did you know the number of conflicts if we have how many queens in each column, diagonal
very good video, chess search algorithm will be a nice too, ex. minimax versus other algorithm or mix of them.
Buena tarde. No ha aplicado para ganar el premio del Instituto Clay?.
Excelente trabajo.
Really nice video. Godt arbejde.
Mange tak!
This a great video :)
What kind of algorithm is this? ive been learning about some hill climbing and best first searches in university lectures about ai and i wanted to know how you would describe it
Exactly! This is a hill climbing algorithm. The algorithm starts at a random state and repeatedly improves upon it (or climbs the hill 😉). It does so by picking the best state it can reach by moving a single queen. There are many variations on hill climbing algorithms. In the end of the video we look at a technique which can sometimes be used to get better results. Thanks for watching 😃
Hello, I liked ur video, is this A* algorithm? Can u please share the code if it's can be shared
Glad you like it 😀 It's not A*, it is a hill climbing algorithm. I can't share the code with you at the moment, sorry. Definitely read up on hill climbing algorithms - they are pretty simple to understand and implement. Best of luck and thanks for your comment 😊
@@OttoBotCode np u too)
This might be a dumb question, but if possible can you give a tip in how to generate all possible children in a random order?
That's a great question! When the program starts, you can generate a list containing all moves. Each move can be stored as a pair (r, c) where r is a row index and c is column index. The move (r, c) says "move the queen in row r to column c".
For each step in the algorithm, you shuffle the list of moves and then generate the resulting states one by one.
This approach will give you a truly random state generation order, but there is a problem with it. There are O(N^2) moves, so shuffling at every step is slow.
Instead, I decided to use two arrays called rowOrder and colOrder. Both arrays contain the N integers from 0 to N-1 (in some random order). To generate the states, I loop over rowOrder, and for each row, try all columns in colOrder. This move ordering is not completely random, but it is much faster to shuffle these two arrays at every step.
Hope this makes sense! 😀
Isn't this video solving the N=NP problem?
Unfortunately not 😉. The algorithm used here appears to be quite efficient in practice but there is no theoretical guarantee about it's running time! Thanks for watching 😀
the N=NP is not about how many complexity you add to the problem i think, i mean, in this 1000 queens example is not important if its 1000, 1million or infinite queens, or the time you need every complet solution, the N=NP problem target is another thing related to this process, is easy to check the results but harder to produce that results, if the times it takes for check for every solution is the same than the time it takes to find that solution, thats it i think
the np problem is related to finding all possible configurations , not finding one .