Technological Thoughts by Jerome Kehrli

Entries tagged [algorithms]

Snake ! Reloaded ...

by Jerome Kehrli

Posted on Saturday Oct 22, 2016 at 02:06PM in OpenGL

I needed to have a little fun recently when slacking on my computer at night so, as is often the case in such situation, I spent some time on my snake project again.
I implemented a few evolutions as explained below and am now working on making the auto-pilot algorithm a little better.
It's funny how this snake application is something on which I get over and over again years after years, trying to make it better, reworking it, etc.

The first post on this blog about this app was there :
Yeah, well, that doesn't make me younger, does it ?

The snake project

Snake is a little C++ / OpenGL / Real-Time project which shows a snake eating apples on a two dimensional board. It really is very much like the famous Nokia phone game except the snake finds its way on its own.

No nice textures, no sweet drawings yet, the world elements are mostly simple spheres. Trivial OpenGL features such as fog, lightning and shadows are implemented though.

The auto-pilot is still pretty stupid at the moment and the snake ends up eating itself quite fast.
This is the thing on which I am working now.

Snake Application Screenshot

It still is a game as the "user" can at any moment deactivate the auto-pilot and take the control of the snake himself. At any moment, the auto-pilot can be re-engaged again or deactivated.

The project is open-source'd under GNU LGPL license and if you're interested in OpenGL, Vector Geometry, Real-time C++ Programming, or simply Algorithms you might very well enjoy having a look at the source code provided here.

Read More

Sudoku Laboratoy

by Jerome Kehrli

Posted on Tuesday Aug 30, 2016 at 09:02AM in Computer Science

I have written a little Sudoku program for which I provide here the source code and Windows pre-built executables. Current version is Sudoku 0.2-beta.

It supports the following features:

  • A GUI to display and manipulate a Sudoku board
  • A Sudoku generator
  • A Sudoku solver
  • A Sudoku solving tutorial (quite limited at the moment)

Sudoku Laboratory - Screenshot 1 Sudoku Laboratory - Screenshot 2
At the moment there are two resolution methods supported, one using human-like resolution techniques and a second using backtracking. The resolution of a solvable Sudoku board takes a few milliseconds only.
A solvable Sudoku board is a Sudoku board than has one and only one solution.

The Sudoku board generator generates solvable Sudoku boards. It usually generates boards between 18 and 22 pre-filled cells. (which is quite better than most generators I could find online).
Currently it generates the best (i.e. most difficult) board it possibly can provided the random initial situation (with all cells filled) of the board.
The problem I'm facing in this current version is that it can take from a few seconds only up to several minutes to generate the board (this is discussed in the algorithms section below).
In addition, the difficulty of the resulting board is not tweakable at the moment. In some cases it generates an extremely difficult board (only solvable with nishio) in a few seconds while some other times it needs two minutes to generate an easy board.

The software is written in C++ on Linux with the help of the wxWidgets GUI library.
It is cross-platform to the extent of the wxWidgets library, i.e. it can be compiled on Windows, OS X, BSD, etc.

A makefile is provided to build it, no configure scripts, i.e. you need to adapt the makefile to your own Linux distribution (or on Windows Mingw, TDM, etc.).
Happily only few adaptations should be required.

Read More