Binary is the new Sudoku

A couple of days ago somebody sent me an e-mail asking if I could write a program that generates binary puzzles. I didn’t know what binary puzzles were, but a search in google quickly led me to this site. Apparently, the “Binary” is a new kind of logic puzzle that involves only the numbers zero and one.

The goal is to fill in the grid with zeros and ones with the following restrictions:

  • There are as many zeros as ones in every row and every column.
  • No more than two of the same numbers can be next to or under each other.
  • Rows or columns with the same content are not allowed.

Every puzzle has a unique solution, which in this case is:

The program I wrote uses the following algorithm to generate new puzzles. First it fills a grid with random zeros and ones in such a way that all restrictions apply. Then it removes numbers randomly while making sure that the puzzle maintains exactly one solution. When it has removed the right amount of numbers the puzzle is shown on screen. Click here to download the jar (source files are included) and read on for instructions on how to use the program.

Continue reading

Checkers game

Long, long time ago, when I was still a full time student, I once became first in a checkers cup with a program I wrote. Alas, those days of glory are over. Looking back, the program was pretty simple. Choosing an efficient board representation made generating the moves a piece of cake and my program didn’t make use of any opening libraries or endgame strategies. It just implemented minimax search with alpha-beta pruning. Although it wasn’t really sophisticated, I still think the program was pretty sweet and I felt disappointed when I realized I had lost the source code. That’s why I decided to implement this game again only this time in Java (the original was written in C++). I fired up NetBeans and this is the result.

Geek Jewelry

I’ve been programming in the Java language for more than 10 years now, but I never got around to getting myself certified. That is until last month when I did the Sun Certified Programmer for the Java 2 Platform exam. Today the mail delivered an envelope from Sun Microsystems containing my SCJP certificate, a card stating I’m a Sun Certified Professional and best of all a neat pin.

L-Systems

In a previous post I spoke about JavaLogo. When talking about “turtle graphics”, L-systems automatically come to mind. For those who don’t know, L-systems or Lindenmayer systems are a mathematical formalism proposed by the biologist Aristid Lindenmayer in 1968 as a foundation for an axiomatic theory of biological development. More recently, L-systems have found several applications in computer graphics.

Central to L-systems, is the notion of rewriting, where the basic idea is to define complex objects by successively replacing parts of a simple object using a set of rewriting rules or productions. The rewriting can be carried out recursively.

Take the following example:

Axiom: F++F++F
Rewrite rule: F -> F-F++F-F

Now we come to the point where its relation with “turtle graphics” becomes apparent. The F, means draw a line forward. +, means turn left, – means turn right. When we apply the rewrite rule 4 times and when turning left or right always turn 120°, drawing the L-system’s turtle graphics gives us the following figure which is called the Koch Snowflake.

Koch Snowflake

Another example of a L-system is

Axiom: F+F+F+F
Rewrite rule: F -> FF-F-F-F-F-F+F

Applying the rewrite rule 4 times and always turning 90°, gives us this figure:

lindenmayer2.gif

When you’re looking at creating interesting figures with “turtle graphics”, checking out Lindenmayer systems further might prove worthwhile. Take a look at some examples I made using JavaLogo.

For more info:

JavaLogo

The MIT isn’t the only university that’s putting free course materials on the web, the Dutch Open University is doing the same. One of the courses they have published so far is an introduction to (Java) programming. Java isn’t the easiest language to start programming in when you’re a complete newbie, but the designers of this course have taken an interesting approach. From this course’ website you can download a JavaLogo.jar file that contains some classes that allow you to code in a LOGO kind of way. The most famous feature of LOGO is it’s “turtle graphics”. Take a line of code like this one:

REPEAT 4 [FD 100 LT 90]

This LOGO program draws a simple square with sides of 100 units long: FD is short for Forward and LT stands for Left. In LOGO you basically control a “turtle” on screen leaving a trail when moving.

LOGO is a great introduction to programming because it gently introduces basic programming concepts like procedures and recursion. It’s very easy and a lot of fun to create interesting patterns such as all kinds of spirolaterals and fractals. With JavaLogo you can write web-enabled programs in a similar way in Java. I’ve been playing around with it and created this applet in a few lines of code that shows the Sierpinski triangle.