Sudoku solver in Rust. http://olav.it/experiment/rust-sudoku-solver/

sudoku.rs

#![feature(test)]
extern crate test;

const BOARD: &'static str = "
+---+---+---+
|375| 2 |4 9|
|   |3  |1  |
|812|   |7  |
+---+---+---+
| 47|2  | 3 |
|638|5 9|274|
| 9 |  7|58 |
+---+---+---+
|  4|   |612|
|  6|  8|   |
|9 3| 6 |847|
+---+---+---+
";

struct Sudoku {
	board: [u8; 9*9],
}

impl Sudoku {
	fn new() -> Sudoku {
		Sudoku{
			board: [0; 9*9],
		}
	}

	fn new_from_string(s: &str) -> Sudoku {
		let mut board: [u8; 9*9] = [0; 9*9];

		let mut board_started = false;
		let mut index = 0;
		for c in s.chars() {
			if c == '|' {
				board_started = true;
			}

			if !board_started {
				continue;
			}

			if index >= 81 {
				break;
			}

			let num = (c as i32)-48;
			if num >= 1 && num <= 9 {
				board[index] = num as u8;
				index += 1;
				continue;	
			} else if c == ' ' {
				index += 1;
			}
		}

		Sudoku{
			board: board,
		}
	}

	fn copy(&self) -> Sudoku {
		let mut board = [0; 9*9];
		for (i, num) in self.board.iter().enumerate() {
			board[i] = *num;
		}

		Sudoku{
			board: board,
		}
	}

	fn get(&self, x: usize, y: usize) -> u8 {
		self.board[y*9+x]
	}

	fn start_solver(&mut self) -> bool {
		self.solve(0)
	}

	fn validate_row(&self, y: usize) -> bool {
		let mut counters = [0; 9];
		for x in (0..9) {
			let val = self.get(x, y);
			if val == 0 {
				continue;
			}
			counters[val as usize-1] += 1;
			if counters[val as usize-1] > 1 {
				return false;
			}
		}
		true
	}

	fn validate_column(&self, x: usize) -> bool {
		let mut counters = [0; 9];
		for y in (0..9) {
			let val = self.get(x, y);
			if val == 0 {
				continue;
			}
			counters[val as usize-1] += 1;
			if counters[val as usize-1] > 1 {
				return false;
			}
		}
		true
	}

	fn validate_sub(&self, cx: usize, cy: usize) -> bool {
		let mut counters = [0; 9];
		for y in (cy*3..(cy+1)*3) {
			for x in (cx*3..(cx+1)*3) {
				let val = self.get(x, y);
				if val == 0 {
					continue;
				}
				counters[val as usize-1] += 1;
				if counters[val as usize-1] > 1 {
					return false;
				}
			}
		}
		true
	}

	fn is_valid(&self, index: usize) -> bool {
		let y = index / 9;
		let x = index - y * 9;
		
		self.validate_row(y) && self.validate_column(x) && self.validate_sub(x/3, y/3)
	}

	fn solve(&mut self, index: usize) -> bool {
		if index >= 81 {
			return true;
		}

		if self.board[index] != 0 {
			return self.solve(index+1);
		}

		for i in (1..10) {
			self.board[index] = i;
			if !self.is_valid(index) {
				self.board[index] = 0;
				continue;
			}

			if self.solve(index+1) {
				return true;
			}
		}
		false
	}


	fn print(&self) {
		let hr = "+---+---+---+";
		println!("{}", hr);
		for y in (0..9) {
			for x in (0..9) {
				if x%3 == 0 {
					print!("|");
				}
				let mut num = self.get(x, y);
				if num == 0 {
					print!(" ");
				} else {
					print!("{}", num);
				}
			}
			println!("|");
			if y%3 == 2 {
				println!("{}", hr);
			}
		}
		println!("");
	}
}

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    #[bench]
    fn bench_solve(b: &mut Bencher) {
    	let test_board = ::Sudoku::new_from_string(::BOARD);
        b.iter(|| test_board.copy().start_solver());
    }
}