Solving A Tetris Cube, Recursive Backtracking, Algorithm X, Oh My!

A few days ago I got my hands on one of these:

A Tetris Cube. Twelve pieces, and a box of 4 by 4 by 4. Your task: to put the pieces neatly in the box again. The box said there are more than 9000 solutions, but I knew nonetheless this wasn't going to be an easy task. I was going to solve it, "Without cheating!", I proclaimed proudly.

An hour or so later these little blocks were completely driving me crazy. Usually I'm not that bad with these kinds of puzzles, but this thing certainly proved to be very difficult. I decided to call it a day and would try again later.

The next day I tried again, I was making a little progress, but every time I came close a little piece stuck out just a tiny little bit! This was going nowhere. If I were to beat this devil's contraption, I would need to resort to other means.

"I'll just throw together a recursive function real quick, that should be easy enough, right? (And no, that is not cheating...)" How I came to regret those words. In my experience, this:

I'll just quickly find a solution with recursive backtracking.

Almost always turns into this:

Damn, damn, damn! Why is it so slow? How can I speed this thing up?

But first things first. There are a few ways you could solve this, but first, let's take a slight detour to explain backtracking (you may skip this if you already know all this, but if you do know all this, then you probably know the solution to the puzzle as well, or would handle things better than I did):

Detour: Recursive backtracking in general


Let's see what a recursive backtracking function generally looks like:

recursive_funtion(level) {
for all possible ways for something {
try it
if solution valid {
if solution complete {
done, show solution
}else{
recursive_function(next_level)
}
}
(revert this try)
}
}

As you can see, this method consists of a level, which we traverse in each recursive call, and a set of local decisions we make at each level. Take a magic square, for example (image from the Wikipedia page):

With the above method, we would define our level as the position in the grid (ranging from 1 to 9, as there are 9 spaces to fill with a number), the decisions at each level would be a number ranging from 1 to 9, our function would be:

recursive_funtion(position) {
for number from 1 to 9, not used elsewhere already {
put this number on this position, make it unavailable
if solution valid {
if solution complete {
done, show solution
}else{
recursive_function(next_position)
}
}
(make this space blank again, and the number available)
}
}

A few remarks:
(1) As each number can only be used once in the whole square, we must keep an array or set somewhere to keep track of the numbers used, which can be easily done in each programming language.
(2) Note that we can check mid-solution, we must not wait until we are at position 9 (the last position) to check if the solution is valid. In fact, we can speed things up a bit by implementing a few optimalizations. For example: after each row is done (at positions 3, 6 and 9), check if this row sums to 15, if it does not, there is no sense continuing towards deeper levels in our tree.

Speaking of trees, I hope you see how the combination of levels and decisions correspond to a tree. If you do not: here is a picture:

(Not all levels, lines and branches are shown, but it should give you a pretty clear idea.) Note that, if we picked e.g. the number 2 for position (level) 1, we cannot use it in the following levels, as shown in the tree.

Now let's see how the function will work, we start at the first level, with the first number:

This is a valid choice, so we can step down to the next level. In level 2, our first number we can pick is 2:

This is a valid choice, so we can step down to the next level. In level 3, we can pick 3, let's see what happens:

Since we now have a complete row, we can check if the sum 1+2+3=15. Is isn't, so it makes no sense to continue at this point. Look at the huge part of the tree we can "cut off", as shown by the red curved line.

We're still in level 3, we try the following number: 4. 1+2+4=7, which isn't 15. We can cut away this part as well. Number 5 gives 8, 6 gives 9, and so on until number 9 gives 1+2+9=12, all the branches have been cut. Note that we can make an important observation here: your optimizations should try to cut away from the tree as early as possible, that way, the solution space in which we have to search can be decreased dramatically. (This is also the reason why the hardest choices or levels are often put first in these trees.)

Now the algorithm "backtracks" back to level 2, and tries the following number there: 2:

And so on (the yellow numbers are the ones we've "done", or excluded in our optimization). This continues until we find a solution, e.g.:
Level 1: 2, level 2: 7 and level 3: 6 gives 15;
level 4: 9, level 5: 5 and level 6: 1 gives 15;
level 7: 4, level 8: 3 and level 9: 8 gives 15.

Back on track (no pun intended): recursive backtracking in this case


For the Tetris Cube, we have tree decision variables:
(1) the block used (there were 12 different blocks);
(2) the position were we put the block;
(3) the rotation of the block.

If we'd used position as the level, we have 64 different levels (4x4x4). If we were able to place any remaining block at this position, we could immediately use the next unoccupied space as the position in the next recursive call (since it makes no sense trying all the occupied positions first, since they won't validate anyway).

If we'd used block as the level, we have 12 different levels. If we are able to place this block at any available position in a specific rotation, we can move on the the next block. It seems a bit more sensible to use this method. This way, our tree will be smaller (less tall), and the decisions inside the function purely concern position and orientation in 3d-space. Our function now looks like:

recursive_funtion(block) {
for all positions 1 to 64 {
for all orientations 1 to 24 {
put our block at this position in this orientation
if solution valid {
if solution complete {
done, show solution
}else{
recursive_function(next_block)
}
}
(remove this block)
}
}
}

There are still a few questions left we have to answer, mainly: the different rotations, and how we can validate a partial solution. But first: let's take a look at the different blocks and how we can encode them.

The different blocks


There are 12 blocks, colored in either red, blue or yellow (but the colors themselves mean nothing, they just add decoration). Since the 3d-modelling program Blender runs too slow on my laptop (Compositing enabled and such) I quickly whipped out a few lines of Povray code.

Did you know I can do animations too?

Now how do we encode them? Each block can be described by a set of tiny 1x1x1 sub-blocks placed along the x, y and z axes. I call the tiny block placed at (0,0,0) the pivot. Take the red L for example, this block can be described as a combination of five little blocks:
{(0,0,0); (1,0,0); (2,0,0); (0,1,0); (0,2,0)}
(0,0,0) is the corner-block and our pivot.

Another way of describing this block with another pivot point:
{(0,0,0); (1,0,0); (2,0,0); (2,1,0); (2,1,0)}

As you can see, it doesn't matter which sub-block we use as our pivot block or how we places our x,y and z axes. Since our function will try every position and every possible rotation, we try every combination anyway.

Now why are there 24 rotations? Every block can be placed facing the direction along: x positive, x negative, y positive, y negative, z positive and z negative, which gives 6 possible directions.
For every direction, we can rotate the block in 4 different ways (0°, 90°, 180° and 270°). 4x6=24. Easy.

Taking the description {(0,0,0); (1,0,0); (2,0,0); (0,1,0); (0,2,0)} and saying: put this block in position 34 facing y negative and rotated 90° now just becomes a matter of transforming and rotating objects in 3d. I won't describe the details here, it involves some matrix manipulations and such, but are really simple when rotating in the four degrees mentioned above. If you want to know more, take a look here or Google it.

In PHP, the language I was using (I know, I know - remember, I thought this would be a quick and easy job), a block description looks like:

// 1 1 1
// 1
// (1)
$blocks[] = array(array(0,0,0)
,array(0,1,0)
,array(0,2,0)
,array(1,2,0)
,array(2,2,0) );

Verifying partial solutions


Just as with our magic square, we can do a few checks after placing a few blocks, a few of them are necessary:
(1) a block may not overlap another block;
(2) a block may not go outside the bounds of the 4x4x4 block.

You could also get creative:
(3) a block may not be placed in such a way that we have an isolated empty space. This is, a space surrounded by occupied spaces (or by the bounds of our 4x4x4 cube).

Trying the program


We're done, I was exited, I would beat this thing!

The program now looked like this (you can't read the code - believe me, it's a good thing):

The program was running dog slow. It was doing lots of block-position-rotation combinations very fast, but it was still too slow. I thought I had made an error, and changed some parameters. I used a 2x2x2 bounding box with only three little pieces to fill it with. The program immediately displayed all the solutions (not that many of course). It was working fine, but couldn't handle the large solution space of a 4x4x4 box. That's the problem with recursive backtracking, a "magic square" (see above), with 9 spaces is easy enough, but one with 10 spaces is a lot harder, and one with 11 spaces is even harder then the previous increment (non-linear). It was back to the drawing board again.

The following day...


The next day I decided to Google around a bit. It turns out that someone else has already solved this puzzle and posted his method online here. The author seems to like solving all these puzzles. Most of his findings and description is exactly the same as what I found, so why did his method work. You can download his program (http://scottkurowski.com/tetriscube/TetrisCubeSolved.zip) and take a look at the source code yourself.

So why was his program working?
(1) C! It's a pity, but C is much, much faster than PHP, a factor we can't omit here.
(2) He doesn't use a backtracking recursive function, but the general method is the same (a bunch of goto's and iterating over all the possible permutations the place the blocks one by one). It does backtrack however.

It's a pretty and well-written program. I felt defeated. Both by the puzzle and by an other programmer. Since I didn't want to rewrite everything in C to see if a recursive method would prove successful there (I don't like C), I wanted to see if I could solve it using a "slow" language anyway: less brute-forcing, more being smart.

Searching for a better method


I recalled reading something about Dancing Links and how someone solved a Sudoku puzzle with them. "Sudoku and Tetris Cubes look alike", I thought. So I continued researching this.

First of all, we have "Algorithm X", an algorithm found by Donald Knuth for solving exact cover problems. Exact cover problems are problems in which every constraint is an "exactly one"-constraint. Knuth uses the Pentomino puzzle as an example (every piece should be used exactly once and every space must be overlapped by a piece exactly once).

Also - more good news - Algorithm X is recursive and backtracking, it basically optimizes the way the recursion is done (see the linked Wikipedia page above to see how the algorithm works, make sure you understand it before continuing, it's quite easy and Wikipedia does a really good job at explaining it.)

Dancing Links is a method to implement Algorithm X based on the fact that it is very easy to remove and re-add elements in a double linked list. Instead of using this, I first decided to try a simple Algorithm X implementation.

Basically, Algorithm X performs a few operations on a matrix in which each element is either zero (0) or one (1). A solution is then a set of rows so that in each column there is only one one (1).

Take the Pentomino puzzle for example (if you aren't familiar with the puzzle, take a look here). It is basically the same problem as our Tetris cube, except for the fact that it is in 2d instead of 3d. We construct a matrix as such (from Wikipedia):


There are two constraints:
(1) for each of the 12 pieces, there is the constraint that it must be placed exactly once. Name these constraints after the corresponding pentominoes: F I L P N T U V W X Y Z.
(2) for each of the 60 spaces, there is the constraint that it must be covered by a pentomino exactly once.

Thus there are 12+60=72 constraints in total.

The problem involves many choices, one for each way to place a pentomino on the board. It is convenient to consider each choice as a sets of 6 constraints: 1 constraint for the pentomino being placed and 5 constraints for the five squares where it is placed. For example:

{F, 12, 13, 21, 22, 32}
{F, 13, 14, 22, 23, 33}
{I, 11, 12, 13, 14, 15}
{L, 12, 22, 32, 42, 43}
…

One of many solutions of this exact cover problem is the following set of 12 choices:

{I, 11, 12, 13, 14, 15}
{N, 16, 26, 27, 37, 47}
{L, 17, 18, 28, 38, 48}
{U, 21, 22, 31, 41, 42}
{X, 23, 32, 33, 34, 43}
{W, 24, 25, 35, 36, 46}
{P, 51, 52, 53, 62, 63}
{F, 56, 64, 65, 66, 75}
{Z, 57, 58, 67, 76, 77}
{T, 61, 71, 72, 73, 81}
{V, 68, 78, 86, 87, 88}
{Y, 74, 82, 83, 84, 85}

So, in our case, we need a row for every choice we can make, that is: all the combinations of every piece and every possible way of placing it. Our finds every valid possible combination for every block and constructs rows in the matrix:

for every block {
for every position {
for every rotation {
try this, if this placement is possible (thus if it does not exceed the boundaries of the 4x4x4 box, add it as a row: {BLOCK; pos1, pos2, pos3,...}
}
}
}

Now our columns: we have 12 blocks, and 64 positions these blocks can occupy. 12+64=76. For every row, we:
(1) set a one (1) in one of the first twelve columns according to the block this row uses;
(2) set a one (1) in every "position" this row occupies.

After quickly throwing some ugly code together, I ran the program. First, it constructs the choices and the matrix:

Constructing choices:
0: ................................................................
1: ................................................................
2: ................................................................
3: ................................................................
4: ................................................................
5: ................................................................
6: ................................................................
7: ................................................................
8: ................................................................
9: ................................................................
10: ................................................................
11: ................................................................
Number of choices/rows: 4488 out of 18432 theoretical possibles choices
Constructing matrix: .................................................................................................................................................................................................................................................................................................................................................................................................................................................................
Done, number of rows: 4488 and cols: 76

The matrix itself is a bit large to display here. But here are the first few rows:

OUTPUTTING MATRIX:
0 {0; 0; 1; 2; 6; 7; }: 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 {0; 0; 1; 2; 18; 19; }: 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 {0; 0; 4; 8; 9; 13; }: 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 {0; 0; 16; 32; 33; 49; }: 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 {0; 0; 4; 8; 24; 28; }: 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 {0; 0; 16; 32; 36; 52; }: 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
6 {0; 1; 5; 9; 10; 14; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 {0; 1; 17; 33; 34; 50; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
8 {0; 1; 5; 9; 8; 12; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 {0; 1; 17; 33; 32; 48; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 {0; 1; 5; 9; 25; 29; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 {0; 1; 17; 33; 37; 53; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
12 {0; 2; 6; 10; 11; 15; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 {0; 2; 18; 34; 35; 51; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
14 {0; 2; 6; 10; 9; 13; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15 {0; 2; 18; 34; 33; 49; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16 {0; 2; 6; 10; 26; 30; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
17 {0; 2; 18; 34; 38; 54; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
18 {0; 3; 2; 1; 5; 4; }: 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
...

As you can see, in these rows, the first block (number zero) is used, so the first column is one (1), the next eleven columns are zero (0). The next 64 columns are one if the row uses that position.

The program then gives some verbose information:

==> (0) Number of rows: 4488 and cols: 76
Picking 12, has 117
117 rows to do for column
==> (1) Number of rows: 3414 and cols: 70
Picking 15, has 22
22 rows to do for column
==> (2) Number of rows: 2025 and cols: 64
Picking 17, has 45
45 rows to do for column
==> (3) Number of rows: 1156 and cols: 57
Picking 26, has 10
10 rows to do for column
...
==> (10) Number of rows: 9 and cols: 12
Picking 4, has 3
3 rows to do for column
==> (11) Number of rows: 0 and cols: 0
<== Column has zero ones. ==> (11) Number of rows: 0 and cols: 0
<== Column has zero ones. ==> (11) Number of rows: 0 and cols: 0
<== Column has zero ones. ==> (10) Number of rows: 10 and cols: 12
Picking 4, has 2
2 rows to do for column
==> (11) Number of rows: 0 and cols: 0
<== Column has zero ones. ==> (11) Number of rows: 2 and cols: 6
Picking 10, has 2
2 rows to do for column
==> (12) Number of rows: 0 and cols: 0


And finally, a first solution is found, alongside a simple presentation to try it on the cube:

All done, here is a list of choices:
CHOICE NR 0: 0 0 1 2 6 7
CHOICE NR 393: 1 19 3 23 22 21
CHOICE NR 741: 2 5 9 13 29 30 45
CHOICE NR 1113: 3 15 31 14 11 10
CHOICE NR 2693: 7 4 8 12 28 44
CHOICE NR 2371: 5 63 62 46 61 60
CHOICE NR 3328: 8 58 47 42 43 39 27
CHOICE NR 3621: 9 38 51 54 55 59
CHOICE NR 4427: 11 49 53 50 34 35 18
CHOICE NR 2635: 6 56 57 40 24 20 16
CHOICE NR 2004: 4 48 52 32 33 17
CHOICE NR 3938: 10 26 25 41 37 36

Solution found:
Plane 0:
3 3 2 7
3 3 2 7
0 0 2 7
1 0 0 0
Plane 1:
3 2 2 7
8 10 10 6
1 1 1 6
1 11 4 6
Plane 2:
8 5 2 7
8 8 10 6
8 9 10 10
11 11 4 4
Plane 3:
5 5 5 5
9 8 6 6
9 9 11 4
9 11 11 4

Which looks like this:

Ha, gotcha! If we would use Dancing Links as well, and a faster/better suited language, this would go even faster.

Ubuntu Jauntu: Skype Worked Before, Now: "Problem with audio capture"

There are two things I currently not like about Ubuntu or Linux in general: the whole sound mess, and the whole graphics mess (but both are getting better). This problem is about the first mess.

Skype was working perfectly in Interprid, now in Jaunty it was telling me that there was a "Problem with audio capture". I tested Ubuntu's sound-recorder as well, which was not working either.

I'm using the default, normal Skype from the Medibuntu repo's!

Let's take a look at all the different factors here. First of all, open System → Preferences → Sound. Mine looks like this:

• Sound Events - Sound playback: Autodetect
• Music and Movies - Sound playback: Autodetect
• Audio Conferencing
• Sound playback: Autodetect
• Sound capture: ALSA - Advanced Linux Sound Architecture, in your case, this may say PulseAudio Sound Server here. However, I have noticed that ALSA seems to record better sound (less garbled, especially with slower computers). Since we're not doing anything unusual with recorded sound (client-server, multiple inputs), I suggest you also pick ALSA here.

Now right click the sound icon in the panel and pick "Open Volume Control". My device says "HDA Intel (Alsa mixer)". You'll probably need the Alsa mixer as well. I have a few sliders I have to play with:

• In the Playback-tab (yes, here!): Mic Boost
• In the Recording-tab: Capture
• In the Switches-tab: make sure Microphone Capture is enabled! This was disabled after my Jaunty upgrade. If you're not seeing any relevant sliders or checkboxes, click the Preferences-button and enable all relevant sliders/switches.

Now open sound-recorder. You should be able to record sound now. Also, start pavucontrol, and click the Input Devices-tab, the level meter should respond to you clapping your hands for example.

Hear yourself? No, then try fiddling again with the settings in the previously opened windows before you continue!

Yes, good, onwards to Skype. Try making a test call. In my case, Skype was still complaining about the audio capture. Let's open Skype's options → Sound Devices.

In my case, the options were:

• Sound In: HDA Intel (hw:Intel,0)
• Sound Out: pulse
• Ringing: pulse

Which was working in Intrepid. If you suffer the same problem, read on...

A sidenote, your Sound In device might be either pulse or default as well. There are a few cases when you should use these:

• default: if you've succesfully changed configuration files to make the correct devices the default ones. This will almost never be the case.
• pulse: if you're using PulseAudio server for the Sound Capture. But even then, I don't recommend it. Using pulse for Sound In often crashes Skype on my machine...

Again, provided when you use a normal Skype (non static, non OSS).

Your Sound Out/Ringing devices are already correct, they need to be pulse. Sound In will be set to an hw-device.

Before reading further, try making a test call with every listed hw-device (I had four, you can have more or less).

If none of them are working or if you're sure which hw-device you need (and it isn't working), try this: edit /etc/pulse/daemon.conf (don't forget to sudo) and make sure the following lines are present and uncommented, with the following values:

default-fragments = 8
default-fragment-size-msec = 5

This is an optional step however, but it seems to help with the Skype sound quality (an other option is setting default-fragment-size-msec to 10).

(!) Now,  edit ~/.asoundrc (no need to be root here, it's a file in your home directory). And make sure the following lines are there:

pcm.pulse { type pulse }
ctl.pulse { type pulse }

Which I totally did in Hardy as well! The update must've deleted them. This simple file seemed to do the trick!

Then, just to be sure, I reinstalled  the libasound2-plugins package.

Reboot, or restart pulseaudio (kill it, then start it in i.e. a Terminal window). Restart Skype. Skype was working fine now. If it is not, make sure you try every plughw-device.



Still not working, no matter how much you try? You're out of luck. If sound-recorder and sound playback is working, you can try an emergency solution. Install the static, OSS version of Skype (you can find it with Medibuntu or floating around in a tarball somewhere). and start it with:

padsp skype

To route the sounds through the PulseAudio sink. Sound devices in this Skype should all be set to default (or OSS). Calls should work now. Be warned though: always try this as a last resort, routing OSS sound through PulseAudio is slow and bloated, ugly and old. Your record voice will sound like... well, crap.

Vice City (And Perhaps Other Games) In Wine - CD Error With ISO

So, you've just gotten yourself two .iso's for Grand Theft Auto: Vice City (your backups, of course), which you want to play in Wine. What do you do?

That's easy, you say:

sudo mkdir /media/isoimage
sudo mount -o loop ./cd1.iso /media/isoimage

And start the setup with Wine.

Now the installer asks for the second CD, what do you do? Here we have to "eject" our "cd" first...

wine eject
sudo umount /media/isoimage
sudo mount -o loop ./cd2.iso /media/isoimage

And we're done. You want to start the game, but it requires the play disk, even although you're sure you've mounted it. Thing is, Vice City isn't looking at your /media/isoimage mount point, but it's looking at your drive letters... where could the cd be?

Take a look in ~/.wine/dosdevices (it's a hidden directory in your home folder). We're going to create two symbolic links there (in my case, there were a lot of symbolic, broken links already there, I deleted every one of them except c: and z:). One for the mount point, and one for the actual device (or in our case: the image).

ln -sf /media/isoimage ~/.wine/dosdevices/e:
ln -sf ~/cd2.iso ~/.wine/dosdevices/e::

Note the double colons (e::) in the second line. That's it, the game should start fine now.

Be sure to replace /media/isoimage, e:, e::, ~/cd1.iso, ~/cd2.iso and other displayed paths/locations with the ones relevant for you.

Modern Genetic (And Other) Algorithms Explained: Part 7 - Conclusion

(This is the final part in the Modern Genetic Algorithms Explained series, click here to go to the first post, or browse through all the parts with the Table Of Contents at the end of this post.)

In the past series, we have looked at genetic algorithms, simulated annealing, ant colony simulation and tabu search. Each method had its pro's and cons, and there certainly is room for exploration left.

I hope you've enjoyed this series, or that it has at least sparked your interest in the topic.

Here are a few more (general resources), if you want to know more:

Other related techniques:

• Evolutionary programming
• Genetic programming
• Harmony search - this is interesting: it's based on how musicians compose music, also see this website
• Memetic algorithms - a very new and interesting area in evolutionary optimization. It combines a genetic algorithm to the ability of learning (hence the name: "memes")
• And many more...

Books:

• Introduction to Evolutionary Computing
• Evolutionary Computation
• How to Solve It: Modern Heuristics
• A Field Guide to Genetic Programming (the PDF is free!)
• Genetic Programming: On the Programming of Computers by Means of Natural Selection
  

A specialized event was held in the USA: Foundations Of Genetic Algorithms. You can find a lot of interesting information on their website.

Finally, I want to mention a software project which looks promising: Paradiseo:

A white-box object-oriented framework, portable (Windows, Unix and MacOS), dedicated to the flexible design of metaheuristics: solution-based metaheuristics (Local search, Simulated annealing, Iterated local search, Tabu search, ...) and population-based metaheuristics (Genetic algorithm, Particle swarm optimization, Evolution strategy, Differential evolution algorithms, ...).

-----

Table Of Contents (click a link to jump to that post)

1. Introduction

2. Genetic Algorithms

3. CHC Eshelman

4. Simulated Annealing

5. Ant Colony Optimization 

6. Tabu Search

7. Conclusion 

Modern Genetic (And Other) Algorithms Explained: Part 6 - Tabu Search

(This is part 6 in the Modern Genetic Algorithms Explained series, click here to go to the first post, or browse through all the parts with the Table Of Contents at the end of this post.)

Tabu search is not really "modern" anymore, but still widely used nonetheless.

The pseudocode looks like this:

Construct an initial solution
Until timelimit hit or satisfiable solution found do:
    Find all neighbours which are not in the tabu list, and calculate their score
    Pick the best neighbour, add the previous solution to the tabu list

Notice that the "best neighbour" must not be better than the current solution, or than the ever best found solution.

Maintaining a tabu list can be time and memory consuming, alternatively we could construct a list like this: add the difference between two following solutions to the list (so that they cannot be undone), and keep it in the list for n iterations. N, or the length of the list is important: make it too long and the algorithm might get stuck, make it too short and the algorithm will tend towards local maxima.

This time, I've coded the example in PHP, I hope nobody minds:

$target = 300;

//construct an initial solution
$tabulist = array('ttl' => array(), 'change' => array());
$solution = array();
$min = 0;
$max = 100;
for ($i=0;$i<6;$i++)
    $solution[] = rand($min,$max);
  
//until solution found
while (true){
    $best_neighbour_solution = false;
    $best_neighbour_score = 1000;
    $best_neighbour_tabu = false;
    for ($position=0;$position<6;$position++){
        if (!in_array("$position+",$tabulist['change'])
                and $solution[$position] < $max){
            $temp_solution = $solution;
            $temp_solution[$position]++;
            $score = fitness($temp_solution,$target);
            if ($score < $best_neighbour_score){
                $best_neighbour_score = $score;
                $best_neighbour_solution = $temp_solution;
                //make sure this step doesn't get undone
                $best_neighbour_tabu = "$position-";
            }
        }
        if(!in_array("$position-",$tabulist['change'])
                and $solution[$position] > $min){
            $temp_solution = $solution;
            $temp_solution[$position]--;
            $score = fitness($temp_solution,$target);
            if ($score < $best_neighbour_score){
                $best_neighbour_score = $score;
                $best_neighbour_solution = $temp_solution;
                //make sure this step doesn't get undone
                $best_neighbour_tabu = "$position+";
            }
        }
    }
    //pick the best neighbour
    $solution = $best_neighbour_solution;
    $fitness = fitness($solution,$target);
    echo "Iteration $iterations: fitness = $fitness\n";
    if ($fitness == 0){
        echo "Perfect solution found:\n";
        print_r($solution);
        die;
    }
    //add change to tabu list
    $tabulist['ttl'][$iterations] = 5; //remember for 5 iteration
    $tabulist['change'][$iterations] = $best_neighbour_tabu;
    //update the tabulist
    foreach ($tabulist['ttl'] as $key => &$val){
        $val--;
        if ($val <= 0){
            unset($tabulist['ttl'][$key]);
            unset($tabulist['change'][$key]);
        }
    }
    echo "Iteration $iterations: tabulist now contains "
        .count($tabulist['ttl'])." items \n";
    $iterations++;
}


function fitness($array, $target){
    return abs(array_sum($array)-$target);
}


The neighbour calculation could be done a little better (there's a bit of ugly duplicate code), but the following output is given:

Iteration : fitness = 57
Iteration : tabulist now contains 1 items
Iteration 1: fitness = 56
Iteration 1: tabulist now contains 2 items
Iteration 2: fitness = 55
Iteration 2: tabulist now contains 3 items
Iteration 3: fitness = 54
Iteration 3: tabulist now contains 4 items
Iteration 4: fitness = 53
Iteration 4: tabulist now contains 4 items
Iteration 5: fitness = 52
Iteration 5: tabulist now contains 4 items
...
Iteration 55: tabulist now contains 4 items
Iteration 56: fitness = 1
Iteration 56: tabulist now contains 4 items
Iteration 57: fitness = 0
Perfect solution found:
Array
(
    [0] => 66
    [1] => 14
    [2] => 20
    [3] => 99
    [4] => 14
    [5] => 87
)


With this sample problem, such an output was, of course, expected. Notice that I've used the second method of keeping a tabulist.

This post concludes this series, we only have one post to go, with a general conclusion.

-----

Table Of Contents (click a link to jump to that post)

1. Introduction

2. Genetic Algorithms

3. CHC Eshelman

4. Simulated Annealing

5. Ant Colony Optimization 

6. Tabu Search

7. Conclusion 

Modern Genetic (And Other) Algorithms Explained: Part 5 - Ant Colony Optimization

(This is part 5 in the Modern Genetic Algorithms Explained series, click here to go to the first post, or browse through all the parts with the Table Of Contents at the end of this post.)

First, let's go to Wikipedia for a definition:

The ant colony optimization algorithm (ACO), is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs.

This algorithm is a member of Ant colony algorithms family, in Swarm intelligence methods, and it constitutes some metaheuristic optimizations. Initially proposed by Marco Dorigo in 1992 in his PhD thesis [1] [2] , the first algorithm was aiming to search for an optimal path in a graph; based on the behavior of ants seeking a path between their colony and a source of food. The original idea has since diversified to solve a wider class of Numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants.

"Good paths through graphs". I have not converted our sample problem from the previous posts to a graphing problem. So no Python sample this time, sorry.

You do get to see some pseudocode though:

Given a number of nodes
Given some edges between nodes (paths)
Given BT := {}, this will contain our best tour
Randomly construct a tour T
Create a number of "ants" (often equal to number of nodes)
Associate a distance, pheromone value, and delta pheromone value to every edge
Iterate until time limit hit or satisfiable solution found:
  For each ant do:
    Do until tour constructed:
    Next node is chosen depending on visibility (e.g. 1/distance) and pheromone trail
    E.g. choose next node with probability (visibility^a)*(pheromone trail^b)
    Calculate fitness of this tour
    Copy this tour to the best tour if fitness is better
    Update the pheromone trail of each edge of this ant's tour:
    E.g. delta pheromone for edge := 1/(tour cost)
  For each edge:
    Lower pheromone value by a factor
    Add delta pheromone value to pheromone value
    Set delta pheromone := 0


ACO is a very interesting method, again, we see certain aspects already used in the previous posts, like using pheromone trails to avoid local maxima. Since the algorithm is closely tied to graphs, nodes and paths, it's no wonder it's often used to find shortest paths, or to solve the travelling salesman problem.

There are some interesting links on the Wikipedia page, one of them is this application:

After a while, an ant finds a path to the food and places pheromones:

Those who are interested can read more about Swarm intelligence or Particle swarm optimization.

-----

Table Of Contents (click a link to jump to that post)

1. Introduction

2. Genetic Algorithms

3. CHC Eshelman

4. Simulated Annealing

5. Ant Colony Optimization 

6. Tabu Search

7. Conclusion 

Modern Genetic (And Other) Algorithms Explained: Part 4 - Simulated Annealing

(This is part 4 in the Modern Genetic Algorithms Explained series, click here to go to the first post, or browse through all the parts with the Table Of Contents at the end of this post.)

First of all: Simulated Annealing is not a genetic algorithm, but it is a modern optimization technique.

Wikipedia tells us the following:

Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global minimum of a given function in a large search space. It is often used when the search space is discrete (e.g., all tours that visit a given set of cities). For certain problems, simulated annealing may be more effective than exhaustive enumeration — provided that the goal is merely to find an acceptably good solution in a fixed amount of time, rather than the best possible solution.

The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. The heat causes the atoms to become unstuck from their initial positions (a local minimum of the internal energy) and wander randomly through states of higher energy; the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one.

Let's take a look at some pseudocode:

Randomly construct a valid solution
For each temperature do:
  For number of trials to do at each temperature do:
    Move solution to a neighbour
    Accept neighbour with probability(old_score, new_score, temperature)
    Lower the temperature by a reduction factor

It becomes clear that this method can be used in discrete optimization problems only, so that we can construct neighbours from our current state. E.g., a first solution in the problem we've been discussing might be [10,51,5,18] with a neighbour [10,52,5,18].

Also, a probability function needs to be defined. Some functions are constructed so that better solutions will always be accepted. Ideally, we would always like to assign a certain probability, so that worse solutions have a chance of being accepted too (or better ones have a chance at rejection). Again: this is to avoid local maxima (comparable with GA's).

Often, the new solution is accepted with an exponential distribution: exp( (new_score-old_score)/temperature ).

Note: the pseudocode at the Wikipedia page doesn't use trials, for some problems, this is good enough.

Let's see some Python code (again, based on the code mentioned in the previous posts):

from random import randint, random
from operator import add
from math import *

def individual(length, min, max):
  'Create a member of the population.'
  return [ randint(min,max) for x in xrange(length) ]

def fitness(individual, target):
  """
  Determine the fitness of an individual. Higher is better.
  individual: the individual to evaluate
  target: the target number individuals are aiming for
  """
  sum = reduce(add, individual, 0)
  return abs(target-sum)

def probability(o_fitness, n_fitness, temperature):
  if n_fitness < o_fitness:
    return 1
  return exp( (n_fitness-o_fitness) / temperature)

def temperature(step, max_steps):
  return max_steps - step

def neighbour(ind, min, max):
  pos_to_mutate = randint(0, len(ind)-1)

  if random() < 0.5:
    ind[pos_to_mutate] -= 1
  else:
    ind[pos_to_mutate] += 1

  if ind[pos_to_mutate] < min:
    ind[pos_to_mutate] = min
  elif ind[pos_to_mutate] > max:
    ind[pos_to_mutate] = max

  return ind

def evolve(ind, nr_trials, step, max_steps, min, max, target):
  best_fit = 10000;
  for i in range(1,nr_trials):
    n_ind = neighbour(ind, min, max)
    o_fitness = fitness(ind,target)
    n_fitness = fitness(n_ind,target)

  if n_fitness < best_fit:
    best_fit = n_fitness

  #move to new state?
  if probability(o_fitness, n_fitness, temperature(step,max_steps)) >= random():
    ind = n_ind
    print "Best fitness this evolution:",best_fit
    print "Temperature this evolution:",temperature(step,max_steps)

  return ind

If the fitness of the neighbour is better (remember: that means lower), we immediately accept it. We don't really need a chance of rejection for this problem. Otherwise, we use exp( (n_fitness-o_fitness) / temperature).
We use a separate function to calculate the temperature for each step. This function is kept fairly simple (max steps - this step), but non-linear temperature can also be implemented.

Let's try it, our starting temperature becomes 100, using 1000 trials per temperature:

import sys
sys.path.append("C:\Users\Seppe\Desktop")
from annealing import *
target = 300
i_length = 6
i_min = 0
i_max = 100
i = individual(i_length, i_min, i_max)
print fitness(i, target)
i_k = 0
i_kmax = 100
i_trials = 1000
while i_k < i_kmax:
  i = evolve(i, i_trials, i_k, i_kmax, i_min, i_max, target)
  i_k += 1

The output:

Best fitness this evolution: 34
Temperature this evolution: 100
Best fitness this evolution: 7
Temperature this evolution: 99
Best fitness this evolution: 0
Temperature this evolution: 98
Best fitness this evolution: 44
Temperature this evolution: 97
Best fitness this evolution: 43
Temperature this evolution: 96
Best fitness this evolution: 33
Temperature this evolution: 95
Best fitness this evolution: 39
Temperature this evolution: 94
Best fitness this evolution: 44
Temperature this evolution: 93
Best fitness this evolution: 34
Temperature this evolution: 92
Best fitness this evolution: 36
Temperature this evolution: 91
Best fitness this evolution: 50
Temperature this evolution: 90
Best fitness this evolution: 68
Temperature this evolution: 89
Best fitness this evolution: 67
Temperature this evolution: 88
Best fitness this evolution: 53
Temperature this evolution: 87
Best fitness this evolution: 49
Temperature this evolution: 86
Best fitness this evolution: 35
Temperature this evolution: 85
Best fitness this evolution: 55
Temperature this evolution: 84
Best fitness this evolution: 5
Temperature this evolution: 83
Best fitness this evolution: 0

Simulated annealing is easy to program and implement. Provided it is easy to construct neighbours, and a sensible combination of temperature and probability functions can be constructed, and the number of trials is well defined. Still: this method might be too naive to solve more difficult problems.

The source code can be downloaded here.

An interesting implementation is this. It is based on another genetic programming experiment located here (both are very interesting and fun examples, I highly recommend reading them).

Another Java applet to look at: solving a travelling salesman problem with simulated annealing.

-----

Table Of Contents (click a link to jump to that post)

1. Introduction

2. Genetic Algorithms

3. CHC Eshelman

4. Simulated Annealing

5. Ant Colony Optimization 

6. Tabu Search

7. Conclusion 

Testing CSS For Code Tag

Just ignore this... I'm testing the CSS for my code.

.code{
width: 464px;
overflow: auto;
background: #f8f8f8;
border-right: 1px dashed #e6e6e6;
border-top: 1px dashed #e6e6e6;
border-bottom: 1px dashed #e6e6e6;
border-left: 4px solid #e6e6e6;
margin-left: 10px;
padding: 4px;
}

pre,code,tt {
font: 'Liberation Mono', 'lucida console', 'courier new', monospace;
line-height:1.5;
}


Nokia N95, 3G, Bluetooth, And Ubuntu Intrepid - 3G Tethering Howto

The following steps are instructions to surf the web using a Nokia N95 with 3G, connected to your Intrepid laptop via Bluetooth.

1. Make sure you have the required packages installed:

sudo apt-get install bluez-utils bluez-pin ppp

2. Find out the phone's MAC address. Enable Bluetooth on phone and laptop, and enter the following command:

hcitool scan

Output example:

$ hcitool scan
Scanning ...
00:1C:9A:26:F5:DD Macuyiko N95

And note your MAC-address of your phone.

3. Find out the phone's channel, with the N95, this might change from time to time:

sdptool search --bdaddr MAC DUN | grep Channel

Replace MAC with your phone's MAC address.

Output example:

$ sudo sdptool search --bdaddr 00:1C:9A:26:F5:DD DUN | grep Channel
Channel: 4

Note this channel.

4. Edit /etc/ppp/peers/BluetoothDialup:

sudo gedit /etc/ppp/peers/BluetoothDialup

Paste the following:

/dev/rfcomm1 115200
local
nocrtscts
connect "/usr/sbin/chat -v -f /etc/chatscripts/proximus-gprs"
noauth
defaultroute
usepeerdns
novj
remotename proximus
debug
#user
lcp-restart 5
ms-dns 195.238.2.21

There are a few lines which you might need to change. I'm using the Belgium Proximus operator.

First of all, change /etc/chatscripts/proximus-gprs to something more related to your provider (e.g.: /etc/chatscripts/myprovider-gprs). We're going to create this script in the next step. Also: you might need to change the ms-dns entry as well (in most cases you can leave it out, but I had to add it though). Also notice that I have used /dev/rfcomm1 as the used device, we'll use this in the next steps as well.

5. Create a chatscript at /etc/chatscripts/proximus-gprs

sudo gedit /etc/chatscripts/proximus-gprs

Note that you may have chosen a different name for your chatscript in the previous step. Paste:

ABORT BUSY
ABORT 'NO CARRIER'
ABORT VOICE
ABORT 'NO DIALTONE'
ABORT 'NO DIAL TONE'
ABORT 'NO ANSWER'
"" ATZ
OK AT+CGDCONT=1,"IP","internet.proximus.be"
OK ATDT*99#
CONNECT ""

Notice the bold entries? You need to change them for your provider. Look up your APN and data profile number. If you google for "APN 3g [yourprovider]" you will often find the correct results, or look here for APNs for many providers. The data profile number line will often be OK ATDT*99# or OK ATDT*99***1#, so try them both.

6. Try it out

Enter the following command:

rfcomm connect RFCOMM# MAC CHANNEL

Replace RFCOMM# with the /dev/rfcomm-number you've used before (only the number!), I've used 1. MAC is your phone's MAC adres again, and CHANNEL is the channel you found earlier.

If all went well it should say:

$ rfcomm connect 1 00:1C:9A:26:F5:DD 4
Connected /dev/rfcomm1 to 00:1C:9A:26:F5:DD on channel 4
Press CTRL-C for hangup

Now we're going to enable the PPP connection, in a new terminal window (keep the "CTRL-C for hangup"-one open), enter:

pon BluetoothDialup

BluetoothDialup is the filename of the file we have created in /etc/ppp/peers/ earlier in step 4.

If all went well you should see an entry now in your ifconfig output:

$ ifconfig
ppp0      Link encap:Point-to-Point Protocol
          inet addr:81.169.31.99  P-t-P:10.6.6.6  Mask:255.255.255.255
          UP POINTOPOINT RUNNING NOARP MULTICAST  MTU:1500  Metric:1
          RX packets:3 errors:0 dropped:0 overruns:0 frame:0
          TX packets:4 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:3
          RX bytes:54 (54.0 B)  TX bytes:69 (69.0 B)

If you're done surfing the internet, turn off PPP:

poff

Press CTRL-C in that other terminal window to break the Bluetooth/3G-connection.

Note: if you've done something wrong (e.g.: used the wrong channel), you can release rfcomm's with:

rfcomm release RFCOMM#

With RFCOMM# equal to the /dev/rfcomm-number you've used before.

Optional steps: use gnome-ppp to connect

If you have gnome-ppp installed, you can also use a graphical interface to configure the above steps.

First of all, you still have to execute:

rfcomm connect RFCOMM# MAC CHANNEL

But you don't have to create the files from steps 4 and 5. We could automate the connect-step as well, but since the N95's channel changes from time to time, this wouldn't be very convenient. Also, I like having a terminal open to notify me that I'm still surfing via my phone.

Then open up gnome-ppp. If you have to enter a blank username and password for your provider, just enter some dummy values. I used "blank" and "blank" :).

Phone number: I tried *99***1# this time. And it also seemed to work, great!

Then press Setup. Enter the following values:

• Device: /dev/rfcomm1 (or the other rfcomm you defined earlier)
• Type: USB Modem (yes, USB!)
• Speed: 460800 works here, this probably means I could have used this value in the previous configuration files as well, instead of 115200
• Phone Line: Tone (default)
• Volume: High (default)

Then press Init Strings.

• Leave Init 2 unchanged (ATQ0 V1 E1 S0=0 &C1 &D2 +FCLASS=0)
• Enter this in Init 3: AT+CGDCONT=1,"IP","internet.proximus.be"
  Again, change this for your provider! I also had to manually define a DNS in the Networking tab, just like in the previous steps. This might not be the case for you.

You're done, make sure you're not wired or wirelessly connected to test this :).

Screenshot:

Final note: some people have to add novj to /etc/ppp/options as well. I didn't, tho. Check the Ubuntu forums/Google for information about your specific operator and/or hardware.

These instructions were only tested with my Thinkpad, my N95, and my operator. I've set up laptops with Vodafone cards before, and you can use gnome-ppp for those as well, just make sure you're using the correct device. Often the device will be at /dev/ttyS0, but use dmesg to find out the exact location.