src/test/bench/sudoku.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // ignore-pretty very bad with line comments
  12
  13 #![feature(box_syntax)]
  14 #![allow(non_snake_case)]
  15
  16 use std::old_io::BufferedReader;
  17 use std::old_io::stdio::StdReader;
  18 use std::old_io;
  19 use std::iter::repeat;
  20 use std::num::Int;
  21 use std::os;
  22
  23 // Computes a single solution to a given 9x9 sudoku
  24 //
  25 // Call with "-" to read input sudoku from stdin
  26 //
  27 // The expected line-based format is:
  28 //
  29 // 9,9
  30 // <row>,<column>,<color>
  31 // ...
  32 //
  33 // Row and column are 0-based (i.e. <= 8) and color is 1-based (>=1,<=9).
  34 // A color of 0 indicates an empty field.
  35 //
  36 // If called without arguments, sudoku solves a built-in example sudoku
  37 //
  38
  39 // internal type of sudoku grids
  40 type grid = Vec<Vec<u8> > ;
  41
  42 struct Sudoku {
  43     grid: grid
  44 }
  45
  46 impl Sudoku {
  47     pub fn new(g: grid) -> Sudoku {
  48         return Sudoku { grid: g }
  49     }
  50
  51     pub fn from_vec(vec: &[[u8;9];9]) -> Sudoku {
  52         let g = (0..9u).map(|i| {
  53             (0..9u).map(|j| { vec[i][j] }).collect()
  54         }).collect();
  55         return Sudoku::new(g)
  56     }
  57
  58     pub fn read(mut reader: &mut BufferedReader<StdReader>) -> Sudoku {
  59         /* assert first line is exactly "9,9" */
  60         assert!(reader.read_line().unwrap() == "9,9".to_string());
  61
  62         let mut g = repeat(vec![0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8, 0u8])
  63                           .take(10).collect::<Vec<_>>();
  64         for line in reader.lines() {
  65             let line = line.unwrap();
  66             let comps: Vec<&str> = line.as_slice()
  67                                        .trim()
  68                                        .split(',')
  69                                        .collect();
  70
  71             if comps.len() == 3u {
  72                 let row = comps[0].parse::<u8>().unwrap();
  73                 let col = comps[1].parse::<u8>().unwrap();
  74                 g[row as uint][col as uint] = comps[2].parse().unwrap();
  75             }
  76             else {
  77                 panic!("Invalid sudoku file");
  78             }
  79         }
  80         return Sudoku::new(g)
  81     }
  82
  83     pub fn write(&self, writer: &mut old_io::Writer) {
  84         for row in 0u8..9u8 {
  85             write!(writer, "{}", self.grid[row as uint][0]);
  86             for col in 1u8..9u8 {
  87                 write!(writer, " {}", self.grid[row as uint][col as uint]);
  88             }
  89             write!(writer, "\n");
  90          }
  91     }
  92
  93     // solve sudoku grid
  94     pub fn solve(&mut self) {
  95         let mut work: Vec<(u8, u8)> = Vec::new(); /* queue of uncolored fields */
  96         for row in 0u8..9u8 {
  97             for col in 0u8..9u8 {
  98                 let color = self.grid[row as uint][col as uint];
  99                 if color == 0u8 {
 100                     work.push((row, col));
 101                 }
 102             }
 103         }
 104
 105         let mut ptr = 0u;
 106         let end = work.len();
 107         while ptr < end {
 108             let (row, col) = work[ptr];
 109             // is there another color to try?
 110             let the_color = self.grid[row as uint][col as uint] +
 111                                 (1 as u8);
 112             if self.next_color(row, col, the_color) {
 113                 //  yes: advance work list
 114                 ptr = ptr + 1u;
 115             } else {
 116                 // no: redo this field aft recoloring pred; unless there is none
 117                 if ptr == 0u { panic!("No solution found for this sudoku"); }
 118                 ptr = ptr - 1u;
 119             }
 120         }
 121     }
 122
 123     fn next_color(&mut self, row: u8, col: u8, start_color: u8) -> bool {
 124         if start_color < 10u8 {
 125             // colors not yet used
 126             let mut avail = box Colors::new(start_color);
 127
 128             // drop colors already in use in neighbourhood
 129             self.drop_colors(&mut *avail, row, col);
 130
 131             // find first remaining color that is available
 132             let next = avail.next();
 133             self.grid[row as uint][col as uint] = next;
 134             return 0u8 != next;
 135         }
 136         self.grid[row as uint][col as uint] = 0u8;
 137         return false;
 138     }
 139
 140     // find colors available in neighbourhood of (row, col)
 141     fn drop_colors(&mut self, avail: &mut Colors, row: u8, col: u8) {
 142         for idx in 0u8..9u8 {
 143             /* check same column fields */
 144             avail.remove(self.grid[idx as uint][col as uint]);
 145             /* check same row fields */
 146             avail.remove(self.grid[row as uint][idx as uint]);
 147         }
 148
 149         // check same block fields
 150         let row0 = (row / 3u8) * 3u8;
 151         let col0 = (col / 3u8) * 3u8;
 152         for alt_row in row0..row0 + 3u8 {
 153             for alt_col in col0..col0 + 3u8 {
 154                 avail.remove(self.grid[alt_row as uint][alt_col as uint]);
 155             }
 156         }
 157     }
 158 }
 159
 160 // Stores available colors as simple bitfield, bit 0 is always unset
 161 struct Colors(u16);
 162
 163 static HEADS: u16 = (1u16 << 10) - 1; /* bits 9..0 */
 164
 165 impl Colors {
 166     fn new(start_color: u8) -> Colors {
 167         // Sets bits 9..start_color
 168         let tails = !0u16 << start_color as uint;
 169         return Colors(HEADS & tails);
 170     }
 171
 172     fn next(&self) -> u8 {
 173         let Colors(c) = *self;
 174         let val = c & HEADS;
 175         if 0u16 == val {
 176             return 0u8;
 177         } else {
 178             return val.trailing_zeros() as u8
 179         }
 180     }
 181
 182     fn remove(&mut self, color: u8) {
 183         if color != 0u8 {
 184             let Colors(val) = *self;
 185             let mask = !(1u16 << color as uint);
 186             *self    = Colors(val & mask);
 187         }
 188     }
 189 }
 190
 191 static DEFAULT_SUDOKU: [[u8;9];9] = [
 192          /* 0    1    2    3    4    5    6    7    8    */
 193   /* 0 */  [0u8, 4u8, 0u8, 6u8, 0u8, 0u8, 0u8, 3u8, 2u8],
 194   /* 1 */  [0u8, 0u8, 8u8, 0u8, 2u8, 0u8, 0u8, 0u8, 0u8],
 195   /* 2 */  [7u8, 0u8, 0u8, 8u8, 0u8, 0u8, 0u8, 0u8, 0u8],
 196   /* 3 */  [0u8, 0u8, 0u8, 5u8, 0u8, 0u8, 0u8, 0u8, 0u8],
 197   /* 4 */  [0u8, 5u8, 0u8, 0u8, 0u8, 3u8, 6u8, 0u8, 0u8],
 198   /* 5 */  [6u8, 8u8, 0u8, 0u8, 0u8, 0u8, 0u8, 9u8, 0u8],
 199   /* 6 */  [0u8, 9u8, 5u8, 0u8, 0u8, 6u8, 0u8, 7u8, 0u8],
 200   /* 7 */  [0u8, 0u8, 0u8, 0u8, 4u8, 0u8, 0u8, 6u8, 0u8],
 201   /* 8 */  [4u8, 0u8, 0u8, 0u8, 0u8, 7u8, 2u8, 0u8, 3u8]
 202 ];
 203
 204 #[cfg(test)]
 205 static DEFAULT_SOLUTION: [[u8;9];9] = [
 206          /* 0    1    2    3    4    5    6    7    8    */
 207   /* 0 */  [1u8, 4u8, 9u8, 6u8, 7u8, 5u8, 8u8, 3u8, 2u8],
 208   /* 1 */  [5u8, 3u8, 8u8, 1u8, 2u8, 9u8, 7u8, 4u8, 6u8],
 209   /* 2 */  [7u8, 2u8, 6u8, 8u8, 3u8, 4u8, 1u8, 5u8, 9u8],
 210   /* 3 */  [9u8, 1u8, 4u8, 5u8, 6u8, 8u8, 3u8, 2u8, 7u8],
 211   /* 4 */  [2u8, 5u8, 7u8, 4u8, 9u8, 3u8, 6u8, 1u8, 8u8],
 212   /* 5 */  [6u8, 8u8, 3u8, 7u8, 1u8, 2u8, 5u8, 9u8, 4u8],
 213   /* 6 */  [3u8, 9u8, 5u8, 2u8, 8u8, 6u8, 4u8, 7u8, 1u8],
 214   /* 7 */  [8u8, 7u8, 2u8, 3u8, 4u8, 1u8, 9u8, 6u8, 5u8],
 215   /* 8 */  [4u8, 6u8, 1u8, 9u8, 5u8, 7u8, 2u8, 8u8, 3u8]
 216 ];
 217
 218 #[test]
 219 fn colors_new_works() {
 220     assert_eq!(*Colors::new(1), 1022u16);
 221     assert_eq!(*Colors::new(2), 1020u16);
 222     assert_eq!(*Colors::new(3), 1016u16);
 223     assert_eq!(*Colors::new(4), 1008u16);
 224     assert_eq!(*Colors::new(5), 992u16);
 225     assert_eq!(*Colors::new(6), 960u16);
 226     assert_eq!(*Colors::new(7), 896u16);
 227     assert_eq!(*Colors::new(8), 768u16);
 228     assert_eq!(*Colors::new(9), 512u16);
 229 }
 230
 231 #[test]
 232 fn colors_next_works() {
 233     assert_eq!(Colors(0).next(), 0u8);
 234     assert_eq!(Colors(2).next(), 1u8);
 235     assert_eq!(Colors(4).next(), 2u8);
 236     assert_eq!(Colors(8).next(), 3u8);
 237     assert_eq!(Colors(16).next(), 4u8);
 238     assert_eq!(Colors(32).next(), 5u8);
 239     assert_eq!(Colors(64).next(), 6u8);
 240     assert_eq!(Colors(128).next(), 7u8);
 241     assert_eq!(Colors(256).next(), 8u8);
 242     assert_eq!(Colors(512).next(), 9u8);
 243     assert_eq!(Colors(1024).next(), 0u8);
 244 }
 245
 246 #[test]
 247 fn colors_remove_works() {
 248     // GIVEN
 249     let mut colors = Colors::new(1);
 250
 251     // WHEN
 252     colors.remove(1);
 253
 254     // THEN
 255     assert_eq!(colors.next(), 2u8);
 256 }
 257
 258 #[test]
 259 fn check_DEFAULT_SUDOKU_solution() {
 260     // GIVEN
 261     let mut sudoku = Sudoku::from_vec(&DEFAULT_SUDOKU);
 262     let solution   = Sudoku::from_vec(&DEFAULT_SOLUTION);
 263
 264     // WHEN
 265     sudoku.solve();
 266
 267     // THEN
 268     assert!(sudoku.equal(&solution));
 269 }
 270
 271 fn main() {
 272     let args        = os::args();
 273     let use_default = args.len() == 1u;
 274     let mut sudoku = if use_default {
 275         Sudoku::from_vec(&DEFAULT_SUDOKU)
 276     } else {
 277         Sudoku::read(&mut *old_io::stdin().lock())
 278     };
 279     sudoku.solve();
 280     sudoku.write(&mut old_io::stdout());
 281 }