Super Queen

In the chess literature amongst some of the most theoretical chess scholars there is a concept of the Super Queen, or in abbreviated form, SQ. SQ is a hypothetical variation of the game whereas we give an extra power to the already almighty queen: now in addition to the bishop- and rook-like moves, the queen also inherits the knight-like move (colloquially, the queen can now jump). Such a small variation of the game would actually cause a massive restructure of not only the overall dynamics of the game, but also every single strategy and fundamental would have to be revisited and reformulated: how would this impact the opening? The development phase? The gambits? The defense strategies, the clustering strategies, the tempo, the end game, the pieces promotion, the pieces sacrifice (the queen sacrifice), and so on so forth? An analogy to such an event can be draw in the realm of mathematics: when the root square of minus one was suddenly given a life in the form of the “number” i, a brand new and complex branch of the mathematics (the complex numbers) was born. Theoretical chess scholars just love contemplating the idea of the SQ and what implications that would have to the game of chess. For now, this remains highly theoretical. But who knows, one day it might come to life, just like sqrt(-1)….
The following problem deals with SQ: suppose you’re given a chess board of NxN where 0 < N <= 100, randomly filled with one of these four possibilities: the starting position of a SQ, or “S”; the position of the adversary King, or “K”; positions already filled with some (any) piece, or “X”; positions not filled by any piece (empty cells), or “.”. Your job is to calculate the minimum number of movements, if any, to move the SQ in such a way to capture the king “K” without capturing any other piece along the way. If there isn’t such a path, just print a message saying “not found”.
The use of backtracking is an alternative to solve the problem, and its implementation is quite straightforward  as seen in previous posts. However, backtracking enumerates all possible solutions which won’t be practical here since it would cost us 2^100 to enumerate them all, or 1/3 of the number of atoms in the universe. That would take an enormous time for sure.
In this particular case a better approach would be to use a simple Breadth-First Search (BFS) algorithm. In general the overall structure for a BFS is the following:

Enqueue(starting position)
Mark starting position
While(queue is not empty)
{
  Value = Dequeue()
  If(value is equal to target)
    Break;
  For each value’ in the neighborhood of value that has not been marked yet
  {
    Enqueue(value’)
    Mark value’
  }
}

Notice that each value, or cell, can only be visited once since it gets marked and no longer visited afterwards. Also, since the search is a radius-based one starting from the minimum radius growing towards higher ones, once the target is found it is guaranteed to be the one with the minimum radius (distance), therefore the shortest path. This is actually a variation of Dijkstra’s Algorithm applied to an unweight indirect graph. The time-complexity for this algorithm applied to the SQ problem would be hence the total number of cells in the board, or 100^2 = 10,000, or < 2^14, which is much more reasonable than the 2^100 with the backtracking. There is a space cost associated with this algorithm which is the use of the queue, hence the space complexity would also be O(N^2) (in our case N = 100). For the following example (N = 30):

X X . X X X X X X X X X . X X X X X . . . X X X X . X X X X
X X X X X X X X . X X X X X X . X X X . X . X X X X . X X X
X X . . X X X X X X X X X X X X X . K X X X X X X X X X X X
X X X X X X X X X X . X X X X X X X X X X . X . X X X X X X
X X X . X X X X X X . X X X X X . X X X X X X X X . X X X X
X X X X X X X X X . S X X X X X X X X X . X X X . X . X X X
X X . X . . . X X X X X X . X X X . X X X X . . X X X X . .
X X X X . X X X . X X X . . X X X X X X X . X . X X X . X X
X X X . X X X X X X X X . X X X X . . . X X X X X X . X X X
X X X X X . X . X X . X X X X . X X X X X X X X X X X X X X
X X . X X . X X X . X X X X . X . . . X X X X X . X X . X .
X X X X X . X X X X X X X X . . . X X X X X X X X X . X X X
X X X X X X X X X X X X . X . . X . . X X X X X . X X X X X
. X X . . . X X X X X X X X X X X X X . X . X X X X X X X X
X X X X X . X X X X . . X X X . X . X X X X X X X X X X X X
X . X . X X . X X X X X . X . X X X . X . X X X X X X . X .
X . X . X X X X X X . . X X X X X X X X X X X X X X X X X X
X . X X X . . X . . . X X X X . X . X X . X X X X X X . X X
. . . X X . . X X X X X X X . X X X . . X X X X X X X X X .
X . . . X . X . X X . X X X X . X . X X . X X X X X X X X X
X X X X X X X X X . X X X X . X . X X X X X X X X X . X X X
X X X X . X X X X . X X X X X X X X X X X X X X X . . X X .
X X X X X . . X X X X X X X X X X . X X X X X X X X . X . .
X X X X X X X X X . X X X . . X X . X X X X X X X X . X X .
X X X . . X X X X X X X X X X X X X X X . . . X X X X X X .
X X X X . X X . . . X X . X . X X X X X X X X X X X X . X X
X X X X X X X X X X X X X . X . . X X X . . X . . X X X X X
. X X X X X . X . X X . X X . X X X X X X . X X X X X X X X
X X X X X X X X X . X X X X X . X X . X X X . X X X . X . X
X X X X X X . X X X X X . . X . X . X X X X X X X X . X . X

The solution would be the following (in bold), in exact 21 steps:

X X . X X X X X X X X X . X X X X X . . . X X X X . X X X X
X X X X X X X X . X X X X X X . X X X . X . X X X X . X X X
X X . . X X X X X X X X X X X X X Q K X X X X X X X X X X X
X X X X X X X X X X . X X X X X X X X X X . X . X X X X X X
X X X . X X X X X X . X X X X X Q X X X X X X X X . X X X X
X X X X X X X X X Q S X X X X X X X X X . X X X . X . X X X
X X . X . . . X X X X X X . X X X Q X X X X . . X X X X . .
X X X X . X X X Q X X X . . X X X X X X X . X . X X X . X X
X X X . X X X X X X X X . X X X X Q Q . X X X X X X . X X X
X X X X X . X Q X X . X X X X . X X X X X X X X X X X X X X
X X . X X Q X X X . X X X X . X Q . . X X X X X . X X . X .
X X X X X Q X X X X X X X X Q . . X X X X X X X X X . X X X
X X X X X X X X X X X X Q X . . X . . X X X X X . X X X X X
. X X . Q . X X X X X X X X X X X X X . X . X X X X X X X X
X X X X X . X X X X . Q X X X . X . X X X X X X X X X X X X
X . X . X X Q X X X X X . X . X X X . X . X X X X X X . X .
X . X . X X X X X X Q . X X X X X X X X X X X X X X X X X X
X . X X X Q . X Q . . X X X X . X . X X . X X X X X X . X X
. . . X X . Q X X X X X X X . X X X . . X X X X X X X X X .
X . . . X . X . X X . X X X X . X . X X . X X X X X X X X X
X X X X X X X X X . X X X X . X . X X X X X X X X X . X X X
X X X X . X X X X . X X X X X X X X X X X X X X X . . X X .
X X X X X . . X X X X X X X X X X . X X X X X X X X . X . .
X X X X X X X X X . X X X . . X X . X X X X X X X X . X X .
X X X . . X X X X X X X X X X X X X X X . . . X X X X X X .
X X X X . X X . . . X X . X . X X X X X X X X X X X X . X X
X X X X X X X X X X X X X . X . . X X X . . X . . X X X X X
. X X X X X . X . X X . X X . X X X X X X . X X X X X X X X
X X X X X X X X X . X X X X X . X X . X X X . X X X . X . X
X X X X X X . X X X X X . . X . X . X X X X X X X X . X . X

Full code (C#) down below:

//Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SuperQueen
{
    class Program
    {
        static void Main(string[] args)
        {
            int dimension = 0;
            int density = 0;
            if (args.Length != 2 ||
                !Int32.TryParse(args[0], out dimension) ||
                !Int32.TryParse(args[1], out density) ||
                density < 0 ||
                density > 80)
            {
                Console.WriteLine("Usage: SuperQueen.exe <board dimension> <density of occupied positions on the board [0-80]>");
                return;
            }
            ChessBoard chessBoard = new ChessBoard(dimension, density);
            if (chessBoard.Randomize())
            {
                chessBoard.Print();
                chessBoard.Process();
            }
        }
    }
}

//ChessBoard.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace SuperQueen
{
    class ChessBoard
    {
        class QueuedElement
        {
            public int r;
            public int c;
            public int numberOfSteps;
            public QueuedElement from;
            public QueuedElement(int r, int c, QueuedElement from, int numberOfSteps)
            {
                this.r = r;
                this.c = c;
                this.numberOfSteps = numberOfSteps;
                this.from = from;
            }
        }
       
        private char[,] board;
        private int dimension;
        private int densityOccupiedPositions = 0;
        private int queenR = 0;
        private int queenC = 0;
        private int kingR = 0;
        private int kingC = 0;
        private char EMPTY = '.';
        private char OCCUPIED = 'X';
        private char SUPERQUEENSTART = 'S';
        private char SUPERQUEEN = 'Q';
        private char KING = 'K';
        private char MARK = '@';
        private ChessBoard() { }
        public ChessBoard(int dimension, int densityOccupiedPositions)
        {
            if (dimension <= 0)
            {
                throw new Exception("Invalid dimension: " + dimension.ToString());
            }
            this.densityOccupiedPositions = densityOccupiedPositions;
            this.dimension = dimension;
            this.board = new char[dimension, dimension];
            this.ClearBoard();
        }
        public bool Randomize()
        {
            this.ClearBoard();
            Random rd = new Random();
            for (int i = 0; i < this.dimension; i++)
            {
                for (int j = 0; j < this.dimension; j++)
                {
                    if (rd.Next(0, 100) < this.densityOccupiedPositions)
                    {
                        this.board[i, j] = OCCUPIED;
                    }
                }
            }
            bool placedQueen = false;
            bool placedKing = false;
            int r = 0;
            int c = 0;
            int nTries = 0;
            int MAXTRIES = 1000000;
            while ((!placedQueen || !placedKing) &&
                    nTries < MAXTRIES)
            {
                nTries++;
                r = rd.Next(0, dimension);
                c = rd.Next(0, dimension);
                if (!placedQueen && this.board[r, c] == EMPTY)
                {
                    this.board[r, c] = SUPERQUEENSTART;
                    this.queenR = r;
                    this.queenC = c;
                    placedQueen = true;
                }
                r = rd.Next(0, dimension);
                c = rd.Next(0, dimension);
                if (!placedKing && this.board[r, c] == EMPTY)
                {
                    this.board[r, c] = KING;
                    this.kingR = r;
                    this.kingC = c;
                    placedKing = true;
                }
            }
            if (nTries >= MAXTRIES)
            {
                Console.WriteLine("Could not randomize the board. Aborting");
                return false;
            }
            return true;
        }
        public void Print()
        {
            for (int r = 0; r < this.dimension; r++)
            {
                for (int c = 0; c < this.dimension; c++)
                {
                    if (this.board[r, c] == MARK)
                    {
                        Console.Write("{0} ", EMPTY);
                    }
                    else
                    {
                        Console.Write("{0} ", this.board[r, c]);
                    }
                }
                Console.WriteLine();
            }
        }
        public void Process()
        {
            Console.WriteLine();
            Console.WriteLine("Processing...");
            Queue<QueuedElement> queue = new Queue<QueuedElement>();
            QueuedElement qe = new QueuedElement(this.queenR, this.queenC, null, 0);
            queue.Enqueue(qe);
            bool caughtKing = false;
            while (queue.Count > 0)
            {
                qe = (QueuedElement)queue.Dequeue();
                if (qe.r == this.kingR && qe.c == this.kingC)
                {
                    caughtKing = true;
                    break;
                }
                //Knight-like move:
                SetCell(qe.r + 2, qe.c + 1, qe, ref queue);
                SetCell(qe.r + 2, qe.c - 1, qe, ref queue);
                SetCell(qe.r + 1, qe.c + 2, qe, ref queue);
                SetCell(qe.r + 1, qe.c - 2, qe, ref queue);
                SetCell(qe.r - 1, qe.c + 2, qe, ref queue);
                SetCell(qe.r - 1, qe.c - 2, qe, ref queue);
                SetCell(qe.r - 2, qe.c + 1, qe, ref queue);
                SetCell(qe.r - 2, qe.c - 1, qe, ref queue);
                int ir = 0;
                int ic = 0;
                //Bishop-like move:
                //Up right
                ir = qe.r + 1;
                ic = qe.c - 1;
                while (SetCell(ir, ic, qe, ref queue))
                {
                    ic--;
                    ir++;
                }
                //Down right
                ir = qe.r + 1;
                ic = qe.c + 1;
                while (SetCell(ir, ic, qe, ref queue))
                {
                    ic++;
                    ir++;
                }
                //Up left
                ir = qe.r - 1;
                ic = qe.c - 1;
                while (SetCell(ir, ic, qe, ref queue))
                {
                    ic--;
                    ir--;
                }
                //Down left
                ir = qe.r - 1;
                ic = qe.c + 1;
                while (SetCell(ir, ic, qe, ref queue))
                {
                    ic++;
                    ir--;
                }
                //Rook-like move:
                //right
                ir = qe.r + 1;
                ic = qe.c;
                while (SetCell(ir, ic, qe, ref queue))
                {
                    ir++;
                }
                //left
                ir = qe.r - 1;
                ic = qe.c;
                while (SetCell(ir, ic, qe, ref queue))
                {
                    ir--;
                }
                //up
                ir = qe.r;
                ic = qe.c - 1;
                while (SetCell(ir, ic, qe, ref queue))
                {
                    ic--;
                }
                //down
                ir = qe.r;
                ic = qe.c + 1;
                while (SetCell(ir, ic, qe, ref queue))
                {
                    ic++;
                }
            }
            Console.WriteLine();
            if (caughtKing)
            {
                Console.WriteLine("Found solutions in {0} steps", qe.numberOfSteps);
                SetSuperQueens(qe.from); //Start from the previous to avoid replacing the king placement
                this.Print();
            }
            else
            {
                Console.WriteLine("Not found!");
            }
        }
        private void SetSuperQueens(QueuedElement qe)
        {
            if (qe == null || qe.from == null)
            {
                return;
            }
            this.board[qe.r, qe.c] = SUPERQUEEN;
            SetSuperQueens(qe.from);
        }
        private bool SetCell(int r, int c, QueuedElement from, ref Queue<QueuedElement> queue)
        {
            bool retVal = false;
            bool skipEnqueuing = false;
            if (r >= 0 && r < this.dimension && c >= 0 && c < this.dimension)
            {
                switch (this.board[r, c])
                {
                    case '.': //empty
                        this.board[r, c] = MARK;
                        retVal = true;
                        break;
                    case 'X': //occupied
                        retVal = false;
                        break;
                    case 'S': //super queen starting point
                        retVal = false;
                        break;
                    case 'Q': //super queen mid position
                        retVal = false;
                        break;
                    case 'K': //king
                        retVal = true;
                        break;
                    case '@': //mark
                        retVal = true; //set as true, since we might be in the midst of a rook/bishop-like move, but don't enqueue it
                        skipEnqueuing = true;
                        break;
                }
            }
            if (retVal && !skipEnqueuing)
            {
                QueuedElement qe = new QueuedElement(r, c, from, from.numberOfSteps+1);
                queue.Enqueue(qe);
            }
            return retVal;
        }
        private void ClearBoard()
        {
            for (int r = 0; r < this.dimension; r++)
            {
                for (int c = 0; c < this.dimension; c++)
                {
                    this.board[r, c] = EMPTY;
                }
            }
        }
    }
}