Solving N-Queens under 3 secondsUsing the Min-conflicts AI algorithm to quickly solve N-QueensCarlos GonzalezBlockedUnblockFollowFollowingJan 6One Solution for N = 8 QueensN-Queens is a famous computer science problem.
The goal is to place “N” Number of queens on an “N x N” sized chess board such that no queen is under attack by another queen.
There’s plenty of solutions to this problem, but there’s one particular algorithm which is my favorite: Min-Conflicts.
Min-conflicts will randomly choose a queen, and move it to a place on the board where there are less conflicting queens than there are now.
If there is no such spot, it will pick another random queen and continue to iterate.
Seems pretty simple right?Using Min-Conflicts we would move to the board with Score = -3Let’s go ahead and try to implement this on an arbitrary N x N sized board.
I like to work from the top down, so I’ll go ahead and write the solution using min-conflicts and then I’ll go back and fill in the functions that I haven’t written yet.
If you prefer the opposite way of working, feel free to skip down to the N-Queens class section and come back here when you’re done.
Min-Conflicts ImplementationTo start, let’s set our board to be sized 8 x 8 and create a soon to be written NQueens object:Now, we can start our main loop that continues iterating until none of the queens are conflicting.
We will only be working with one queen per iteration so we initially set our minimum number of conflicts for a single queen to a value that will be guaranteed to be minimized.
We know “n + 1” will always be minimized because there are at most “n – 1” conflicts for a single queen.
Then, we pick a random queen and obtain all the positions that our chosen queen can be moved to.
Finally, we initialize the position we will be moving our queen to:Next, we have our largest but most important chunk of code,Let’s break this down.
First, keep in mind that we are still inside the while loop from our past chunk of code.
With that in mind, we start by iterating through all of the possible positions that our chosen queen can move through.
During every iteration, we move the queen to the chosen position and evaluate the number of conflicts at that position.
If there are less conflicts than our lowest number of conflicts so far, we store that position and store that new lowest number of conflicts.
Then we move our queen back to its original position for the next iteration.
Once we have iterated through all of the available positions, we move our queen to the position that had the lowest number of conflicts.
If there are still conflicts, we continue to iterate through our outer while-loop.
I like to go ahead and print out the solution that was found once the while loop terminates:Check at the end of this post for the full source code for this part.
N-Queens ClassThis section is only for those who are curious as to how I implemented the N-Queens class.
Feel free to skip it if the algorithm above made sense.
First, I represented the problem by setting up the board as a 2D array with randomly placed 1’s where the queens were located, and 0’s everywhere else.
Also, I have an array that keeps track of the queens’ positions.
Now, looking at our min-conflicts code, there are several functions we need to write.
allQueensSafe(): which checks if there are no conflictspickRandomQueen(): which returns a randomly chosen queenavailablePositions(): which takes in a queen and returns all the positions that queen can move tomoveQueen(): which takes in an empty position and a queen’s position and swaps themspecificQueenConflicts(): which returns the number of conflicts a given queen hasprintBoard(): returns the position of all queens on the boardallQueensSafe() iterates through every queen’s position and checks to see if that queen is being attacked by another queen.
It does this by checking to see if there are queens in the same row, column, or at a diagonal to it.
Here’s the allQueensSafe() function:Which calls the UnderAttack() function:which call the 3 functions that actually check for conflicts:pickRandomQueen() simply returns a random queen from our array of queens:availablePositions() returns all of the positions that queen can move to.
I chose to only move queens up and down in their respective columns since this would greatly speed up computation.
moveQueen(): takes in two positions, one current position of a queen and the destination of that queen.
This is implemented by changing the 2D positions array from a 0 to a 1, or vice versa and updating the queens position array.
specificQueenConflicts(): takes in a queen’s position and returns the number of conflicts that queen has.
printBoard(): prints out the position of all queensWow… That was a lot of code… But that’s it!.We did it!.????Closing Thoughts And Full CodeWhile N-Queens may seem like a basic algorithm, it’s used heavily in practice.
One example is that NASA has used it to reduce the time it takes them to schedule all of the requests to use their telescopes so that there are no conflicting times.
Apparently using Min-Conflicts brought their total scheduling time down from almost a day to around 10 minutes.
That’s pretty cool stuff!.Here’s the full source code for the min-conflicts algorithm:And here is the full source code for the NQueens class:As a final note, min-conflicts can sometimes take very long to converge because the randomly chosen positions for the queens are simply poor guesses.
However, those are anomalies so if you find that it’s taking longer than a second or two, just terminate the program and re-run it.
Sometimes I have to do this a couple of times before it quickly terminates with a solution.
If you have any questions, let me know below!Note: The full github repo can be found here.. More details