Backtracking, knights and patterns

Another commonly used technique in Computer Science for solving algorithm problems is backtracking. Backtracking consists of recursively enumerating all the different possible solutions, and picking the best one out of all of them (in case the problem’s dealing with optimal solutions). Backtracking usually makes use of heuristics to cut/prune down the search space. In general the high-level structure of a backtracking algorithm is as follows:

Backtracking(Enumeration L, Solution S)
{
  //Part 1
  If (L is the final enumeration)
    Check if S is the best one thus far
  //Part 2
  For each K such that K is in the neighborhood of S
    Backtracking(L+1, K)
}

And that’s it. To exemplify backtracking I picked a chess problem: given the dimensions of a chess board (usually 8, but we’ll let the user decides which dimension) N, determine the maximum number of knights that can be safely placed on the N-board without one knight threatening any other. You will see that the solution to this problem follows a very simple mathematical pattern than thought (at least thought by me). Backtracking is one way to solve this problem – it is expensive because there isn’t much of a heuristic that can be used to prune down the search space. In part 2 of our algorithm we’ll try to place one knight in the current position, but we’ll also skip that position. Algorithm is very slow, and actually impractical for N >= 8 (O(2^64)…), but running it for N <= 7 you can find a nice pattern popping up:

For N = 5:
K X K X K
X K X K X
K X K X K
X K X K X
K X K X K

For N = 6:
K X K X K X
X K X K X K
K X K X K X
X K X K X K
K X K X K X
X K X K X K

As you can see the pattern is simple:
- For even rows (assuming rows start from row 0), place a knight in the even columns (assuming cols start from col 0)
- For odd rows (assuming rows start from row 0), place a knight in the odd columns (assuming cols start from col 0)
And so you have it. Such implementation can actually be done in linear time now that we figured out the mathematical pattern associated with the solution. Backtracking code below (C#):

//Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace KnightsOnChessBoard
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 0;
            if (args.Length == 0 || !Int32.TryParse(args[0], out n))
            {
                Console.WriteLine("Usage: KnightsOnChessBoard.exe <squared board dimension>");
                return;
            }
            ChessBoard chessBoard = new ChessBoard(n);
            ChessBoard bestChessBoard = new ChessBoard(n);
            Process(0, n, ref chessBoard, ref bestChessBoard);
            Console.WriteLine("Max number of placed knights for a {0}-board: {1}", n, bestChessBoard.numberOfKnightsPlaced);
            bestChessBoard.PrintBoard();
        }
        static void Process(int coordinate,
                            int n,
                            ref ChessBoard chessBoard,
                            ref ChessBoard bestChessBoard)
        {
            if (coordinate >= n * n)
            {
                if (chessBoard.numberOfKnightsPlaced > bestChessBoard.numberOfKnightsPlaced)
                {
                    bestChessBoard.Copy(chessBoard);
                }
                return;
            }
            int r = coordinate / n;
            int c = coordinate % n;
            //Place it on (r,c). Move to coordinate+1
            if (chessBoard.AttemptPlacementOfKnight(r, c))
            {
                Process(coordinate + 1, n, ref chessBoard, ref bestChessBoard);
                chessBoard.RemovePlacementOfKnight(r, c);
            }
            //Don't place it on (r,c). Move to coordinate+1
            Process(coordinate + 1, n, ref chessBoard, ref bestChessBoard);
        }
    }
}

//ChessBoard.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace KnightsOnChessBoard
{
    class ChessBoard
    {
        public int numberOfKnightsPlaced = 0;
        private int[,] board;
        private int n;
        private int OCCUPIED_BY_KNIGHT = -1;
        private int FREE = 0;
        private ChessBoard() { }
        public ChessBoard(int n)
        {
            this.n = n;
            this.board = new int[this.n, this.n];
            this.Reset();
        }
        public void Copy(ChessBoard chessBoard)
        {
            this.numberOfKnightsPlaced = chessBoard.numberOfKnightsPlaced;
            this.n = chessBoard.n;
            for (int r = 0; r < this.n; r++)
            {
                for (int c = 0; c < this.n; c++)
                {
                    this.board[r, c] = chessBoard.board[r, c];
                }
            }
        }
        public void PrintBoard()
        {
            Console.WriteLine();
            for (int r = 0; r < this.n; r++)
            {
                for (int c = 0; c < this.n; c++)
                {
                    if (this.board[r, c] == OCCUPIED_BY_KNIGHT)
                    {
                        Console.Write("K ");
                    }
                    else if (this.board[r, c] == FREE)
                    {
                        Console.Write("0 ");
                    }
                    else
                    {
                        Console.Write("X ");
                    }
                }
                Console.WriteLine();
            }
        }
        public bool AttemptPlacementOfKnight(int r, int c)
        {
            if (r < 0 || r >= this.n || c < 0 || c >= this.n)
            {
                return false;
            }
            if (this.board[r, c] != FREE)
            {
                return false;
            }
            this.board[r, c] = OCCUPIED_BY_KNIGHT;
            this.numberOfKnightsPlaced++;
            this.Mark(r + 2, c + 1, 1);
            this.Mark(r + 2, c - 1, 1);
            this.Mark(r - 2, c + 1, 1);
            this.Mark(r - 2, c - 1, 1);
            this.Mark(r + 1, c + 2, 1);
            this.Mark(r + 1, c - 2, 1);
            this.Mark(r - 1, c + 2, 1);
            this.Mark(r - 1, c - 2, 1);
            return true;
        }
        public void RemovePlacementOfKnight(int r, int c)
        {
            if (r < 0 || r >= this.n || c < 0 || c >= this.n)
            {
                return;
            }
            if (this.board[r, c] != OCCUPIED_BY_KNIGHT)
            {
                return;
            }
            this.board[r, c] = FREE;
            this.numberOfKnightsPlaced--;
            this.Mark(r + 2, c + 1, -1);
            this.Mark(r + 2, c - 1, -1);
            this.Mark(r - 2, c + 1, -1);
            this.Mark(r - 2, c - 1, -1);
            this.Mark(r + 1, c + 2, -1);
            this.Mark(r + 1, c - 2, -1);
            this.Mark(r - 1, c + 2, -1);
            this.Mark(r - 1, c - 2, -1);
        }
        private void Mark(int r, int c, int threat)
        {
            if (r < 0 || r >= this.n || c < 0 || c >= this.n)
            {
                return;
            }
            if (this.board[r, c] != OCCUPIED_BY_KNIGHT)
            {
                this.board[r, c] += threat;
            }
        }
        private void Reset()
        {
            for (int r = 0; r < this.n; r++)
            {
                for (int c = 0; c < this.n; c++)
                {
                    this.board[r, c] = FREE;
                }
            }
        }
    }
}