Chessboard Puzzle Solver

chessboard_puzzle.cs

using System;
using System.Collections;

namespace ChessboardPuzzle
{
    static class Program
    {
        static void Main()
        {
            // Inspired by 3blue1brown's excellent video on the topic: https://www.youtube.com/watch?v=wTJI_WuZSwE
            Console.WriteLine("A chess board (8x8 squares) is set up in a prison, with a coin on each square, i.e. 64 total coins.");
            Console.WriteLine("A guard places a key under one coin, and picks the values (heads/tails) of each coin.");
            Console.WriteLine("Two prisoners (A and B) take part in this puzzle. If they succeed, they escape.");
            Console.WriteLine("First, prisoner A is brought into the room, shown the board, and told which position the key is under.");
            Console.WriteLine("Prisoner A must then flip one coin - no more, no less. They then leave the room via a different exit.");
            Console.WriteLine("Prisoner B then enters the room. They cannot touch the board. They are allowed one guess at which square the key is in.");
            Console.WriteLine("If prisoner B guesses the position of the key correctly, both prisoners are freed.");
            Console.WriteLine("Prisoners A and B can strategise ahead of time, but the guard listens in and can pick key positions and board states to thwart them.");
            Console.WriteLine("The prisoners must come up with a solution that works 100% of the time, even in these adversarial conditions.");
            Console.WriteLine();
            Console.WriteLine("Here's how they solve it...");
            Console.WriteLine();
            
            var rng = new Random();

            Console.WriteLine("Guard is picking the position of the key...");

            int keyPos = rng.Next(0, 64);
            Console.WriteLine("Key position: [{1},{2}] -> index {0}", keyPos, keyPos % 8, (keyPos - (keyPos % 8)) / 8);
            Console.WriteLine();

            Console.WriteLine("Guard is setting up the board...");

            byte[] bs = new byte[8];
            rng.NextBytes(bs);
            var board = new BitArray(bs);

            // prisoner A knows the key position, and can see the board
            PrisonerA(ref board, keyPos);

            Console.WriteLine();
            Console.WriteLine("==== HANDING OVER TO OTHER PRISONER ====");
            Console.WriteLine();

            // prisoner B only sees the board
            int keyPosGuess = PrisonerB(board);

            Console.WriteLine();
            if (keyPosGuess == keyPos)
            {
                Console.WriteLine("SUCCESS! Key is found and prisoners escape.");
            }
            else
            {
                Console.WriteLine("FAILURE! Prisoners are stuck.");
            }
        }

        static void PrisonerA(ref BitArray board, int keyPos)
        {
            Console.WriteLine();
            Console.WriteLine("==== PRISONER A ENTERS THE ROOM ====");
            Console.WriteLine();

            Console.WriteLine("Prisoner A is told key position: [{1},{2}] -> index {0}", keyPos, keyPos % 8, (keyPos - (keyPos % 8)) / 8);
            Console.WriteLine();

            Console.WriteLine("Prisoner A can see the board.");

            DrawBoard(board, keyPos);
            
            Console.WriteLine("Prisoner A does a board parity calculation:");

            int parity = CalculateParity(board);

            int flipPos = keyPos ^ parity;
            Console.WriteLine("Change needed to turn parity value ({0}) into key position ({1}) = {0} ^ {1} = {2}", parity, keyPos, flipPos);
            Console.WriteLine("Prisoner A flips coin at index {0} -> position [{1},{2}]", flipPos, flipPos % 8, (flipPos - (flipPos % 8)) / 8);
            board[flipPos] = !board[flipPos];
            Console.WriteLine();

            DrawBoard(board, keyPos, flipPos);

            Console.WriteLine();
            Console.WriteLine("==== PRISONER A LEAVES THE ROOM ====");
            Console.WriteLine();
        }

        static int PrisonerB(BitArray board)
        {
            Console.WriteLine();
            Console.WriteLine("==== PRISONER B ENTERS THE ROOM ====");
            Console.WriteLine();

            Console.WriteLine("Prisoner B can see the board, but does not know the key position.");

            DrawBoard(board);

            Console.WriteLine("Prisoner B does a board parity calculation:");
            int keyPosGuess = CalculateParity(board);

            Console.WriteLine("Prisoner B calculated parity of {0}, which encodes key position [{1},{2}]", keyPosGuess, keyPosGuess % 8, (keyPosGuess - (keyPosGuess % 8)) / 8);
            
            return keyPosGuess;
        }

        static void DrawBoard(BitArray board, int keyPos = -1, int flipPos = -1)
        {
            Console.WriteLine("Board state:");
            Console.WriteLine("   | 0   1   2   3   4   5   6   7   ");
            Console.WriteLine("---+---------------------------------");
            for (int y = 0; y < 8; y++)
            {
                Console.Write("{0:D2} | ", y * 8);
                for (int x = 0; x < 8; x++)
                {
                    int index = (y * 8) + x;

                    string suffix;
                    if (index == keyPos && index == flipPos)
                        suffix = "KF";
                    else if (index == keyPos)
                        suffix = "K ";
                    else if (index == flipPos)
                        suffix = "F ";
                    else
                        suffix = "  ";

                    string value = board[index] ? "H" : "T";
                    Console.Write("{0}{1} ", value, suffix);
                }
                Console.WriteLine();
                if (y < 7)
                    Console.WriteLine("   |");
                else
                    Console.WriteLine();
            }
        }

        static int CalculateParity(BitArray board)
        {
            int parity = 0;
            Console.Write("parity = ");
            for (int i = 0; i < 64; i++)
            {
                int bitValue = board[i] ? 1 : 0;
                Console.Write("({0}*{1})", bitValue, i);
                if (i < 63)
                    Console.Write(" ^ ");
                if (i % 8 == 7)
                    Console.WriteLine();
                parity ^= bitValue * i;
            }
            Console.WriteLine("= {0}", parity);
            Console.WriteLine();
            return parity;
        }
    }
}