Checksum programs (1996)
University of Queensland library number
checksum calculator. C version;
University of Queensland student number
C version;Python version
My first π program.
Turbo Pascal version (1990);
DOS compiled version (EXE);
C version (circa 1995)
Latin square and critical set programs
Critical sets in Latin squares were the subject of my PhD thesis in 2001 and many of my academic papers.
If you know Sudoku puzzles, Latin squares are a generalization of these - without the subsquare properties and restriction to nine different symbols.
Critical sets are minimal subsets of a Latin square that can uniquely determine the whole square. scs(n) and lcs(n) denote the smallest and largest critical sets in a Latin square of order n respectively.
Find large critical sets
Stinson and van Rees ("Some large critical sets", 1982) found that lcs(5) >= 10, lcs(7) >= 24, lcs(9) >= 39, and lcs(10) >= 55.
The algorithms developed in this program for searching for Latin squares and critical sets improved these bounds to lcs(5) = 11, lcs(7) >= 25, lcs(9) >= 45, and lcs(10) >= 57. (See relevant OEIS sequence.)
These algorithms were developed during the period 1998-2001.
Find trades in 3xn Latin rectangles
This is an implementation in C of the algorithm published in Cavenagh's paper "Latin trade algorithms and the smallest critical set in a Latin square" (2003).
Gurobi and C Source code for project in the paper: "The size of the smallest uniquely completable set in order 8 Latin squares"
6x6 Latin square main classes for program
7x7 Latin square main classes for program
8x8 Latin square main classes for program
This program finds the size of the smallest critical set in a Latin square of order up to 8. It uses the concept of Latin trades (interchangeable sets in Latin squares) and 0-1 integer programming to
determine the smallest critical set size in a representative ("main") class of Latin squares (there are 283,657 main classes of 8x8 Latin squares).
Using this algorithm in 2002-2003 on approximately 200 computers over a period of four months with LP solvers such as CPLEX and BonsaiG, I determined that scs(8) = 16.
The resulting paper was published in the Journal of Combinatorial Mathematics and Combinatorial Computing in 2005.
In 2011 I reimplemented the program using the Gurobi solver and reran it over a few months on one MacBook Pro laptop.
The paper was cited in McGuire et al's proof that There is no 16-Clue Sudoku - where "Latin trades" are referred to as "unavoidable sets".
Count chess positions at small depths
I wrote these programs in 2002-2003 to calculate the value of perft(10) - the number of possible chess games at the end of the 10th ply, or the number of possible chess games after 5 moves by each
side from the initial position. In order to avoid mistakes, I wrote move generators using both the 8x8 array and "x88" approach.
This value is 69,352,859,712,417 and this program was the first to (publicly) calculate this value (also see Computer Chess Club post from 2003).
It was written from scratch and uses the balanced binary tree library of Vixie and Wirth.
It was also the first program (also in 2003) to (publicly) calculate the number of checkmates at plies 7 and 8. The value at ply 6, 10,828, was computed in 1897.
Other OEIS sequences I updated as a result were Number of chess games with n plies (another version), Number of distinct chess positions after n plies including differences due to availability and possibility of castling and en passant captures, and Number of possible chess diagrams after n plies.
Back in 2000 I entered a competition for writing the smallest x86 assembly "Prime Finder" program. Most people's code was much smaller and for some strange reason
my code didn't make the time limit. A bit later I decided to do it in C.
I think I did very well with 78 characters but there was lots of discussion about what
was legal and what was not. The code looked very IOCCC like. Dennis Ritchie (RIP) got involved in the thread.