The n-queens problem is about arranging n queens on an n x n chessboard such that no queen attacks another queen.
It turns out that this is quite a common example for using a backtracking algorithm. However my initial solution involved going through permutations of the column positions for each queen. Here are my whiteboard notes and source code for this solution and then my implementation of a more traditional backtracking solution further down:
And here is my explanation and implementation of backtracking solution (iterative):
Structured bindings are a useful new feature in c++17. They are particularly handy where you have multiple return values. Here are some examples showing how things have evolved over different versions of c++:
Here are some basic logic gates and how we can combine them to get an XOR:
In order to perform addition of arbitrary length binary numbers we first start with creating a Half Adder, which can add two single binary bits to result in a single two bit binary number. We can then create a Full Adder, which allows us to add three binary bits that results in a single two bit binary number. We need to add three bits as that allows to add two bits of two numbers and a carry bit. Next we chain together a sequence of full adders to add two binary numbers with any number of bits. We can optimise this to use bitwise operators to do ANDs, XORs and bitshifts to do the addition and carry operations on a sequence of bits. We can multiply numbers by doing repeated shift and add operations. Here are my whiteboard notes for all of these:
A few fiddly cases of exponentiation to deal with in this problem. A simple O(n) solution is fairly straightforward but that will not pass some of the leetcode test cases. An implementation that uses binary exponentiation will work in O(log n) time and will pass the leetcode tests. One other fiddly edge case was the test case that used INT_MIN as the exponent, which does not allow us to *= -1 for negative exponents, so I had to use long int to expand the range of the exponent. My original binary exponentiation implementation was messy, so the elegant solution below took inspiration from https://www.geeksforgeeks.org/write-an-iterative-olog-y-function-for-powx-y/
The most efficient way I could think of to solve this problem was to use an unordered_multimap to store sorted strings as keys and the original strings as values. This will then automatically provide the groupings we need. Here are my whiteboard notes:
The idea with my solution is that you work your way through layers of the box, starting with the outside layer and then moving inwards. For each layer we step through four points at a time, starting at the corners and then working our way around. In the solution below I store those four points in an array and then I call std::rotate() to shift the numbers. I felt this was logically slightly simpler. An optimisation on this would be to use a single temporary variable to store one of the points and copy the other points to each other.
The obvious way to solve this is to repeatedly call next_permutation() from the standard library. Another way to solve it is to implement what next_permutation() does and I have done that in a previous solution: https://www.adamk.org/leetcode-31-next-permutation/
I thought I would have a go at solving this by using the nature of recursive calls to go through combinations. The following is a logically simple but not very efficient way of doing it: