# Slightlly OT - Bingo problem

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
I may have mentioned that I run an Introduction to PHP course at a local
college (very basic - I'm no PHP expert).  Well, one of my students was
doing really well so I set him some extension work.  The task was to use
PHP to generate a random bingo card.  The standard UK card has nine rows
and three columns.  Each row has five numbers.  All numbers are
different, out of a pool of 90.

I asked my student to design one card.  He came back a few days later
with a solution that generated six cards, using each of the90 numbers
just once.  Or so I thought.

Although I'd set the problem I had not coded the solution myself so I
set to it.  I tried various methods but could not get a script which
would work reliably every time.  More often than not I could not get all
the numbers to fit.  I eventually solved the problem by brute force, ie
I discard all attempts that don't work.  See
http://www.ckdog.co.uk/php/test/bingo.php for my solution
Code is here:
http://www.ckdog.co.uk/php/test/bingo_code.phps

I was still smarting because I thought my student had come up with a
better solution than me so I took another look at his.  He had the same
problem, occasionally, the last line was not complete.  It's a bit like
the card game patience, sometimes it doesn't work out.  If you are
reading this Craig, don't look at my solution  :-)

The question I have is this.  Is it possible to write an algorithm that
will place all 90 numbers in the matrix in a random fashion that will
not have to loop because of failed attempts?

--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker /

## Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:

I guess you mean three rows and nine columns (so that 5 numbers in each
row sum up to 15 numbers per card).

<snip>

This solution seems trivial to me, so it must be wrong:

1. Generate a random permutation of the 90 numbers.
(Google knows how to do it.)

2. Split the permutation in 6 blocks of 15 numbers.

3. Sort each block.

4. Assign each block to a card.

Am I missing something?

## Re: Slightlly OT - Bingo problem

contained the following:

Doh! Yes of course.  I've been working on this too long...

Yes, I didn't give you all the information.  The columns represent the
ranges 1-9, 10-19, 20-29, and so on up to 80-90 for the last one.

It follows then that for each card there cannot be more than 3 numbers
from each range.

--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker /

## Re: Slightlly OT - Bingo problem

.oO(Geoff Berrow)

There's a mathematical approach for doing that (can't remember exactly,
would have to look it up), but PHP is already capable of doing it.

A quick 'n dirty hack:

<?php
// too lazy to write HTML tables ... ;-D

// create array with 90 numbers, ordered randomly
\$numbers = range(1, 90);
shuffle(\$numbers);

// create six cards
for (\$i = 0; \$i < 6; \$i++) {
// get 15 numbers for each card and fill up to 27 with empty elements
\$card = array_pad(array_slice(\$numbers, \$i * 15, 15), 27, 0);
// randomize positions on the card
shuffle(\$card);
// print the card out
for (\$j = 0; \$j < 27; \$j++) {
print \$card[\$j] != 0 ? sprintf(' %02u', \$card[\$j]) : ' ..';
print (\$j + 1) % 9 ? '' : "\n";
}
print "\n\n";
}
?>

HTH
Micha

## Re: Slightlly OT - Bingo problem

.oO(Michael Fesser)

OK, I missed that 5-per-row issue (never played Bingo), but it should
not be hard to add.

Micha

## Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:

Something like this?

http://www.jwscripts.com/playground/bingo.phps

JW

## Re: Slightlly OT - Bingo problem

from Janwillem Borleffs contained the following:

Nice but I forgot to give you all some information.

The numbers have to be aligned so that people can mark them off easily.
That means 1-9 go in column 1, 10-19 in column 2 20-29 in column 3 and
so on.  The last column has numbers in the range 80-90

--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker /

## Re: Slightlly OT - Bingo problem

from Geoff Berrow contained the following:

However, it also prints the same cards each time.
--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker /

## Re: Slightlly OT - Bingo problem

Geoff Berrow wrote:

Actually it doesn't (try http://www.jwscripts.com/playground/bingo.php ).

If you want the numbers more random than they currently are, use seeding as
described on:

http://www.php.net/manual/en/function.mt-srand.php

JW

## Re: Slightlly OT - Bingo problem

from Janwillem Borleffs contained the following:

No you are right, but it still doesn't comply with the other rules.

--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker /

## Re: Slightlly OT - Bingo problem

I think he might have caught on to the trick - there's a Bingo post on
alt.comp.lang.php ;-)

--
<http://www.andyhsoftware.co.uk/space Space: disk usage analysis tool

## Re: Slightlly OT - Bingo problem

from Andy Hassall contained the following:

He has. <g>

--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker /

## Re: Slightlly OT - Bingo problem

.oO(Geoff Berrow)

Another idea ...

It should be possible to set all numbers on all six cards in a way
similar to the eight-queens-problem.

There are some defined constraints on the rows and columns, which can be
easily checked:

* There are 18 rows, splitted into 6*3. Each row holds 5 numbers.
* There are 9 columnss, the first contains the numbers 1-9, the next
10-19 and so on, the last one contains 80-90. So you always know which
column a number belongs to, you just have to find a row that isn't
completed yet (has less than 5 numbers).

So consider all six 9*3 cards as one single 9*18 card, then it should be
as follows:

* Get a number.
* Determine its column.
* Put it in the first row that has less than 5 numbers.
* Move on to the next number.

If at some point a number can't be set because there's no free row
available for the required column, step back to the last set number and
change their position, then continue from there (and if the position
can't be changed anymore move back another step). This backtracking is
quite easy to do with recursive algorithms.

Just the basic idea ...

Micha

## Re: Slightlly OT - Bingo problem

Michael Fesser wrote:

Without recursion my algorithm often (*) fails for the last few numbers

(*) I haven't had a run for the whole 90 numbers :-)

================================================
<?php
function row_ok(\$x, \$number) {
if (count(\$x) == 5) return false;
\$lo = (int)(\$number/10) * 10;
if (\$lo == 90) \$lo = 80;
\$hi = \$lo + 9;
if (\$lo == 80) \$hi = 90;
foreach (\$x as \$v) {
if ((\$lo <= \$v) && (\$v <= \$hi)) {
return false;
}
}
return true;
}

function insert_number(&\$c, \$number) {
if (count(\$c[0]) + count(\$c[1]) + count(\$c[2]) == 15) {
return false; /* if card is full */
}
\$initial_row = \$row = rand(0, 2);
while (!row_ok(\$c[\$row], \$number)) {
++\$row;
if (\$row == 3) \$row = 0;
if (\$row == \$initial_row) return false;
}
\$c[\$row][] = \$number;
return true;
}

function print_cards(&\$cards) {
print_r(\$cards);                        /* I'm lazy :-) */
}

\$cards = array(
array(array(), array(), array()),       /* ******************** */
array(array(), array(), array()),       /* six cards            */
array(array(), array(), array()),       /*                      */
array(array(), array(), array()),       /* with three rows each */
array(array(), array(), array()),       /*                      */
array(array(), array(), array()),       /* ******************** */
);

\$numbers = range(1, 90);

foreach (\$numbers as \$n) {
\$initial_card = \$card = rand(0, 5);
while (!insert_number(\$cards[\$card], \$n)) {
++\$card;
if (\$card == 6) \$card = 0;

/* without recursion this algorithm fails: stop it */
if (\$card == \$initial_card) {
echo 'last inserted number: ', \$n-1, "\n";
print_cards(\$cards); exit();
}
}
}

print_cards(\$cards);
?>

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com /
== ** ## !! ------------------------------------------------ !! ## ** ==
may bypass my spam filter. If it does, I may reply from another address!

## Re: Slightlly OT - Bingo problem

from Michael Fesser contained the following:

That's what my solution does.

Yes, I wondered if some backtracking might work, but my earlier versions
only failed on the last few numbers. Right now, if it fails I just run
the whole thing again.  Since this works it is probably 'good enough'
but I'm just after something a bit more elegant.
--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker /

## Re: Slightlly OT - Bingo problem

.oO(Geoff Berrow)

I tried, and it failed impressingly. ;)

I underestimated the complexity of setting 90 slots on a 9*18 card, so
that each row contains 5 and each column 10 (except for the first and
last) slots.

Currently I think your trial-and-error method will lead faster to a
result than a more systematic and deterministic approach.

Micha

## Re: Slightlly OT - Bingo problem

Michael Fesser wrote:

hehe, me too -- but I haven't given up, not just yet.

Just to make matters more difficult, can a card have 0 (zero) or three
numbers in a range? According to the original post, it can -- but do
*real* bingo cards have empty or full columns?

example:

-- 12 23 -- -- 56 61 -- 82
03 16 28 31 -- -- -- 78 --
07 17 -- 36 -- -- 64 -- 90
^^       ^^
(full)   (empty)

And (for printing only) are the numbers in each column ordered?

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com /
== ** ## !! ------------------------------------------------ !! ## ** ==
may bypass my spam filter. If it does, I may reply from another address!

## Re: Slightlly OT - Bingo problem

I noticed that Message-ID:
contained the following:

As I understand it, yes.  I'll try to get a real card later and check.

--
Geoff Berrow (put thecat out to email)
It's only Usenet, no one dies.
My opinions, not the committee's, mine.
Simple RFDs http://www.ckdog.co.uk/rfdmaker /

## Re: Slightlly OT - Bingo problem

Pedro Graca wrote:

Latest code finds cards taking between
an instant and /a long time/ on my 500MHz PC:

Sample run:

*    bingo\$ php bingo.php
*    07 17 24 37 47 -- -- -- --
*    -- 12 27 -- -- -- 63 73 80
*    05 13 26 -- 43 -- -- 72 --
*
*
*    -- 16 23 35 -- 53 -- 76 --
*    08 -- 21 38 -- 55 -- -- 83
*    -- 19 22 31 -- 54 -- -- 81
*
*
*    -- -- -- -- 44 51 68 79 86
*    -- -- 20 -- 45 -- 66 75 88
*    01 18 -- -- -- 50 62 -- 87
*
*
*    -- -- -- 39 -- 57 60 70 85
*    -- -- 25 -- -- 58 64 77 84
*    02 14 29 -- 48 52 -- -- --
*
*
*    03 -- -- 30 49 -- 61 -- 90
*    -- 11 -- 34 42 59 67 -- --
*    04 -- -- -- 46 -- 65 78 89
*
*
*    09 10 28 33 41 -- -- -- --
*    06 15 -- 32 -- 56 -- 71 --
*    -- -- -- 36 40 -- 69 74 82

== bingo.php =========================================

<?php
define('STOP_NUMBER', 90);

function can_insert_at_row(&\$row, \$n) {
if (count(\$row) == 5) return false;
\$lo = ((int)(\$n/10)) * 10;
if (\$lo == 90) \$lo = 80;
\$hi = \$lo + 9;
if (\$lo == 80) \$hi = 90;
\$cnt = 0;
foreach (\$row as \$v) {
if ((\$lo <= \$v) && (\$v <= \$hi)) ++\$cnt;
}
return (\$cnt == 0);
}

function can_insert_at_card(&\$card, \$n) {
if (count(\$card[0]) + count(\$card[1]) + count(\$card[2]) == 15) return false;
\$lo = ((int)(\$n/10)) * 10;
if (\$lo == 90) \$lo = 80;
\$hi = \$lo + 9;
if (\$lo == 80) \$hi = 90;
\$cnt = 0;
foreach (\$card as \$row) {
foreach (\$row as \$v) {
if ((\$lo <= \$v) && (\$v <= \$hi)) ++\$cnt;
}
}
return (\$cnt < 3);
}

function insert_number_R(&\$cards, \$n) {
/* for all cards, in random order */
\$ini = mt_rand(0, 5);
\$end = \$ini + 6;

for (\$i = \$ini; \$i < \$end; ++\$i) {
\$ii = \$i%6;
if (can_insert_at_card(\$cards[\$ii], \$n)) {
/* for all rows, in random order */
\$ini_r = mt_rand(0, 2);
\$end_r = \$ini_r + 3;

for (\$j = \$ini_r; \$j < \$end_r; ++\$j) {
\$jj = \$j%3;
if (can_insert_at_row(\$cards[\$ii][\$jj], \$n)) {
/* insert it */
\$insert_index = count(\$cards[\$ii][\$jj]);
\$cards[\$ii][\$jj][\$insert_index] = \$n;

if (\$n == STOP_NUMBER) return true;

/* and recurse for 1 + \$n */
/* returning (with true) if recursive call returned true */
if (insert_number_R(\$cards, 1 + \$n)) return true;

/* remove \$n */
unset(\$cards[\$ii][\$jj][\$insert_index]);

/* backtrack to the previous x9 number */
if (\$n == 89) return false;
if (\$n % 10 != 9) return false;
}
}
}
}
/* and return false (to backtrack) if all cards have been tried */
return false;
}

function print_cards(&\$cards) {
foreach (\$cards as \$card) {
foreach (\$card as \$row) {
\$last = 0;
foreach (\$row as \$n) {
\$group = (int)(\$n/10);
if (\$group == 9) \$group = 8;
while (\$last < \$group) { echo "-- "; ++\$last; }
printf("%02d ", \$n);
\$last = \$group+1;
}
while (\$last++ < 9) echo "-- ";
echo "\n";
}
echo "\n\n";
}
}

\$cards = array(
array(array(), array(), array()),       /* ******************** */
array(array(), array(), array()),       /* six cards            */
array(array(), array(), array()),       /*                      */
array(array(), array(), array()),       /* with three rows each */
array(array(), array(), array()),       /*                      */
array(array(), array(), array()),       /* ******************** */
);

if (!insert_number_R(\$cards, 1)) echo "Could not do it. Sorry!\n\n";
else print_cards(\$cards);
?>

--
Mail to my "From:" address is readable by all at http://www.dodgeit.com /
== ** ## !! ------------------------------------------------ !! ## ** ==
may bypass my spam filter. If it does, I may reply from another address!

## Re: Slightlly OT - Bingo problem

Pedro Graca wrote:

<snip>

Is it about creating 6 cards or just 1 card? Anyway, I don't find it
to be difficult if you use shuffle-pick-remove logic.

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com    Blog: http://rajeshanbiah.blogspot.com /