Created
April 6, 2013 18:27
-
-
Save pcwalton/5327090 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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); | |
| } | |
| } | |
| } |
first puzzle 17 clue worst case
389 754 612
267 913 485
451 826 739
613 547 928
824 639 157
795 182 364
546 291 873
972 3108 541
138 475 296
puzzle type=MANUAL_INPUT
Elapsed time is: 17 milliseconds
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!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Worst case wiki 17 clue
================================
389 754 612
267 913 485
451 826 739
613 547 928
824 639 157
795 182 364
546 291 873
972 3108 541
138 475 296
puzzle type=MANUAL_INPUT
Elapsed time is: 17 milliseconds