Hi

I wrote a BBC BASIC program to generate UK style 90 number bingo tickets.

For those of you who don't know what these look like, here's a description.

On one page are 6 grids, one above the next with a gap between. Each grid is 9 cells wide by 3 cells deep.

The numbers 1 to 90 are used once only. In the first column are the numbers 1 to 9, the second column has numbers 10 to 19, etc, all the way to the 9th column which has numbers 80 to 90 in it.

Now there are some constraints, and these are the bit where it becomes almost impossible to fill the grid in one pass without having to swap some cells or starting again.

I've tried to draw up some grids with a pen and paper and fill them manually but it gets quite difficult near the end.

The constraints are:

1) Every row must have exactly 5 numbers in it.

2) The 3 cell high column in each ticket must have between 1-3 numbers in it but never zero numbers.

3) In each 3 cell high column, the numbers are sorted with lower numbers higher than larger numbers.

4) All the numbers 1 to 90 are used only once in each set of 6 tickets.

The method I have tried is as follows:

1) Loop 9 times through:

2) Pick a column randomly that hasn't been completed already.

3) Fill random positions in the whole set of 6 tickets within that column with the numbers that are in that column, checking that there are not already 5 numbers in that row.

4) After placing all numbers, check there are no tickets with zero numbers in that column.

5) A few other space checks

6) If there are any errors we delete the numbers placed and go back to step 3.

7) Mark column as completed.

Until all columns are completed.

This is quite quick, but is using a brute force approach to achieve the goal. I'd like to re-think the algorithm to make sure it is guaranteed that it completes first time every time without having to erase numbers and try again, but I just can't think how this would be achieved.

Anyone fancy a non-fractal related challenge of trying to do better. It doesn't need to be written in BASIC, essentially any language is fair game.

I have a suspicion that even APL would have been able to do this, but I have only ever scratched the surface of examining this language.

Simon