Queens on LinkedIn is darn cool, but it sucks to wait everyday
so I made my own Queens with a few awesome twists
If you don’t know yet, LinkedIn has been hosting its own games since May. One of them is a puzzle called Queens.
In Queens, you have to place certain flags according to a set of rules. If you put them in the right places, you will win.
It sounds simple, yet I’m addicted. I’ve been on a 76-day streak, played 187 times since it was released.
The only downside about this game is you can only play once per day. Like a NYT crossword.
Therefore, I decided to build my own Queens so I can play whenever, but of course, all of my creations come with a twist, or a few:
The compute-intensive game logic is going to be implemented in C, ported to web through WASM.
Must be done with vanilla JS.
No external framework is used, the only exception is TailwindCSS for styling.
What is WASM?
“The computational model of WebAssembly is based on a stack machine. Code consists of sequences of instructions that are executed in order. Instructions manipulate values on an implicit operand stack. ” - WASM specification
WASM is basically assembly for websites. It is in the name.
All programming languages can be compiled to WASM and run natively on the web. However, unlike plain cross-compiling, WASM brings unparalleled speed compared to JS.
This is thanks to its brilliant specifications — which details the abstract machine it runs on and its close-to-hardware instruction set — its “intermediate representation” nature.
Fun fact: WASM runs in an abstract stack machine. Instead of using registers like normal computers, it just push/pop values into the stack. This makes it relatively simple but also has potential issues.
Why WASM for a game?
WASM has changed the web since it was introduced. We don’t encounter it much in the day-to-day operations of building products. But it has made huge impact.
For example, do you know that the smooth user interface of Figma is completely on WASM since 2017 — only a few months after WASM was released.
Or Unity has supported WebAssembly target a few years ago for huge speed improvements.
In compute-intensive applications, WASM can bring incredible impact, which is why it is perfect for making Queens.
Introducing BinkedIn Queens
Since I’m a no-bs person and a show-the code guy, I’m going to start with giving you the source code and the site first.
If you only want to try the game, you can do that here. If you want to read the source code, you can do that here.
The game is entirely written in vanilla JS, only exception is using TailwindCSS because I don’t want to style everything by hand. The logic is written in C, then compiled to WASM.
I will walk briefly through the algorithm in the next section.
Backtracking in Queens
In Queens, you have a colourful board with 2 simple rules:
Exactly one queen can be placed in each row, column, and color region.
Two queens cannot touch each other, not even diagonally.
If you have done competitive programming before, you must have been like “hold up, is this the N-queens problem?”.
To which I’ll answer, it is, a variation.
In N-queens, you have to place N chess queens on an N×N chessboard so that no two queens attack each other. This problem can be solved in multiple ways, the most simple is by backtracking.
Put in layman terms, to solve a board, we’ll brute force it by testing all possible solutions.
In our case though, we’ll use this algorithm not to solve a board, but to generate boards that can be solved. This is relatively straight-forward and quite a challenge so I’ll leave the code here for you to binge.
The worst-case time complexity of this algorithm is O(N!), which makes it perfect for the category of a compute-intensive task.
For the sake of benchmarking, I wrote the algorithm in both C and JS. In the below graph, you can see that as the board grows, the time also increases.
While the graph is not in the shape of a factorial function, it shows that the time is increasing somewhat exponentially.
What is special about my Queens?
Well, I guess they are all pretty. But jokes aside, my Queens have something that LinkedIn don’t have:
Unlimited board generation: no longer capped by daily limit
Customizable sizing: you can play 500x500 board that is generated in less than 1 second.
You can find the source code and website mentioned earlier above.
Endnote
I wrote this article to introduce you to the potential of using WASM in your product.
The use cases of WASM doesn’t end at compute intensive stuff. It can literally be used to run cross-platform code, like running your C++ code on client side, without cross-compiling it to JS first. This can tremendously reduce your development time. Not to mention the potential of porting native projects onto the web.
Find a list of supported languages here.