Archive for January, 2007

I only came across H.264 recently, up to that point I thought DivX was supposed to be the be all and end all of video encoding. Two things brought it to my attention, first the promise of much smaller video sizes, and secondly, the new AppleTV doesn’t support DivX, but does support H.264.

So I installed thin liquid film, which is a Python QT frontend for ffmpeg. Once installed the program is very straightforward:

1. Select the file
2. Select the encoding (H.264)
3. Select the audio quality (I went for 128kbps)
4. Select the output directory
5. Click ‘Encode’

My test program was an old episode of Stargate SG-1 that had been recorded via a TV card, then encoded with DivX. The quality is pretty good, and the 45 minute show took 347M. The re-encoding took just under an hour (P4 - 2Ghz laptop, with stuff running in the background), pretty long if I’m going to re-encode every video I have. First impression, great, the file size dropped to 98M! More than a threefold saving, that would put off the construction of that 1TB NAS device I keep thinking about. Sadly it was not to last. The quality suffered a lot, even on my 14″ laptop screen the image was blurry. I guess two lossy encodings is too much, no matter how fancy they are.

But all might not be lost, I also have several DVD boxsets that I’d like available on my PC. With a DVD as a source it should produce a good quality video.

I’ve been meaning to write this for a while. It started when I camed across this page of the shortest sudoku solvers. They all follow the basic algorithm, which is described here. I orginally thought it was a brute force algorithm, so I wanted a more elegant solution, but on closer examination it in fact uses constraints and backtracking, like a Prolog program would. Still I wanted to write one in Prolog. It turns out it’s quite simple, and here is my program:

% Sudoku Solver
%
% Author: Miles Barr
% Version: 1.0
%
% Example Usage:
%
% Board = [ [_,_,3,_,4,9,_,_,8],
%           [_,1,_,5,_,_,_,3,_],
%           [8,_,7,3,_,_,_,_,_],
%           [_,6,8,9,_,_,_,_,5],
%           [2,_,_,_,_,_,_,_,6],
%           [4,_,_,_,_,6,7,1,_],
%           [_,_,_,_,_,5,9,_,3],
%           [_,8,_,_,_,1,_,6,_],
%           [9,_,_,2,3,_,1,_,_]
%         ],
% sudoku(Board),
% print_board(Board).

:- use_module(library('clp/bounds')).
:- use_module(library('lists')).

% Our general constraint is that each set of 9 (row, column or 3x3 grid) is made
% up from the numbers 1-9, and each number is not repeated.
valid(L) :- L in 1..9, all_different(L).

% Transpose function from Worksheet 16 of 'Clause and Effect'
transpose([[]|_],[]).
transpose(R,[H|C]) :- chopcol(R,H,T), transpose(T,C).
chopcol([],[],[]).
chopcol([[H|T]|R],[H|Hs],[T|Ts]) :- chopcol(R,Hs,Ts).

% Describe 3 grids in terms of 3 rows
% TODO: There must be a better way to do this.
grids([E11,E12,E13,E14,E15,E16,E17,E18,E19],
      [E21,E22,E23,E24,E25,E26,E27,E28,E29],
      [E31,E32,E33,E34,E35,E36,E37,E38,E39],
      [E11,E12,E13,E21,E22,E23,E31,E32,E33],
      [E14,E15,E16,E24,E25,E26,E34,E35,E36],
      [E17,E18,E19,E27,E28,E29,E37,E38,E39]).

% Print a board
print_board([]).
print_board([H|T]) :- write(H), nl, print_board(T).

% Sudoku solving function. 
%
% Input is nine lists of nine integers
sudoku(Board) :-
  % Break the board down into rows
  Board = [R1, R2, R3, R4, R5, R6, R7, R8, R9],
  % Transpose the board to get the columns
  transpose(Board, [C1, C2, C3, C4, C5, C6, C7, C8, C9]),
  % Cut up the rows into 3x3 grids
  grids(R1,R2,R3,G1,G2,G3),
  grids(R4,R5,R6,G4,G5,G6),
  grids(R7,R8,R9,G7,G8,G9),
  % Each row contains unique entries
  valid(R1), valid(R2), valid(R3),
  valid(R4), valid(R5), valid(R6),
  valid(R7), valid(R8), valid(R9),
  % Each column contains unique entries
  valid(C1), valid(C2), valid(C3),
  valid(C4), valid(C5), valid(C6),
  valid(C7), valid(C8), valid(C9),
  % Each grid contains unique entries
  valid(G1), valid(G2), valid(G3),
  valid(G4), valid(G5), valid(G6),
  valid(G7), valid(G8), valid(G9),

  % Turn the board into a list of 81 variables
  flatten(Board, Elements),
  %sign a value to each variable
  label(Elements).

I used SWI Prolog, but it should be trivial to port to other versions.

The general constraint is described by the valid clause, each list must contain all the numbers 1 through 9 exactly once. The list can represent a row, column or 3×3 grid. The next bit is breaking up the board into rows, columns and 3×3 grids, and then making sure each one is valid, which is what the sudoku clause does. That’s it really, and that’s what my first version looked like. In fact my original valid clause was:

valid(L) :- permutation([1,2,3,4,5,6,7,8,9], L).

and I didn’t constraint the values and do a labelling. That didn’t work, or it might work, but it takes a very long time. I came across this Prolog solver, which reminded me of labelling, so I removed the use of permutation, the result, a near instantaneous solver. I also borrowed his printing function.

It’s much longer than the other versions, but it has the nice property that you describe the constraints, and that’s your program, you don’t need to implement backtracking. There are still improvements to be made here, the most important one would be to add in some sort of heuristic to guide the backtracking, at the moment it’s naive and problem does more work than it needs to.

But is this the best way to solve a Sudoku puzzle? One other idea I’ve started thinking about is representing the board as a graph. We have 81 squares, each with 9 values, so we start off with 729 nodes. Each node represents a possible value for that square. Each value node for that square is connected to all the other value nodes of the squares next to it. As we discover the value of certain squares we can mark arcs to other values as illegal, and not use them in our path. Once we have a legal path through one value node for each square, we’re done. Ultimately this method requires the use of the same constraints, so it probably won’t be much better than the list based solution, but it could allow multiple walkers to discover legal row, column or grid paths in parallel, eventually joining them up. This parallelisation might lead to a faster solution. But I’ll leave the implementation and analysis to another time.