gistfile1.rs

static LINES: [ &'static str, ..20 ] = [
    "..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9	near worst case for brute-force solver (wiki)",
    ".......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...	gsf's sudoku q1 (Platinum Blonde)",
    ".2..5.7..4..1....68....3...2....8..3.4..2.5.....6...1...2.9.....9......57.4...9..	(Cheese)",
    "........3..1..56...9..4..7......9.5.7.......8.5.4.2....8..2..9...35..1..6........	(Fata Morgana)",
    "12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8	(Red Dwarf)",
    "1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1	(Easter Monster)",
    ".......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....	Nicolas Juillerat's Sudoku explainer 1.2.1 (top 5)",
    "12.3.....4.....3....3.5......42..5......8...9.6...5.7...15..2......9..6......7..8",
    "..3..6.8....1..2......7...4..9..8.6..3..4...1.7.2.....3....5.....5...6..98.....5.",
    "1.......9..67...2..8....4......75.3...5..2....6.3......9....8..6...4...1..25...6.",
    "..9...4...7.3...2.8...6...71..8....6....1..7.....56...3....5..1.4.....9...2...7..",
    "....9..5..1.....3...23..7....45...7.8.....2.......64...9..1.....8..6......54....7	dukuso's suexrat9 (top 1)",
    "4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........	from http://magictour.free.fr/topn87 (top 3)",
    "7.8...3.....2.1...5.........4.....263...8.......1...9..9.6....4....7.5...........",
    "3.7.4...........918........4.....7.....16.......25..........38..9....5...2.6.....",
    "........8..3...4...9..2..6.....79.......612...6.5.2.7...8...5...1.....2.4.5.....3	dukuso's suexratt (top 1)",
    ".......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6...	first 2 from sudoku17",
    ".......12....35......6...7.7.....3.....4..8..1...........12.....8.....4..5....6..",
    "1.......2.9.4...5...6...7...5.3.4.......6........58.4...2...6...3...9.8.7.......1	2 from http://www.setbb.com/phpbb/viewtopic.php?p=10478",
    ".....1.2.3...4.5.....6....7..2.....1.8..9..3.4.....8..5....2....9..3.4....67.....",
];

struct Sudoku {
	r: [[i16, ..9], ..324],
	c: [[i16, ..4], ..729]
}

pub impl Sudoku {
    #[inline(always)]
	pub fn new() -> Sudoku {
		let mut s = Sudoku { r: [[0, ..9], ..324], c: [[0, ..4], ..729] };
		let mut nr: [i8, ..324] = [0, ..324], r = 0;
		for i16::range(0, 9) |i| {
			for i16::range(0, 9) |j| {
				for i16::range(0, 9) |k| {
					s.c[r][0] = 9 * i + j;
					s.c[r][1] = (i/3*3 + j/3) * 9 + k + 81;
					s.c[r][2] = 9 * i + k + 162;
					s.c[r][3] = 9 * j + k + 243;
					r += 1;
				}
			}
		}
		for i16::range(0, 729) |r| {
			for i16::range(0, 4) |c2| {
				let k = s.c[r][c2];
				s.r[k][nr[k]] = r;
				nr[k] += 1;
			}
		}
		return s;
	}
    #[inline(always)]
	fn update(&self, sr: &mut [i8], sc: &mut [u8], r: i32, v: i32) -> i32 {
		let mut min = 10, min_c = 0;
		for i32::range(0, 4) |c2| {
			sc[self.c[r][c2]] += (v<<7) as u8;
		}
		for i32::range(0, 4) |c2| {
			let c = self.c[r][c2];
			if v > 0 { // move forward
				for i32::range(0, 9) |r2| {
					let rr = self.r[c][r2];
					sr[rr] += 1;
					if sr[rr] == 1 {
						for i32::range(0, 4) |cc2| {
							let cc = self.c[rr][cc2];
							sc[cc] -= 1;
							if (sc[cc] < min) {
								min = sc[cc]; min_c = cc;
							}
						}
					}
				}
			} else {
				for i32::range(0, 9) |r2| {
					let rr = self.r[c][r2];
					sr[rr] -= 1;
					if sr[rr] == 0 {
						let p = self.c[rr];
						sc[p[0]] += 1; sc[p[1]] += 1; sc[p[2]] += 1; sc[p[3]] += 1;
					}
				}
			}
		}
		return (((min as i32) << 16) | (min_c as i32));
	}
    #[inline(never)]
	pub fn solve(&self, inp: &str) -> ~[~str] {
		let mut sc: [u8, ..324] = [9, ..324], sr: [i8, ..729] = [0, ..729];
		let mut cr: [i8, ..81] = [-1, ..81], cc: [i16, ..81] = [-1, ..81];
		let mut s: [i8, ..81] = [0, ..81], s8 = [48u8, ..81];
		let mut hints: i32 = 0;
		for i32::range(0, 81) |i| {
			let c = inp[i] as char;
			s[i] = -1;
			if c >= '1' && c <= '9' {
				s[i] = (c - '1') as i8;
				self.update(sr, sc, i * 9 + (s[i] as i32), 1);
				hints += 1;
				s8[i] = c as u8;
			}
		}

		let mut ret: ~[~str] = ~[];
		let mut i: i32 = 0, dir: i32 = 1, cand: i32 = 10<<16|0;
		loop {
			while i >= 0 && i < 81 - hints {
				if dir == 1 {
					let mut min: i32 = cand>>16;
					cc[i] = (cand & 0xffff) as i16;
					if min > 1 {
						for i32::range(0, 324) |c| {
							if (sc[c] as i32) < min {
								min = sc[c] as i32; cc[i] = c as i16;
								if min <= 1 { break; }
							}
						}
					}
					if min == 0 || min == 10 {
						cr[i] = -1; dir = -1; i -= 1;
					}
				}
				let c: i32 = cc[i] as i32;
				if dir == -1 && cr[i] >= 0 {
					self.update(sr, sc, self.r[c][cr[i]] as i32, -1);
				}
				let mut tmp: i32 = 9;
				for i32::range((cr[i] as i32) + 1, 9) |r2| {
					if sr[self.r[c][r2]] == 0 {
						tmp = r2;
						break;
					}
				}
				if tmp < 9 {
					cand = self.update(sr, sc, self.r[c][tmp] as i32, 1);
					cr[i] = tmp as i8; dir = 1; i += 1;
				} else {
					cr[i] = -1; dir = -1; i -= 1;
				}
			}
			if i < 0 { break; }
			for i32::range(0, i) |j| {
				let r = self.r[cc[j]][cr[j]];
				s8[r/9] = (r%9 + '1' as i16) as u8;
			}
			ret.push(str::from_bytes(s8));
			i -= 1; dir = -1;
		}
		return ret;
	}
}

#[fixed_stack_segment]
fn main() {
	let s = Sudoku::new();
    for uint::range(0, 50) |_| {
        for LINES.each |&line| {
            let _ = s.solve(line);
        }
	}
}

That platinum blonde was a monster!
This is the best result I could get out of my program:

Next best time. Extraordinary difficulty on that one. My program can finish an easy puzzle in 150 microseconds. Thanks for the puzzle!