Table of Contents
The symbol 
returns the reader to the top of the Table of Contents.
1. Introduction 
This article is the first of three articles describing the Bingo game suite that I developed over the past few months. The articles are published in the hope that the software may prove useful to the articles' readers. The three articles address the US version of Bingo that has 75 numbered balls.
1.1. Bingo
In the United States, bingo is a game of chance in which each player matches the numbers printed in different arrangements on cards. The game host (caller) draws at random, marking the selected numbers with tiles. When a player finds the selected numbers are arranged on their card in a row, they call out "Bingo!" to alert all participants to a winning card, which prompts the game host (or an associate assisting the host) to examine the card for verification of the win. Players compete against one another to be the first to have a winning arrangement for the prize or jackpot. After a winner is declared, the players clear their number cards of the tiles and the game host begins a new round of play.
Wikipedia, Bingo (American version) [^]
a form of lotto in which balls or slips, each with a number and one of the letters B, I, N, G, or O, are drawn at random and players cover the corresponding numbers printed on their cards, the winner being the first to cover five numbers in any row or diagonal or, sometimes, all numbers on the card.
Dictionary.com, bingo [^]
Bingo is a game of chance due to the random draws made by the caller and the random arrangement of numbers on a player's Bingo card. It is the latter that is addressed in this article.
In order for a game of Bingo to be played, it is necessary to generate and print the Bingo cards that players will use.
This article discusses the bolded items in the preceding figure.
1.2. Bingo Card
Bingo cards are composed of six rows of five columns. The first row is the card heading and contains the letters 'B', 'I', 'N', 'G', and 'O', each letter appearing in its own column. The following five rows contain random numbers that are generated by a set of rules that specify the values that are allowed to appear in a given column. An undecorated Bingo card appears as:
The center square of the 5 x 5 card is known as a "free space" that is considered as called. When 24 random numbers are inserted, the card may appear as follows.
The figure on the right was created with the requirement that stars be distributed throughout the Bingo cards. When this requirement is imposed, each Bingo card will have one star randomly placed thereon. The location of the star on each card is recorded in the Bingo card file.
The numeric value in the free space, in this case 2066057, is named the group_face and uniquely identifies the card. It is made up of the encoded card color (2 is LightCoral) and the card face number (starting at 1 up to the number of cards generated).
The layout of the card is the responsibility of the Print_Cards program (the subject of Part 2 of this series).
2. Saving the Bingo Cards
Although this article specifically addresses the generation of Bingo cards, once generated, the new Bingo cards are saved.
2.1. Bingo Cards File Format
The format of the Bingo cards file is a 128-byte header followed by a number of Bingo cards. Each card is composed of 25 bytes. The byte at the center of this collection (indexed as 13) is used to record the location of the "star" on the card.
The use of bytes as the form of the saved Bingo card was decided based upon the possibility of a large number of Bingo card being generated. For example, a file containing 800,000 25 byte Bingo cards requires a file of 20,000,128 bytes; while if unsigned 32-bit integers were to be used (in place of 8-bit bytes), the file size would be 80,000,128 bytes.
The Bingo cards file is a direct access file. The formula used to access a specific record numbered card_number is:
public const int CARD_DATA_VALUES = 25;
public const int CARD_VALUES_AT = 128;
public const int CARD_VALUES_SIZE =
CARD_DATA_VALUES *
sizeof ( byte );
public const int CARD_SIZE = CARD_VALUES_SIZE;
card_offset = ( ( card_number - 1 ) * CONST.CARD_SIZE ) +
CONST.CARD_VALUES_AT;
When a player calls "Bingo!," the caller asks the player for the group_face number printed on the card. The group is stripped from the group_face yielding the card_number that will be used in accessing the Bingo card. Note that card numbers are not stored in the Bingo card file; rather they are implied.
As each unique Bingo card is generated, its 25 byte record is appended to the Bingo card file.
2.2. Card_File_IO Class
To save the Bingo cards, the FileStream Class [^] is used. The various methods needed for saving the card file are encapsulated in the Card_File_IO class in the Utilities project. Note that the following is not the whole class but only contains those methods that are used during the generation process. The missing pieces will be discussed in the other parts of this series.
using System;
using System.IO;
using System.Linq;
using CONST = Utilities.Constants;
namespace Utilities
{
public class Card_File_IO
{
private FileStream fs = null;
public bool create_file ( string path,
ref string error_message )
{
bool success = false;
error_message = String.Empty;
try
{
fs = new FileStream ( path,
FileMode.CreateNew,
FileAccess.ReadWrite,
FileShare.Read );
success = true;
}
catch ( Exception e )
{
error_message = e.Message;
success = false;
}
return ( success );
}
⋮
public void zero_bytes_in_file ( long start_at,
int count )
{
if ( fs != null )
{
fs.Seek ( start_at, SeekOrigin.Begin );
for ( int i = 0; ( i < count ); i++ )
{
fs.WriteByte ( ( byte ) 0 );
}
}
}
⋮
public bool write_bytes_to_file (
byte [ ] bytes,
long offset,
ref string error_message )
{
bool success = false;
error_message = String.Empty;
if ( fs != null )
{
try
{
fs.Seek ( offset, SeekOrigin.Begin );
for ( int i = 0; ( i < bytes.Length ); i++ )
{
fs.WriteByte ( bytes [ i ] );
}
fs.Flush ( );
success = true;
}
catch ( Exception e )
{
error_message = e.Message;
success = false;
}
}
return ( success );
}
public bool append_bytes_to_file (
byte [ ] bytes,
int byte_count,
ref string error_message )
{
bool success = false;
error_message = String.Empty;
if ( fs != null )
{
try
{
fs.Seek ( 0, SeekOrigin.End );
fs.Write ( bytes, 0, byte_count );
fs.Flush ( );
success = true;
}
catch ( Exception e )
{
error_message = e.Message;
success = false;
}
}
return ( success );
}
public bool close_file ( ref string error_message)
{
bool success = false;
error_message = String.Empty;
try
{
if ( fs != null )
{
fs.Close ( );
}
success = true;
}
catch ( Exception e )
{
error_message = e.Message;
success = false;
}
return ( success );
}
public bool Dispose ( ref string error_message )
{
bool success = false;
error_message = String.Empty;
try
{
if ( fs != null )
{
fs.Dispose ( );
fs = null;
}
success = true;
}
catch ( Exception e )
{
error_message = e.Message;
success = false;
}
return ( success );
}
}
}
The FileStream (fs) is private to the Card_File_IO class. Within the Generate_Cards application, it is created once and closed by the application_cleanup event handler, triggered by the application exit.
void application_cleanup ( object sender,
EventArgs e )
{
cfio.close_file ( ref error_message );
cfio.Dispose ( ref error_message );
}
There are really no surprises in the Card_File_IO class. All of the methods contained therein are simple and straight-forward.
3. Generating the Cards
The approach to generating unique Bingo cards is:
- Generate a card
- Generate a hash of the values in the card
- Search the hashes binary tree for the newly generated hash
- If hash is found in the hashes binary tree, go to step 1
- If hash was not found in the hashes binary tree:
- Insert hash into the hashes binary tree
- Append the new Bingo card to the end of the Bingo card file
- If another card needs to be generated, go to step 1
Bingo cards are generated by the BackgroundWorker [^] generate_cards_DoWork.
void generate_cards_DoWork ( object sender,
DoWorkEventArgs e )
{
BackgroundWorker worker = ( BackgroundWorker ) sender;
watch.Start ( );
zero_header ( );
for ( int i = 0; ( i < cards_to_generate ); i++ )
{
byte [ ] bytes;
uint hash = 0;
thread_pause_state.Wait ( );
if ( worker.CancellationPending )
{
e.Cancel = true;
return;
}
do
{
bytes = populate_card_array ( );
hash = generated_hash ( bytes,
CONST.CENTER_CELL_INDEX );
} while ( duplicate_hash ( hash ) );
append_bingo_card ( bytes );
worker.ReportProgress ( 0, ( i + 1 ) );
}
watch.Stop ( );
elapsed_time = watch.Elapsed.TotalSeconds;
e.Result = elapsed_time;
}
generate_cards_DoWork is a BackgroundWorker [^]. The algorithm is based on the observation:
If the hash of a Bingo card duplicates an earlier hash, then there is a non-zero probability that the latter Bingo card duplicates an earlier Bingo card.
Note that duplicate hashes do not mean that two Bingo cards are duplicates. Rather, it means that a collision of hashes has occurred. However, two hashes that are not duplicates means that the associated Bingo cards are not duplicates.
If a duplicate hash is encountered, the newly created Bingo card is not added to the growing file of Bingo cards and a new Bingo card is generated.
3.1. Generation Rules
The values in a given column must adhere to the following rules:
- The 'B' column may contain only values from 1 - 15
- The 'I' column may contain only values from 16 - 30
- The 'N' column may contain only values from 31 - 45
- The 'G' column may contain only values from 46 - 60
- The 'O' column may contain only values from 61 - 75
No duplicate values may appear in any column.
The method responsible for generating the values in a card is populate_card_array.
public const int CARD_DATA_VALUES = 25;
public const int CARD_VALUES_AT = 128;
public const int CARD_VALUES_SIZE =
CARD_DATA_VALUES *
sizeof ( byte );
public const int CARD_SIZE = CARD_VALUES_SIZE;
public const int CENTER_CELL_INDEX = 12;
public const int COLUMNS = 5;
public const int ROWS = 5;
const int ALLOWED_IN_COLUMN = 15;
byte [ ] populate_card_array ( )
{
List < int > allowed = new List < int > ( );
byte [ ] bytes = new byte [ card_size ];
int cell = 0;
int index = 0;
for ( int column = 0;
( column < CONST.COLUMNS );
column++ )
{
allowed = Enumerable.Range (
( 1 + ( column * ALLOWED_IN_COLUMN ) ),
ALLOWED_IN_COLUMN ).ToList ( );
for ( int row = 0; ( row < CONST.ROWS ); row++)
{
index = random.Next ( allowed.Count );
bytes [ cell++ ] = ( byte ) allowed [ index ];
allowed.RemoveAt ( index );
}
}
index = random.Next ( star_indices.Count );
bytes [ CONST.CENTER_CELL_INDEX ] =
( byte ) star_indices [ index ];
return ( bytes );
}
For each column, populate_card_array first generates a list (allowed) that contains the values allowed by the generation rules for the current column. Note that Enumerable.Range [^] is defined in the System.Link namespace and requires the using statement "using System.Linq;". Then for each row, a random number [^], between 0 and the current number of values in the allowed list is generated. (Note that the value returned by random.Next is always less than allowed.Count.) This value becomes an index into the allowed list that points to a value to be inserted into the card array (bytes). When the value is inserted into the bytes array, it is removed from the allowed list. This insures that duplicates are not inserted into any column.
Note that populate_card_array generates 25 values although only 24 values are valid. The center square of the Bingo card is to contain a random number that is an index to the location of the star on the Bingo card. To obtain this value efficiently, prior to the execution of generate_cards_DoWork, initialize_star_indices is invoked to generate the allowed index values in star_indices.
void initialize_star_indices ( )
{
star_indices = Enumerable.Range (
0,
CONST.CARD_DATA_VALUES ).ToList ( );
star_indices.RemoveAt ( CONST.CENTER_CELL_INDEX );
}
Without initialize_star_indices the indices would have to be generated each time that a Bingo card was generated. populate_card_array randomly selects an index from star_indices and places that value in the center square.
3.2. Eliminating Duplicate Bingo Cards
The populate_card_array method insures that duplicate values do not occur in a Bingo card. However, there is another rule that must be satisfied — no two Bingo cards generated by this program may be duplicates. To this end, a hash of the values in a Bingo card array was needed.
The Bingo card is passed to generated_hash that generates and returns an unsigned 32-bit integer hash for the Bingo card array. The index of the center square (CONST.CENTER_CELL_INDEX) is passed as the exclusion index.
uint generated_hash ( byte [ ] bytes,
int exclude )
{
uint hash = 2166136261;
unchecked
{
for ( int i = 0; ( i < bytes.Length ); i++ )
{
if ( i == exclude )
{
continue;
}
hash = ( hash * 16777619 ) ^ bytes [ i ];
}
}
return ( hash );
}
The square that will have a star printed therein should not participate in the hash generation and so is excluded. The hash returned by generated_hash is passed to duplicate_hash.
3.3. Searching for Duplicate Bingo Cards
During the generation of Bingo cards, it is necessary to avoid duplicates. Recall that if two objects have different hash codes, the two objects are not equal. There is a problem in that all hashes, generated for all previously generated Bingo cards, must be compared against the hash of a newly generated Bingo card. The structure that this program uses for the storage of these hashes is a binary tree of unsigned integers named hashes. It is declared in the Find_Or_Add class of the Utilities project.
using System.Collections.Generic;
namespace Utilities
{
public class Find_Or_Add : List < uint >
{
private static List < uint > hashes = new List < uint > ( );
public bool find_or_add ( uint hash,
ref int hash_collisions )
{
bool found = true;
int position = this.BinarySearch ( hash );
found = ( position >= 0 );
if ( found )
{
hash_collisions++;
}
else
{
position = ~position;
this.Insert ( position, hash );
}
return ( found );
}
}
}
So if 400,000 Bingo cards were to be generated, hashes binary tree would have 400,000 nodes. Each time that a new Bingo card is generated, its hash must be computed and compared against the growing number of items in hashes.
using FOA = Utilities.Find_Or_Add;
⋮
FOA foa = new FOA ( );
⋮
bool duplicate_hash ( uint hash )
{
return ( foa.find_or_add ( hash,
ref hash_collisions ) );
}
In the case where duplicate_hash returns true, the do-while loop
do
{
bytes = populate_card_array ( );
hash = generated_hash ( bytes,
CONST.CENTER_CELL_INDEX );
} while ( duplicate_hash ( hash ) );
is executed again. If duplicate_hash returns false, the new Bingo card is written to the Bingo card file, and the next, if any, Bingo card is generated.
When all Bingo cards have been generated, the Bingo file header is written.
void emit_header ( )
{
byte [ ] bytes;
long header_offset = ( long ) ( int ) CONST.HEADER_AT;
bytes = header_values_to_byte_array ( version,
number_cards,
cards_start_at,
card_size,
date_created );
cfio.write_bytes_to_file ( bytes,
header_offset,
ref error_message );
}
emit_header invokes the helper header_values_to_byte_array to convert the individual values that make up the header into the byte array that will be written as the header.
byte [ ] header_values_to_byte_array ( int version,
int number_cards,
int cards_start_at,
int card_size,
int date_created )
{
using ( MemoryStream ms = new MemoryStream ( ) )
{
using ( BinaryWriter bw = new BinaryWriter ( ms ) )
{
bw.Write ( version );
bw.Write ( number_cards );
bw.Write ( cards_start_at );
bw.Write ( card_size );
bw.Write ( date_created );
return ( ms.ToArray ( ) );
}
}
}
4. Executing Generate_Cards
In order to execute, Generate_Cards requires the following information:
- The location where the Bingo card file is to be saved
- The number of cards to generate
To avoid permission issues, the default directory for Generate_Cards is C:\Users\Public\Bingo. When the Browse button is clicked, the existing files in the default directory will be displayed. Choosing an existing file will result in a warning like:
Once an output file is specified, the number of cards to be generated is solicited, the Go button is clicked and Generate_Cards executes to conclusion.
In this case, 800,000 cards were specified.
To verify the card generation, I utilize the ViewFile [^] tool.
The value 0x03 (3 decimal) is the version number; the value 0xC3500 (800,000 decimal) is the number of cards contained in this file; the value 0x80 (128 decimal) is the starting byte of the Bingo cards; the value 0x19 (25 decimal) is the number of bytes in each Bingo card; and 0x134B03D (20230205 decimal) is the date that this Bingo card file was created. The first card is visible at byte 128. If ViewFile were to display the left-side in decimal (by clearing the hexadecimal checkbox), the display would be the following.
Starting at byte 128, the first five bytes are the values of the first ('B') column; the next five bytes are the values of the second ('I') column; the next two bytes are the first two values of the third ('N') column; the next byte is the index of the star (4); the next two bytes are the last two values of the third ('N') column; the next five bytes are the values of the fourth ('G') column; and the next five bytes are the values of the fifth ('O') column.
If these values were to be placed onto a Bingo card, they would appear as in the following figure. This is what Print_Cards does and is the subject of the next article in this series.
Note that the values in these columns adhere to the prior generation rules.
Finally, I thought it best to validate the stars positioning. The data was collected from the Bingo card file and converted to a DataTable that was converted to a CSV file. The CSV file was opened by Excel and a graph of the data was plotted.
The result was what was expected: the distribution of stars was relatively even and there were no stars placed in the center square. The sum of all distributions was 800,000, the number of cards that were generated.
5. Conclusion
Generate_Cards produces a file containing unique Bingo cards. The next step is to print these cards under user specifications. This is the subject of the second article in this series.
6. References
7. Development Environment
The software presented in this article was developed in the following environment:
| Microsoft Windows 7 Professional Service Pack 1 |
| Microsoft Visual Studio 2008 Professional |
| Microsoft .Net Framework Version 3.5 SP1 |
| Microsoft Visual C# 2008 |
8. History
| Bingo - Part 1 of 3 - Generate Cards | 02/10/2023 | Original Article |
