I’m playing with some new algos these days: State Patterns and Spin Glasses.
The state pattern is an object oriented class structure that allow you to create very complex state machines (as complex as you want) without having to maintain a huge interstate matrix and have 110% of chance to break the code later. Check the example at my State Pattern small page.
Using this approach I could drastically reduce the complexity of an error log parser and also it’s 10 times faster to run and compile!
The other algo is called spin glass and it’s about dynamic problems, most of the time insoluble by any direct means, and some times insoluble by any means. The problem I’m trying to solve is far too simple and exact: a sudoku.
I though about using spin glasses because for every insertion, it removes lots of possibilities and reduce drastically the number of options. Also, because it keeps a global value, the sum of each row, column and block, it’s straightforward to check when a value was found. Check my little page about sudoku solver.
Using this approach I could solve 10.000 sudoku puzzles in less than one second on a mere pentium 4 machine.
The idea behind State Pattern is to create a generic state (the interface) that is attached to the State Controller. There is no state change list and no switch/case statement on this pattern, only states.
The state knows two things: what to do now and when to change to the next state(s). So, the interface have two important methods: run, that do whatever is needed and newState that returns the new state or itself, in case of no change.
As simple as that, it’s very powerful and extremely fast!
Sudoku glasses is also very simple: It’s a grid or 9x9x9 which’s a cube of spins (0, -1 or a positive number bigger than 8, say 9). It can be seen as a set of 9 sudoku boards, one for each value (1-9). Every time you ‘set’ a value you put the big integer on it and -1 on all cells it blocks (ie. it’s row, col and block).
It’s simple to see that if the sum of all members of the row/col/block is between 0 and -8 it’s not complete yet (ie. some zeros still there). If the sum is -8 means that there’s 8 times -1 and one zero, which means that cell is defined. When you put 9 on it the sum goes bigger than zero, which means it’s solved and marked.