Super Queen II

5 years ago I wrote about a hypothetical problem related to super queens in chess. You can see the original post here. This post starts with a traditional CS algorithmic problem: the 8-queens problem. The idea is to place 8 queens in a chess board with no two queens threatening each other. I wanted to go a little beyond and redo this problem but now with super queens. To recap, a super queen contains all the powers of a regular queen, but it also has the knight powers. Can it be done then? Can we have an 8-super queens problem solved? Let's see.

The idea is to use backtracking with tree pruning. But here is an interesting idea: all you need to solve this problem is actually 5 hash tables that will tell you which queens are dominating the following positions:
 - The rows
 - The columns
 - The first diagonal
 - The second diagonal
 - And finally the fifth one, which is the tricky one, marks any square that it being attacked by any queen in a knight-like move.

The image below depicts this approach:

From that point on, regular backtracking solution. Notice that if you ignore hash table 5 the problem reduces to the 8-queens problem - I actually coded in such a way that you can either ask for a super-queens solution, or regular queens solution.

Finally to answer the question about the feasibility of a solution for the 8-super queens problem, the answer is no, there is no solution. The first N (where N is the dimensions of the board) which yields a valid solution for the N-super queens problem is 12, which has two solutions:

Due to the extra power of the queens, the board needs to be sparse enough in order to avoid the knight-like jump threat, hence the minimum N for which the sparseness of the board gives enough room for maneuver is 12. Code is down below - cheers, Marcelo.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TheNSuperQueensProblemNS
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 0;
            if (args.Length != 2 ||
                !Int32.TryParse(args[0], out n) ||
                (!args[1].Equals("r", StringComparison.CurrentCultureIgnoreCase) && !args[1].Equals("s", StringComparison.CurrentCultureIgnoreCase)))
            {
                Console.WriteLine("Usage: TheNSuperQueensProblem.exe <N - board dimension> <R - regular OR S - super queens>");
                return;
            }
            Solution solution = new Solution();
            solution.TheNSuperQueensProblem(n, args[1].ToLower()[0]);
        }
    }

    public class Solution
    {
        public void TheNSuperQueensProblem(int N, char mode)
        {
            Hashtable[] rowColDiags = new Hashtable[4];
            for (int i = 0; i < rowColDiags.Length; i++) rowColDiags[i] = new Hashtable();

            int numberOfSolutions = 0;
            TheNSuperQueensProblemInternal(0, N, rowColDiags, new Hashtable(), ref numberOfSolutions, new Hashtable(), mode);
            Console.WriteLine();
            Console.WriteLine("Number of solutions for N={0}: {1}", N, numberOfSolutions);
        }
        private void TheNSuperQueensProblemInternal(int r,
                                                    int N,
                                                    Hashtable[] rowColDiags,
                                                    Hashtable solution,
                                                    ref int numberOfSolutions,
                                                    Hashtable knightMoves,
                                                    char mode)
        {
            if (r >= N)
            {
                numberOfSolutions++;
                PrintBoard(N, solution);
                return;
            }

            char letterAssociatedWithTheCurrentQueen = (char)((int)'a' + r);
            for (int c = 0; c < N; c++)
            {
                if (!rowColDiags[0].ContainsKey(r) &&
                    !rowColDiags[1].ContainsKey(c) &&
                    !rowColDiags[2].ContainsKey(r + c) &&
                    !rowColDiags[3].ContainsKey(r - c) &&
                    (mode == 'r' || CheckAndSetKnightMoves(r, c, N, knightMoves)))
                {
                    rowColDiags[0].Add(r, letterAssociatedWithTheCurrentQueen);
                    rowColDiags[1].Add(c, letterAssociatedWithTheCurrentQueen);
                    rowColDiags[2].Add(r + c, letterAssociatedWithTheCurrentQueen);
                    rowColDiags[3].Add(r - c, letterAssociatedWithTheCurrentQueen);

                    solution.Add(r * N + c, Char.ToUpper(letterAssociatedWithTheCurrentQueen));

                    TheNSuperQueensProblemInternal(r + 1, N, rowColDiags, solution, ref numberOfSolutions, knightMoves, mode);

                    solution.Remove(r * N + c);

                    rowColDiags[0].Remove(r);
                    rowColDiags[1].Remove(c);
                    rowColDiags[2].Remove(r + c);
                    rowColDiags[3].Remove(r - c);

                    RemoveKnightMoves(r, c, N, knightMoves);
                }
            }
        }

        private bool CheckAndSetKnightMoves(int r,
                                            int c,
                                            int N,
                                            Hashtable knightMoves)
        {
            if (knightMoves.ContainsKey(r * N + c)) return false;

            int[] possibleMovesRow = { r + 1, r + 1, r - 1, r - 1, r + 2, r + 2, r - 2, r - 2};
            int[] possibleMovesCol = { c + 2, c - 2, c + 2, c - 2, c + 1, c - 1, c + 1, c - 1};

            char letterAssociatedWithTheCurrentQueen = (char)((int)'a' + r);

            bool moveAllowed = true;
            for (int i = 0; i < possibleMovesRow.Length; i++)
            {
                if (possibleMovesRow[i] >= 0 &&
                    possibleMovesRow[i] < N &&
                    possibleMovesCol[i] >= 0 &&
                    possibleMovesCol[i] < N &&
                    knightMoves.ContainsKey(possibleMovesRow[i] * N + possibleMovesCol[i]))
                {
                    moveAllowed = false;
                    break;
                }
            }

            if (moveAllowed)
            {
                for (int i = 0; i < possibleMovesRow.Length; i++)
                {
                    if (possibleMovesRow[i] >= 0 &&
                        possibleMovesRow[i] < N &&
                        possibleMovesCol[i] >= 0 &&
                        possibleMovesCol[i] < N)
                    {
                        knightMoves.Add(possibleMovesRow[i] * N + possibleMovesCol[i], letterAssociatedWithTheCurrentQueen);
                    }
                }
                knightMoves.Add(r * N + c, Char.ToUpper(letterAssociatedWithTheCurrentQueen));
            }

            return moveAllowed;
        }

        private void RemoveKnightMoves(int r,
                                       int c,
                                       int N,
                                       Hashtable knightMoves)
        {
            int[] possibleMovesRow = { r + 1, r + 1, r - 1, r - 1, r + 2, r + 2, r - 2, r - 2 };
            int[] possibleMovesCol = { c + 2, c - 2, c + 2, c - 2, c + 1, c - 1, c + 1, c - 1 };

            for (int i = 0; i < possibleMovesRow.Length; i++)
            {
                if (possibleMovesRow[i] >= 0 &&
                    possibleMovesRow[i] < N &&
                    possibleMovesCol[i] >= 0 &&
                    possibleMovesCol[i] < N)
                {
                    knightMoves.Remove(possibleMovesRow[i] * N + possibleMovesCol[i]);
                }
            }

            knightMoves.Remove(r * N + c);
        }

        private void PrintBoard(int N,
                                Hashtable solution)
        {
            for (int r = 0; r < N; r++)
            {
                for (int c = 0; c < N; c++)
                {
                    char placement = '.';
                    if (solution.ContainsKey(r * N + c))
                    {
                        placement = (char)solution[r * N + c];
                    }
                    Console.Write("{0} ", placement);
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }
    }
}