Posts

Showing posts from June, 2007

Databases and objects

I have long been a fan of Fabian Pascal's database ramblings (not his political and economical ones, the man has absolutely no clue on those). Yes, the relational theory is actually set algebra, and therefore a relational database is the most complete and powerful type of database, bar none. Object databases, hierarchical databases (registry), network databases (objects) - they all have problems which simply do not exist in an RDB. However, I was re-reading an article about the object / relational mismatch problem - Interoperability happens and I got to this part: Developers simply give up on relational storage entirely, and use a storage model that fits the way their languages of choice look at the world. Object-storage systems, such as the db4o project, solve the problem neatly by storing objects directly to disk, eliminating many (but not all) of the aforementioned issues; there is no "second schema", for example, because the only schema used is that of the object d...

Sudoku and TDD

For the last few months, I've been trying on and off to write a program to solve a Sudoku game. The "easy" ones are easy, you just use a rudimentary algorithm: each cell has a list of possible values associated with it start by associating all values 1-9 to each cell repeat until solved: for each cell, remove any values already present in the same line, column, or box By this process of repeated elimination you can solve a lot of the "easy" tables. However, this algorithm is too limited and it will go into an infinite loop if you have a situation where, for example, two cells in the same row can accept values 1 and 5, but at this point you have no way of knowing which is which. Now, of course the solution to that problem is simply a recursive backtracking algorithm: save the current state pick one value and try to solve the rest of the table; if it worked, all is good; if not, go back to the saved state and try the next value The devil, however, is in the deta...