Much to do and KSudoku again...

There is not much time to work on KSudoku recently. But I think I found the reason why generating some puzzles takes forever. And maybe it will benefit from an idea that might also improve difficulty of the puzzles.

At the moment I'm relocating. I'm moving to my first own apartment together with my girlfriend. Until now I stayed with friends or lived in dorms. So I'm looking forward to how it will be. At the same time there is much work to do at my job as we are approaching the release of our project. And the begin of writing my bachelor thesis is approaching. So not much time left for developing on KDE.

KSudoku is currently hardly of any use. Games are much to easy to solve and some games couldn't be even generated. The reason for freezing during generation of Jigsaw-puzzles is a rather simple one. And very hard to solve at the same time.

KSudoku generates puzzles by solving an empty one. As long as it can't solve with logic it tries to insert values at random positions. If it detects that one such value makes the puzzle unsolvable it tries some other value. In case of Jigsaw puzzles entering two values can make them unsolvable.

This game has no solution. Without knowledge of Jigsaws special rules it is difficult to tell that. Once you know the rule this particular problem has an easy solution. I leave it to you to find out which one. But this solution would not apply to other similar problems.

A better way would be to not try all possibilities when testing a branch but going back to earlier values when the errors are rather similar. Another improvement would be to reduce the cost of branching. As branching is a costly operation and there is much room for improvement this would make testing more branches in the same time possible. Lookahead branching would be another improvement that would also increase difficulty of generated games. Instead of testing a complete random branch the solver would first analyze the changed introduced with a branch and select the most promising branch to test it.

And last but not least is there the possibility to improve the logical part of solving. Combining some constraints would make it possible to generate new constraints. This constraints would eliminate many of the branches so that the basis for the exponential trial-and-error-solving would shrink.

New power for KSudoku

Francesco did a great work when he designed KSudoku. It won the second place in a contest of Linux Format and had support for different variants of sudoku-like games from the beginning on. Even 3D puzzles are possible. It was the generic graph coloring solver which made this success possible.

Unfortunately this solver is limited to graph coloring and not very easy to maintain. This is the reason why I'm writing a new generic engine for logic problems codenamed Logine. In theory it is able to solve any logical problem that results in one (or more) static solution(s). This flexibility is reached by an extensible high performance C++ core and QtScript-based descriptions of the rules.

/* Small script demonstrating how to setup rules */

// Create a board
var board = new logine.Board(9, 9);
ruleset.addItem(board);

// Make this board accessible for the application.
ruleset.content.board = board;

// Add cells to board
for(var x = 0; x < 9; ++x) {
 for(var y = 0; y < 6; ++y) {
  var item = new logine.Choice(item, 9);
  board.setItem(item, x, y);
 }
}

// Add containers for rows, columns and blocks
ruleset.content.rows = new Array();
ruleset.content.columns = new Array();
ruleset.content.blocks = new Array();

// Add all rows and columns
for(var i = 0; i < 9; ++i) {
 var row = new logine.Sudoku(board.itemsAt(-1, i));
 ruleset.content.rows.push(row);
 ruleset.addItem(row);

 var column = logine.Sudoku(board.itemsAt(i, -1)
 ruleset.content.columns.push(column);
 ruleset.addItem(column);
}

// Add all blocks
var blocks = board.split(3, 3);
for(var i = 0; i < blocks.size(); ++i) {
 var block = new logine.Sudoku(blocks[i]);
 ruleset.content.blocks.push(block);
 ruleset.addItem(block);
}

This script will setup the rules for a standard 9x9 sudoku. This is enough for playing and solving it. Further code is required for generating games and for interactive help. Yes you read right! Interactive help! The new core is able to provide interactive help for all games generated by the computer or even entered by the user.

Not everything is completely done but I'm alomst there. So you can look forward to a great KSudoku in 4.3.

cout << "Hello Planet!" << endl;

Let me introduce myself. I'm the current maintainer of KSudoku. While I was not very active in KDE for almost a year there are great times approaching. So I want to share this with you.

What is this blog about?

• KSudoku: This is where I'm spending most of my time now. I'm doing a complete rewrite of its core with many new features.
• Other parts of KDE if I find the time.
• Orchid: Currently paused Orchid is my effort to revolutionize the web. It is very modular and may be even of benefit for projects that have nothing to do with the web.
• Other small projects.
• Art
• And last but not least a little bit of my personal life

I hope you enjoy reading what I have to say.

Getting back to work

After some time with no motivation to be productive I got back to coding lately. First things to do are some urgent fixes for KSudoku as KDE 4.1 is nearing the release. I have waited far to long with this. So getting back to my pet-project Orchid will have to wait. But in the meantime let me introduce Orchid. I hear again and again, how complicated it is to get into web development and I share this opinion. I think the main reason is, that with most technologies someone needs to have a broad set of skills and knowledge. For example to build a simple website with descent features in PHP someone needs to know (X)HTML, PHP itself, Javascript, CSS, SQL and how configure the servers. Mistakes may make the whole system vulnerable to attacks. This is acceptable for someone who wants to get into web-design, but for a developer who just wants to create a simple website this is to way to much. Ok, there are frameworks out there which hide the implementation details for some parts but they are not for free anyway. First you need to know about them, requiring much time of research. Then even while they take work from you, they often add further complexity like an OO-layer over Javascript. After some discussion about web-design in the #kdegames-channel i decided to create a Qt-based framework in C++. I will write more about this Orchid-project in my next post.

Hello World!

Hello World!