

The Problem

 100 prisoners are individually numbered 1 to 100
 A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
 Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
 Prisoners start outside the room
 They can decide some strategy before any enter the room.
 Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
 A prisoner can open no more than 50 drawers.
 A prisoner tries to find his own number.
 A prisoner finding his own number is then held apart from the others.
 If all 100 prisoners find their own numbers then they will all be pardoned. If any don't then all sentences stand. 


The task

 Simulate several thousand instances of the game where the prisoners randomly open drawers
 Simulate several thousand instances of the game where the prisoners use the optimal strategy mentioned in the Wikipedia article, of:
 First opening the drawer whose outside number is his prisoner number.
 If the card within has his number then he succeeds otherwise he opens the drawer with the same number as that of the revealed card. (until he opens his maximum).


Show and compare the computed probabilities of success for the two strategies, here, on this page.




References

 The unbelievable solution to the 100 prisoner puzzle standupmaths (Video).
 wp:100 prisoners problem
 100 Prisoners Escape Puzzle DataGenetics.
 Random permutation statistics#One hundred prisoners on Wikipedia.


USE rosettacode;
GO
 
SET NOCOUNT ON;
GO
 
CREATE TABLE dbo.numbers (n INT PRIMARY KEY);
GO
 
-- NOTE If you want to play more than 10000 games, you need to extend the query generating the numbers table by adding
-- next cross joins. Now the table contains enough values to solve the task and it takes less processing time.
 
WITH sample100 AS (
    SELECT TOP(100) object_id
    FROM master.sys.objects
)
INSERT numbers
    SELECT ROW_NUMBER() OVER (ORDER BY A.object_id) AS n
    FROM sample100 AS A
        CROSS JOIN sample100 AS B;
GO
 
CREATE TABLE dbo.drawers (drawer INT PRIMARY KEY, card INT);
GO
 
CREATE TABLE dbo.results (strategy VARCHAR(10), game INT, result BIT, PRIMARY KEY (game, strategy));
GO
 
CREATE PROCEDURE dbo.shuffleDrawers @prisonersCount INT
AS BEGIN
    SET NOCOUNT ON;
 
    IF NOT EXISTS (SELECT * FROM drawers)
        INSERT drawers (drawer, card)
        SELECT n AS drawer, n AS card
        FROM numbers
        WHERE n <= @prisonersCount;
 
    DECLARE @randoms TABLE (n INT, random INT);
    DECLARE @n INT = 1;
    WHILE @n <= @prisonersCount BEGIN
        INSERT @randoms VALUES (@n, ROUND(RAND() * (@prisonersCount - 1), 0) + 1);
 
        SET @n = @n + 1;
    END;
 
    WITH ordered AS (
        SELECT ROW_NUMBER() OVER (ORDER BY random ASC) AS drawer,
            n AS card
        FROM @randoms
    )
    UPDATE drawers
    SET card = o.card
    FROM drawers AS s
        INNER JOIN ordered AS o
            ON o.drawer = s.drawer;
END
GO
 
CREATE PROCEDURE dbo.find @prisoner INT, @strategy VARCHAR(10)
AS BEGIN
    -- A prisoner can open no more than 50 drawers.
    DECLARE @drawersCount INT = (SELECT COUNT(*) FROM drawers);
    DECLARE @openMax INT = @drawersCount / 2;
 
    -- Prisoners start outside the room.
    DECLARE @card INT = NULL;
    DECLARE @open INT = 1;
    WHILE @open <= @openMax BEGIN
        -- A prisoner tries to find his own number.
        IF @strategy = 'random' BEGIN
            DECLARE @random INT = ROUND(RAND() * (@drawersCount - 1), 0) + 1;
            SET @card = (SELECT TOP(1) card FROM drawers WHERE drawer = @random);
        END
        IF @strategy = 'optimal' BEGIN
            IF @card IS NULL BEGIN
                SET @card = (SELECT TOP(1) card FROM drawers WHERE drawer = @prisoner);
            END ELSE BEGIN
                SET @card = (SELECT TOP(1) card FROM drawers WHERE drawer = @card);
            END
        END
 
        -- A prisoner finding his own number is then held apart from the others.
        IF @card = @prisoner
            RETURN 1;
 
        SET @open = @open + 1;
    END
 
    RETURN 0;
END
GO
 
CREATE PROCEDURE dbo.playGame @gamesCount INT, @strategy VARCHAR(10), @prisonersCount INT = 100
AS BEGIN
    SET NOCOUNT ON;
 
    IF @gamesCount <> (SELECT COUNT(*) FROM results WHERE strategy = @strategy) BEGIN
        DELETE results
        WHERE strategy = @strategy;
 
        INSERT results (strategy, game, result)
        SELECT @strategy AS strategy, n AS game, 0 AS result
        FROM numbers
        WHERE n <= @gamesCount;
    END
 
    UPDATE results
    SET result = 0
    WHERE strategy = @strategy;
 
    DECLARE @game INT = 1;
    WHILE @game <= @gamesCount BEGIN
        -- A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
        -- Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
        EXECUTE shuffleDrawers @prisonersCount;
 
        -- A prisoner tries to find his own number.
        -- Prisoners start outside the room.
        -- They can decide some strategy before any enter the room.
        DECLARE @prisoner INT = 1;
        DECLARE @found INT = 0;
        WHILE @prisoner <= @prisonersCount BEGIN
            EXECUTE @found = find @prisoner, @strategy;
            IF @found = 1
                SET @prisoner = @prisoner + 1;
            ELSE
                BREAK;
        END;
 
        -- If all 100 findings find their own numbers then they will all be pardoned. If any don't then all sentences stand.
        IF @found = 1
            UPDATE results SET result = 1 WHERE strategy = @strategy AND game = @game;
 
        SET @game = @game + 1;
    END
END
GO
 
CREATE FUNCTION dbo.computeProbability(@strategy VARCHAR(10))
RETURNS decimal (18, 2)
AS BEGIN
    RETURN (
        SELECT (SUM(CAST(result AS INT)) * 10000 / COUNT(*)) / 100
        FROM results
        WHERE strategy = @strategy
    );
END
GO
 
-- Simulate several thousand instances of the game:
DECLARE @gamesCount INT = 2000;
 
-- ...where the prisoners randomly open drawers.
EXECUTE playGame @gamesCount, 'random';
 
-- ...where the prisoners use the optimal strategy mentioned in the Wikipedia article.
EXECUTE playGame @gamesCount, 'optimal';
 
-- Show and compare the computed probabilities of success for the two strategies.
DECLARE @log VARCHAR(max);
SET @log = CONCAT('Games count: ', @gamesCount);
RAISERROR (@log, 0, 1) WITH NOWAIT;
SET @log = CONCAT('Probability of success with "random" strategy: ', dbo.computeProbability('random'));
RAISERROR (@log, 0, 1) WITH NOWAIT;
SET @log = CONCAT('Probability of success with "optimal" strategy: ', dbo.computeProbability('optimal'));
RAISERROR (@log, 0, 1) WITH NOWAIT;
GO
 
DROP FUNCTION dbo.computeProbability;
DROP PROCEDURE dbo.playGame;
DROP PROCEDURE dbo.find;
DROP PROCEDURE dbo.shuffleDrawers;
DROP TABLE dbo.results;
DROP TABLE dbo.drawers;
DROP TABLE dbo.numbers;
GO