A program that solves the N queens puzzle
In the repository, you can find 2 folders: 'NQueensMagic' and 'NQueensMagicConsole'. The former contains the core library, and the latter simply connects the program to the Windows Console UI. To get the executable, download the latest release. Keep in mind that the executable is targeted for x64 systems.
So I was figuring out how to program my own chess engine, and suddenly I stumbled upon an article saying that some Math institute offers $1M to anyone who can 'solve a chess puzzle'. It had something to do with the P vs NP problem, and the thing was a bit trickier than what the title suggested (who would guess).
An article on the subject (not the one I saw originally)
P vs NP
Of course, I didn't expect to come up with a solution to the problem. But it made me curious: I thought, maybe I could experiment and arrive at some interesting conclusions. 'Thanks' to the media, I misenterpreted the problem thinking that one needs to invent an algorithm that finds ALL solutions to the puzzle (starting from an empty board) really fast. For example, the standard 8 queens puzzle has 92 unique solutions. So, to my understanding, the algorithm was supposed to find all of them, and then store them somehow. That wasn't quite the case, and I'll explain in a minute.
At first, I tried to come up with a non-conventional way of placing 8 queens so that the combination ends up being one of the 12 fundamental solutions. Interestingly enough, I found that if you take one solution, and shift all the queens one square in any direction (the utmost queen jumps over and ends up on the other side), you can get another fundamental solution! Just by doing that, I managed to find 8 solutions out of 12. So if you're learning chess and your teacher ever asks you to solve this puzzle in a number of ways, you can use this method. Anyway, as you can imagine, there is still a couple of problems. First of all, not all solutions can be found this way. Secondly, we still need to find the first solution somehow. And lastly, it all becomes much more complicated on larger boards: the algorithm has to change depending on N. So I gave up on that idea.
Eventually I decided: why not use the good old backtracking method but somehow make it more efficient than... well, anything that implements a 2D array of some sort? I just wanted to get some meaningful and stable results. Again, I wasn't trying to solve a millennium problem: I was practicing, and that was it. So I sat in front of the chessboard and thought: 'If only I could use bitboards here, but at the same time be able to scale the board'. And then an idea occured to me which seemed brilliant: why the hell not make an array of bitboards so that each bitboard acts like an individual element in a matrix? Then I started coding, and what you see here implements this very idea.
It was only after I finished the 1st version of the project that I realised: the original problem was not about finding all of the solutions per N. Instead, it stated: you either prove that there is an algorithm that can solve the completion(!) puzzle in a polynomial time OR prove that there isn't one. The 'completion' part here is key. What this means is basically another version of the puzzle in which you need to complete a given set of queens, i.e. having some of the queens already placed on the board, place the rest without moving the original ones. Now it seemed more like Sudoku. My algorithm was exponential, not polynomial (alas), but I modified the program so that it was now able to perform both tasks: either finding all solutions, or completing a randomly generated or a specified preset. I found the results to be quite interesting, and they are illustrated in the corresponding section of this document.
If you have read the introduction, you already get the idea that the core principle of this program is behind a scalable array of bitboards. The array is 1D but it can easily represent a 2D matrix - in the same way as a bitboard represents a 2D chessboard. But there is still a catch: all is good when N is a power of 8 (an Int64 in 2D-perspective has a side of 8) but what if that's not the case (N = 5, 12, 47, etc)? Because we can't just cut the utmost bitboards in half or in 3/4 or 5/8. Well, actually we can: all we need to do is to mark the redundant bits as 'occupied' and they'll be ignored. Now, for example, a 9x9 board can be represented by 4 bitboards, and 3 of them would mostly contain redundant bits. Based on that, we can draw the conclusion that the algorithm will work most efficiently with N being a power of 8. But really, the difference is negligible compared to the effect of larger N values.
Now that we have this board representation, the algorithm - which is essentially a backtracker - has to do much less work! Instead of iterating through huge arrays of individual squares, it iterates through bitboards and performs bitwise operations. This works basically the same way as chess engines like Stockfish.
The final key point is precalculation. If you can calculate something outside the loop then there is no reason not to. And if we calculated attack rays for each queen each time we place it then it would be a huge drag. Instead, we precalculate all attack rays (and some other variables) BEFORE we start searching, and store them in a big hash table (or a dictionary). This way, when we actually search, all we need to do is to access the value from the hash table and that's it. Well, Stockfish does that too, I know. Although it's important to note that with an increasingly large N our memory usage blows up - so it's better to watch out for it in a resource monitor of some sort. If you want some really huge N then it would be logical to reconsider the way attack bitmasks are stored.
The above key principles work universally for both modes. The only difference is that in Completion mode we have some pre-defined set of queens. There are 2 ways of defining a preset: random generation and custom definition. The latter should be pretty self-explanatory. The former requires another algorithm that does exactly that: generates a preset randomly, i.e. places queens in random spots until it comes up with a valid combination (with no queens attacking one another) of some size. The size, i.e. the number of queens in the preset, can be specified by the user. By default it's N/2, so that the search algorithm needs to complete half of the task, if you will. And of course it needs to find only 1 solution, in contrast to the first mode where the algorithm can potentially look for millions of different solutions. This fact makes it possible to handle much larger boards in Completion mode.
But here is the fun part: because of the random nature of presets, the time it will take the algorithm to complete different presets is totally unpredictable (given the same size and N). Basically, if you're lucky you can get a solution for a 500x500 board in a fraction of a second, and if you're not then you'll have a hard time waiting for the algorithm to solve a mere 72x72 puzzle. I guess, this is the nature of NP-problems.
Suppose the algorithm came up with a solution. But how do we read it? Here serialization comes into play. The array of bitboards representing the solution gets converted into a string of Y-coordinates, i.e. numerical values each indicating the rank where a particular queen is located. That's how all presets and solutions are displayed in the console, and that's how they are saved in files. There is also deserialization which helps converting a user-defined preset into a matrix.
And that's the general idea. More information regarding implementation details can be found in the source files.
I ran the program on a machine with a dual core CPU (4 threads, 3.6 GHz) and 8 GB of physical memory.
With N = 16, all 14,772,512 solutions were found in about 20 seconds. It actually took the program more time (32s) to serialize all those solutions and save them to almost 1,500 files (680 MB). So I didn't see the point of increasing N more than that, as it would create a ton of files and probably cause memory issues.
In Completion mode, as I've said, everything is random. The biggest board in my case was 512x512, and I once got a solution for it in 57 milliseconds. The precalculated attack masks took 10 GB of memory. It's important to note that the number of pre-placed queens in that case was 480 (93.75% of N). Be it 256 or even 400, I wouldn't be lucky enough to get any result in a reasonable amount of time. So you see the problem here.
You may say that C# isn't the best choice for this kind of project, and that C++ or C would be a better pick for ultimate performance. And I would agree. But I simply know C# better, and I specifically studied it during development. Probably some day I will convert this whole thing into C++. But ultimately I think .NET Framework isn't that bad.
Well, the end result seems a bit useless. And I haven't solved any millennium problem yet. However, I can think of a number of different fields where this program can be of use. For example, I imagine it could serve as the basis for some weird encryption algorithm, or indeed a way of arranging objects of some sort, or it could be converted into a Sudoku program. Maybe you see a great opportunity for this project. Or maybe you think my implementation is horrible, and you have a better idea. Either way, please feel free to contact me if you have any suggestions or questions.