Solving the eight queens puzzle

In the eight queens puzzle, you need to place eight queens on a chessboard so that they aren’t attacking eachother. It has 92 solutions.

I implemented one method for solving the problem. It works for any nxn chessboard, but it’s not so fast with large boards.

You can invoke this with java -jar Queens.jar for an 8×8 board, or java -jar Queens.jar n for an nxn board with n queens.

It works by processing the board in vertical strips, first placing a queen in the top-right, and then attempting to place a queen in the second column at the first available space. Once it crosses the board like this, it has found a solution, but it goes through plenty of bad combinations first.

Update: online solution-viewer is now running to make that command-line output more useful.

Beautiful QR Codes

The verdict is in. QR codes are ugly. But they don’t have to be. Check out the modified code featured on this Wikipedia article. You don’t need to be a QR Code expert to do something like that.

The basic idea is that QR codes have error Correction. We can generate codes which store the data in multiple places, so that scanners will still read them if they are damaged.

Scripting the whole operation

Tedious image editing is not my cup of tea, so I made a PHP class to apply some templates to QR codes and add a centred logo for us.

Note: If you don’t have ImageMagick for PHP, read this page. On Ubuntu, apt-get install php5-imagick worked fine for me.

This is the basic formula:

QR Code + Template + Logo = Pretty PR Code

First we need the QR code. It is best generated with the phpqrcode library. Adding the logo wont work unless we use high error correction (H):

QRcode::png("", "code.png", 'H', 8, 0);

After that, code.png looks like this:

Now the templates. Note that we used 8×8 pixels per block and 0 for the border above. The resulting code may line up with one of these templates, adding white lines over the image. Save these images to a ‘template’ folder:

Next, the logo. We have one of those:

Time for the code. This class will do most of the work. Just check the template folder contains an overlay that fits your code.

class QR_Pretty {
	public $template_base = "template/template-{SIZE}.png";
	public $qr = false;
	public $geometry = false;

	function prettify($file, $logo, $output = '') {
		/* Load image */
		$this -> qr = new Imagick();
		$this -> qr -> readImage($file);
		$this -> geometry = $this -> qr -> getImageGeometry();

		/* Perform modifications */
		$this -> add_template();
		$this -> add_logo($logo);

		/* Output image */
		if($output != '') {
			$this -> qr -> setImageFileName($output);
		$this -> qr -> writeImage();

	private function add_template() {
		/* This will overlay a template containing white lines,
			to make the QR codes look less code-ful */
		$size = $this -> geometry['width'];
		$template_filename = str_replace("{SIZE}", $size, $this -> template_base);
		$template = new Imagick();
		$template -> readImage($template_filename);
		$this -> qr -> compositeImage($template, imagick::COMPOSITE_OVER, 0, 0 );

	private function add_logo($logo_file = false) {
		/* This places a logo in the middle of the QR code,
			64x64 would be advisable :) */
		if(!$logo_file) {
			/* No logo to add */
			return false;
		$logo = new Imagick();
		$logo -> readImage($logo_file);
		$logo_size = $logo -> getImageGeometry();
		$x = ($this -> geometry['width'] - $logo_size['width']) / 2;
		$y = ($this -> geometry['height'] - $logo_size['height']) / 2;
		$this -> qr -> compositeImage($logo, imagick::COMPOSITE_OVER, $x, $y);

To use the above class is quite simple. Once you have code.png, logo.png, and a folder full of templates, just do this:

$qr = new QR_Pretty();
$qr -> prettify("code.png", "bitrevis.png", "pretty.png");

That gives us pretty.png, which looks like this:

Thanks to that error correction, this picture still scans and takes us to Slightly larger logos can be used, but 64×64 looks good and scans reliably. Try embedding logos with transparency too!

This means no more excuses for ugly QR codes. Integrate this into your scripts right away.

On the price of watermelons

Watermelons are huge, cheap, and contain a lot of water. The edible part is about 92% water. I wanted to find out whether water from watermelons is cheaper than bottled water at the supermarket.

I compared prices with other beverages, each is the cheapest in its category. Because prices change all the time, these numbers should be taken with a grain of salt:

Item Price per litre (AUD)
Home Brand Cordial (diluted 1:4 with free water) 0.23
Water 0.46
Cheap soft drink 0.63
Milk 0.89
Watermelon Juice 1.05
Tropical Juice 1.90
Lipton Iced Tea 2.57

So it’s settled. You wouldn’t save anything juicing watermelons unless you usually buy natural juice, which it turns out quite pricy!

This is how I got the price of a litre of watermelon water:

Water is 997.1kg/m3 (0.9971g/mL) at 25°C
1000mL * 0.9971g/mL = 997.1g water
997.1g / 91.45% = 1090g watermelon
1.090kg * 96c/kg = 1.05c/L for watermelon water.

This is not science: I ignored the watermelon rind, and the 6.2g / 100g of sugars which would be dissolved in the water. If anybody juices a watermelon in a lab then I will revise these numbers.

Samoan Language Section

I’ve now uploaded my Samoan vocabulary (~1200 words), and unfinished introductory guide. The audio works in Firefox on Ubuntu, but I haven’t tested it in other browsers.

I have around a thousand words and a few hundred examples which I haven’t recorded yet, and the guide/phrases contain many unfinished sections. If you are a native speaker of Samoan, or are interested in helping, then let me know.

You can find the section at:

Update: I’ve made MP3 versions of the audio files, and they can now play in all major browsers.

Using speech synthesis in AGI apps

For some of my telephone apps, stringing together pre-recorded messages is a pain, and it’s not even useful for more dynamic content. This is how I got PHP to do sound output via festival whilst using the asterisk AGI.

First, I made a folder called agi in my /var/lib/asterisk/sounds/en/. This is where we will cache sound files.

This shell script makes a sound file with your text, and saves it in that directory:

echo "$1" | text2wave -otype ulaw -o /var/lib/asterisk/sounds/en/agi/$2.ulaw

For the PHP side, we just use MD5 to name the files based on their contents, and only run the shell script if no file has been created with the text we want.

In this project, $agi refers to an instance of PHP AGI. (highly recommended)

function sayNow($string, $escape = "") {
	global $agi;
	$sounds_path	= "/var/lib/asterisk/sounds/en/agi/";
	$agi_path	= "/var/lib/asterisk/agi-bin/"
	$fn = md5($string);
	$string = str_replace(""", "", $string);
	$string = str_replace(";", ",", $string);
	$string = str_replace("'", "", $string);
	$string = str_replace(""", " slash ", $string);
	if(!file_exists("$sounds_path$fn")) {
		system("$agi_path$common/ "$string" "$fn"");
	return $agi -> stream_file("$sounds_path$fn", $escape);

This makes sound output at least a million times easier. We use it like this:

$a = sayNow("Enter the number, then press hash");

That’s all there is to it. I should probably also set up a cron job to clear the sound files at the end of each week.

Converting Numbers To Words in PHP

This is a straightforward coding task. I’m working on some maths code in PHP, and need a function to output “twenty-five” for 25, “fifteen” for 15, etc. A quick google search pulled up a neat little PEAR package which can do this.

The results weren’t as flash as I’d hoped though. We ended up with this:

894: eight hundred ninety-four

So it turns out that the PEAR class doesn’t print commas or the word ‘and’ in its numbers. We will be feeding our numbers to festival, and also using them for maths questions. Those pesky ands and commas are a must for this project, so this is not good enough:

9539: nine thousand five hundred thirty-nine

Instead, I need:

9539: nine thousand, five hundred and thirty-nine

I found some commented out code, and tried my own modifications, but it wasn’t working right, so I scrapped the PEAR class and started from scratch, using Wikipedia to populate the lists:

The results were perfect. It took about 300 lines to replace the class, and it handles ordinal numbers too. (‘1st’ = ‘first’, ‘100th = one hundredth’, etc). I ditched the currency feature.

To download the replacement class, click here.

It’s simple to use, just express ridiculous numbers or long decimals as strings to avoid errors. See this example for features:

 // one
echo Numbers_Words::toWords(1); newline();

 // two
echo Numbers_Words::toWords(2); newline();

 // twenty-five
echo Numbers_Words::toWords(25); newline();

 // one thousand
echo Numbers_Words::toWords(1000); newline();

 // one thousand and one
echo Numbers_Words::toWords(1001); newline();

 // one hundred thousand and one
echo Numbers_Words::toWords(100001); newline();

 // one hundred and twenty-three million, four hundred and fifty-six thousand, seven hundred and eighty-nine
echo Numbers_Words::toWords("123 456 789"); newline();

 // thirty-six point nine seven
echo Numbers_Words::toWords(36.97); newline();

 /* nine novemvigintillion, eight hundred and seventy-two octovigintillion, three hundred and fourty-eight septemvigintillion,
	nine hundred and seventy-two sesvigintillion, four hundred and ninety-two quinquavigintillion,
	three hundred and eighty-four quattuorvigintillion, nine hundred and two tresvigintillion,
	three hundred and eighty-four duovigintillion, two hundred and ninety unvigintillion, three hundred and eighty-four vigintillion,
	two hundred and ninety novemdecillion, three hundred and fourty-two octodecillion, five hundred and sixty-three septendecillion,
	four hundred and seventy-five sexdecillion, six hundred and thirty-four quindecillion, eight hundred and fifty-seven quattuordecillion,
	four hundred and fifty-seven tredecillion, three hundred and fourty-nine duodecillion, eight hundred and fifty-seven undecillion,
	two hundred and thirty-four decillion, five hundred and twenty-three nonillion, five hundred and thirty-four octillion,
	eight hundred and fifty-three septillion, two hundred and ninety sextillion, four hundred and seventy-eight quintillion,
	two hundred and ninety quadrillion, three hundred and fourty-seven trillion, two hundred and thirty-eight billion,
	nine hundred and fourty-six million, five hundred and thirty-eight thousand, four hundred and seventy-six */
echo Numbers_Words::toWords("9872348972492384902384290384290342563475634857457349857234523534853290478290347238946538476"); newline();

 // seventeenth
echo Numbers_Words::toWords("17th"); newline();

 // eight hundred and sixty-third
echo Numbers_Words::toWords("863rd"); newline();

 // negative seventy-eight point four
echo Numbers_Words::toWords("-78.4"); newline();

function newline() {
	echo "<br />n";

Using correct strings makes synthetic voices much less annoying, and nobody can complain about bad maths questions. 🙂

Scripting Windows Shares

As much as I try to avoid it, sometimes I need to use Windows servers, and windows .bat files aren’t exactly the pinnacle of scripting languages. This post is about bulk-sharing home directories with consistent permissions.

As I’m a reformed Visual Basic programmer, so I decided to solve this in PHP rather than VB script.

This crude script will make a batch file to share every subdirectory (ie, hundreds of users’ home directories), and also delete desktop.ini from each of them them. Save the code below as magic.php, run it, and then run tricks.bat.

$stuff = whats_here();
$tricks = fopen("tricks.bat", "w");
foreach($stuff as $folder) {
	$line = do_things($folder);
	fwrite($tricks, $line);

function do_things($folder) {
	$things .= ":: $folderrn";
	$things .= "net share $folder /DELETErn";
	$things .= "net share $folder=".getcwd()."\$folder /GRANT:EVERYONE,FULLrn";
	$things .= "del /Q $folderdesktop.inirnrn";
	return $things;

function whats_here() {
	/* List directories in this one */
	$here = opendir(getcwd());
	$dir  = array();
	while($kid = readdir($here)) {
		if(is_dir($kid) && $kid != "." && $kid != "..") {
			$dir[] = $kid;
	return $dir;

I’ve heard that Windows PowerShell is pretty useful once you get used to it, but Windows sysadmins seem to dislike scripting as much as I dislike using repetitious GUI interfaces. Oh well, a couple of PHP scripts wont hurt. 🙂

Loading OEIS integer sequences

To show that interpreted languages can be fast when used well, I’m posting this example.

Take the On-line Encyclopedia of Integer Sequences database, which is a collection of integer sequences. That means lists of numbers. You can get a file from, which contains the first few numbers of each sequence. Today’s file extracts to about 38MB.

Now I need to do lookups in this file for a program I’m writing, and that program is in PHP. We want to know some sequences based on their A-number, like this:

$primes = oeis("A000040");
$fibonacci = oeis("A000045");

If we’re smart about it, then even a large file can be parsed in fractions of a second. Here’s how we do it:

/* This code needs an extract of the OEIS database to operate.
	I got it from
	Just extract that to this folder for lookups */
function oeis($number) {
	/* Return an array of values based on a sequence's OEIS number */
	$number = strtoupper($number);
	$fp = fopen("stripped", "r");
	while($ln = fgets($fp)) { /* Find this sequence and break the loop */
		if(substr($ln, 0, strlen($number) + 1) == $number." ") {
			$res = $ln;
	/* Exit if we haven't got anything */
	if(!isset($res)) { return false; }
	$rv = explode(" ", $ln); /* Split lines into left and right of space */
	$ln = trim($rv[1]);
	$ln = substr($ln, 1, strlen($ln)-2); /* Slices off extra commas on sides */
	$rv = explode(",", $ln); /* Split by commas */
	return $rv;

Note that we don’t use explode() until after we have found the line we need, and also note that file_get_contents() is not used at all. (Multi-megabyte strings will bog you down in any language).

Parsing Asterisk Configuration

If you are writing for Asterisk PBX, you may feel the need to create a public telephone directory.

Today we’ve been putting together Phonebook, a web-based phonebook which pulls data from an asterisk server. We used JQTouch for the interface, with PHP to process data files. We also use a CSV file exported from our hosted gmail to ensure that people’s names are spelled correctly.

The configuration

Asterisk’s configuration files are INI-like, and you’ll find them in /etc/asterisk/ on most systems. Just one important thing though, asterisk lets you use brackets ( ) in caller-IDs, etc, which will cause PHP’s parse_ini_file() function to fizzle out and die due to an alleged syntax error.

To save yourself some trouble, use this little class I wrote, which will load INI data into an associative array:

class ns_ini_parser {
	/* Mike's non-standard INI parser for asterisk files.
		Note that PHP's parse_ini_file will die with a syntax error on key = value (bracket), which is unacceptable */

	function parse_string($string) {
		$lines		= explode("n", $string);
		$section	= "0";
		$result		= array();
		foreach($lines as $line) {
			$line = trim($line);
			if($line == "" || substr($line, 0,1) == ";") {
				/* Comment, no action */
			} elseif(substr($line, 0,1) == "[") {  /* [section] */
				$l		  = strlen($line);
				$line		  = trim(substr($line, 1, $l - 2));	/* Strip brackets */
				$section	  = $line;
				if(!isset($result[$section])) {
					$result[$section] = array();
			} else {				/* key = val */
				$parts = explode("=", $line);
				$key = trim($parts[0]);	/* The key is everything left of the equal */
				unset($parts[0]);	/* Got that, unset it */
				$val = trim(join("=", $parts));	/* Value is everything on the righht */
				$result[$section][$key] = $val;
		return $result;

	function parse_file($path) {
		$string = file_get_contents($path);
		return $this -> parse_string($string);

The example usage below will list user’s extensions next to their caller ID, which you could use for a web phonebook:

/* Example PHP code to parse asterisk configuration */
$config_parser = new ns_ini_parser;
$users  = $config_parser -> parse_file("/etc/asterisk/users.conf");

foreach($users as $id => $user) {
	if(is_numeric($id)) { /* Only show numbers, not other sections */
		echo "<a href="tel:$id">$id</a> ".$user['fullname']."<br />";

I don’t think it gets easier than that! I’ll post the rest once you can manage the contacts as well.

Some scripts to make word puzzles


I’ve put together a couple of PHP scripts to make puzzles. The humble find-a-word, a word scrambler, and a cipher.

The output is just HTML, so you can include them on web-pages if you like (look there’s one over there! :o)

I still need to write a command-line interface, as making a find-a-word large enough to hold every single word in the English dictionary is a bit too much for one page-load.

But hey does that sound fun or what? I’m going to market word-search wallpaper!