Solving the puzzle is not the challenge alluded to. The challenge is that given any starting position with queens already placed, find a valid solution by adding more queens. A notable related problem is enumerating and counting all valid solutions. To date, it has been shown by brute force that a 27x27 chessboard has over 243 quadrillion solutions; removing all symmetrical solutions results in about 29 quadrillion. The brute force work took about 7 years with a massively parallel array of custom hardware (written to FPGAs).
To provide some context to the size of the numbers involved, it would take a modern CPU (single-core at 4.5 GHz) about 4 years just to increment a counter as fast as possible from 0 to 29 quadrillion. That is the time estimate just for the work involving the counter; nothing more. It's also hopelessly optimistic, since that assumes you already have a list of all 29 quadrillion solutions, or that there are zero false positives or any instances of wasted effort.
Remarkable, isn't it? And that's just for a 27x27 chessboard. Considering all of the other work that would be necessary as part of the algorithm, it's safe to extend the runtime by a factor of 1,000. That brings the total to 4,000 years of constant work to find and/or test all solutions. Of course you can always divide and conquer and use specialized hardware as the Q27 researchers did. Then it only takes 7 years to do all of the work.
Now let's talk about the 1,000x1,000 chessboard mentioned in the article. Finding a solution to this board is trivial. I wrote a little program in Rust that computes the solution in 5 microseconds. It took 2.3 milliseconds to verify the solution on the same hardware. Yeah, but that's boring! What about counting the number of solutions?
For that I have a very simple proposal; an estimate will get us in the right ballpark. If anyone could find some black magic voodoo to reduce the estimate to within some acceptable margin of error, then the problem of counting n-Queens would be arguably solved. I know of no such reduction function, but coming up with an estimate is trivial.
There are approximately 2.2 * 10990 (+/- a few orders of magnitude) unique solutions for the 1,000x1,000 board. This number is larger than the total number of fundamental particles in the observable universe; in fact, it would take more than 10 billion observable universes to have enough fundamental particles to get even close to this number. If you also include the number of symmetrical solutions, then the result grows even more incomprehensibly.
That is the problem worth $1 million. I wouldn't be surprised if they bountied infinity dollars, since these numbers are strictly too big to deal with, and the black magic voodoo function is probably mythical.
So that's what I got distracted by. In relation to my game, I have so far nothing exciting to show. But I could perhaps entertain a few thoughts and provide a small bit of insight into what I've been doing since completing the dithered gradient shader. Below is a video of a thing I made with shadertoy. It doesn't serve much purpose on its own, apart from being kind of pleasant to look at for a few minutes.
I didn't invent anything shown in this video. Actually it's just a combination of two published shaders that I liked. One that creates a sinusoidal wave pattern, and the other produces ripples like raindrops. The wave pattern is incredibly subtle here, and I toned it down quite a lot from the original. The ripples were also toned down from its original, and slightly increased in frequency. What I like most about it though is this description of how the ripple effect works.
You might speculate that I want to include this shader in the game. Of course I do, it would fantastic! Mapping this shader to a flat surface for simulation of a puddle would be very satisfying, indeed. For that to happen, I need to do some more refactoring on the 3D renderer. Most importantly, I need to implement an API similar to OpenGL ES. This is no trouble really, just a bit of grunt work.
I also created a second shader, but it's not worth even showing at the moment. A written description will have to suffice. The opening scene in the game will contain sunbeams peeking through the darkness. The shader attempts to mimic the shadows of tree leaves as they blow in a gentle breeze through a shining sunbeam. It's really just a couple of sine waves added together and softened around the edges, but if you use your imagination, it kind of works! I have no idea what it will look like through the dithered gradient, though. And it remains to be seen if the effect will pan out well enough to include.
On the 3D scene front, I've experimented with Blender's Python API. Being familiar with Python, I'm rather disappointed with what Blender has to offer. On the bright side, I guess it works, and it could always be far worse. What I have right now is the basis of a script to export the scene to a format that is easy to consume in the game. It is a custom format because, though Wavefront OBJ and FBX would technically work, they are not specialized enough to contain all of the information that the renderer needs.
In short, I want the export format to be as close to the internal representation as possible so there will be minimal processing required, and fewer lines of code to execute at runtime. A good example of the kind of preprocessing required is the tessellation of each mesh; the process of breaking every quad into two triangles. Trivial, but why not just do that automatically when I save the scene in Blender?
I also considered using Unity 3D as a level editor, but I feel like that will introduce unnecessary steps in my asset pipeline. Both are roughly equally capable in terms of features for game development and customizable with scripting, but Blender is without a doubt much better for modeling. What it lacks can probably be fulfilled with scripts.
And that's about it! I laid out a handful of planes in a scene and printed all mesh vertices to the terminal with Python. It's a couple hours away from exporting a usable scene format. I'm considering using CBOR for the on-disk representation, since I got a chance to use it in Rust while playing with the Queens Problem, and it's pretty much perfect. There are pure-Python implementations for CBOR, and that's all I'll really need for Blender.
These next few tasks are busywork, so I'll have to get over the motivation hump to get to something interesting. I'll try to keep up on my blog at least once a week. For all two of my readers (you know who you are! And thank you.)
No comments:
Post a Comment