Monday, March 9, 2009

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.

8 comments:

Giuliano Vilela said...

Really nice job! The way you abstracted the rules of these kind of games from the logic-solving engine itself is really elegant. There sure must be a lot of possibilities for other games on top of this.

On another note, I myself am still an outsider in the world of KDE development, but am currently considering applying for a Google SOC position here, maybe on KDE-Games. Are you considering being a mentor this year?

Anonymous said...

Did you see this article? Seems very relevant.

http://www.physorg.com/news153588084.html

"(PhysOrg.com) -- How many different sudokus are there? How many different ways are there to color in the countries on a map? And how do atoms behave in a solid? Researchers at the Max Planck Institute for Dynamics and Self-Organization in Göttingen and at Cornell University (Ithaca, USA) have now developed a new method that quickly provides an answer to these questions."

Ian Monroe said...

A great use of QtScript. :)

scroogie said...

So I guess this is an Engine to solve Constraint Satisfaction Problems? What are you using? Backtracking or heuristics?

maninalift said...

Just another fellow interested in the algorithmic complexity issue.

Do you use generic a generic constraint-satisfaction algorithm for all problems? Even human-solvable problems of this sort can be prohibitively costly to solve in a generic way. This is not far from my area of work so I'd love to have a look. Is the code public ATM, I didn't find it in playground/games.

You know there is a whole set of other interesting games that could be opened up if you also included support for partially-solvable problems. i.e. each rule has a weighting, what is the best score (sum of weightings for satisfied rules) you can achieve.

JoselB said...

@GiulianoXT Yes, there are many other games I thought about. And that was the reason I'm doing it this way.
I considered applying for a GSOC project as a student myself. However I think mentoring a project might be of greater use. I'm going to dicuss this with the other KDEGames developers.

@Anonymous I know this article. In fact I thought about how this can be applied to my engine. It is perfectly doable but it wouldn't bring much advantage for the games I was thinking about and would make the core even more complex. In fact it might even perform worse in this case.

@Andre You're right. It is a Engine to solve Constraint Satisfaction Problems. It uses backtracking with an elimination of obviously invalid solutions in each step.

@maninalift The code lives currently in a local git repository. But I want to upload it to KDE/Playground in the near future. Regarding partially-solvable problems I currently have no idea what they are. :)

I think I write another article about the way the solver currently works.

maninalift said...

Partially solvable problems:

At the moment a problem is defined by a set of constraints which must be solved.

What I mean by a partially solvable problem is that it might not be possible to solve all of the constraints. Instead each constraint has an associated value (call it a "score") and the aim is to maximise the total score (ie see how many of the constraints you can satisfy at once).

JoselB said...

@maninalift: yes it would be possible to create such games, but for the moment i will concentrate on solvable games as the design is already finished and almost implemented and i want to have it in 4.3