"Bingo" question

[jemidiah]

I have a 5x5 grid filled with the numbers 1-25. 13 of the numbers are drawn randomly and marked. I can draw D of the remaining 12 numbers randomly and mark them off on my grid. I win if I eventually get a "bingo", i.e. 5 marks in any row, column, or either diagonal. My question is, given a value of D, what are my odds P(D) of winning? I should note that in the initial phase marking 13 numbers off, if a number would otherwise create a bingo, it is redrawn. This prevents me from winning without drawing, so P(0) = 0.

The smallest value where I'm guaranteed to win (P(D) = 1) is D=8: that leaves 25-13-8 = 4 unmarked "holes", which isn't enough to put a hole in all 5 columns. The following arrangement illustrates that P(7) < 1, since even after 7 draws there is no bingo:

_ = unmarked
X = initially marked
d = one of the D=7 drawn numbers

_dddd
d_ddX
XX_XX
XXX_X
XXXX_

This question is modeled after the game show Lingo's final round. The D value is determined by the contestants' performance during that round. Most people get D >= 6, and I've always suspected that the tension generated by wondering whether or not they'll draw luckily enough to win is mostly fabricated since they basically always win. There are very few final arrangements like the above for D=7 which result in a loss. I could write a simulation program, but I'd find it tedious. Perhaps someone else would enjoy the exercise, though, which is why I ask here. There's also a chance someone will find an exact answer, but I imagine it would be greatly complicated by the constraint implying P(0) = 0.

[dbasnett]

A quick shot at the problem:

Public Class Form1

    Dim prng As New Random
    Dim l As List(Of Integer)
    Const sel As Integer = -99
    Const tries As Integer = 2000
    Dim ctrs As List(Of Integer)

    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        ctrs = New List(Of Integer)
        For d As Integer = 1 To 12
            ctrs.Add(0)
            For z As Integer = 1 To tries
                NewBoard()
                Dim drw As Integer
                For y As Integer = 1 To d
                    Do
                        drw = prng.Next(l.Count)
                        If l(drw) <> sel Then
                            l(drw) = sel
                            Exit Do
                        End If
                    Loop
                Next
                If checkWin() Then
                    ctrs(d - 1) += 1
                End If
            Next z
        Next d

        For x As Integer = 0 To ctrs.Count - 1
            Debug.WriteLine("{0}   {1:p1}", x + 1, ctrs(x) / tries)
        Next
        Debug.WriteLine("")
    End Sub

    Private Sub NewBoard()
        l = New List(Of Integer)
        l.AddRange(Enumerable.Range(0, 25).ToArray)
        Dim ct As Integer = 0
        Do While ct < 13
            Dim drw As Integer = prng.Next(l.Count)
            If l(drw) <> sel Then
                Dim h As Integer = l(drw)
                l(drw) = sel
                If checkWin() Then
                    l(drw) = h
                Else
                    ct += 1
                End If
            End If
        Loop
        'Dim foo As Integer = l.FindAll(Function(n) n = sel).Count
    End Sub

    '0  1  2  3  4
    '5  6  7  8  9
    '10 11 12 13 14
    '15 16 17 18 19
    '20 21 22 23 24

    Private Function checkWin() As Boolean
        'check diagonals
        If l(0) = sel AndAlso l(6) = sel AndAlso l(12) = sel AndAlso l(18) = sel AndAlso l(24) = sel Then Return True
        If l(20) = sel AndAlso l(16) = sel AndAlso l(12) = sel AndAlso l(8) = sel AndAlso l(4) = sel Then Return True
        Dim match As Integer
        'check rows
        For r As Integer = 0 To 4
            match = 0
            For c As Integer = 0 To 4
                Dim idx As Integer = r * 5 + c
                If l(idx) = sel Then match += 1
            Next
            If match = 5 Then Return True
        Next
        'check cols.
        For c As Integer = 0 To 4
            match = 0
            For r As Integer = 0 To 4
                Dim idx As Integer = c + (r * 5)
                If l(idx) = sel Then match += 1
            Next
            If match = 5 Then Return True
        Next
        Return False
    End Function

    Private Sub showL()
        For r As Integer = 0 To 4
            For c As Integer = 0 To 4
                Dim idx As Integer = r * 5 + c
                Debug.Write(l(idx).ToString().PadLeft(4, " "c))
            Next
            Debug.WriteLine("")
        Next
        Debug.WriteLine("")
    End Sub
End Class

Sample results:

1   18.9 %
2   41.4 %
3   61.9 %
4   79.8 %
5   92.1 %
6   98.0 %
7   99.7 %
8   100.0 %
9   100.0 %
10   100.0 %
11   100.0 %
12   100.0 %

[jemidiah]

Awesome, thank you. I'm surprised the D=5 and 6 cases are so high. Maybe I'll explicitly calculate the D=7 odds. There are only a few dozen losing configurations in that case, which I figure would make the final form at least relatively simple.