美術館というニコリのパズルを解くプログラムです．サンプル問題はニコリのお試し問題からの引用です．

main.rs

use std::io;
use std::time::Instant;

// 美術館(パズル)ソルバ

fn read_line() -> String{
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn read_ints() -> Vec<i64>{
    let s = read_line().replace("\t"," ");
    
    if s == ""{
        Vec::new()
    }else{
        let split:Vec<&str> = s.split(" ").collect();
        split.iter().map(|&x| x.to_string().parse().unwrap()).collect()
    }
}

const DXS : [i64; 4] = [0,0,1,-1];
const DYS : [i64; 4]  = [1,-1,0,0];

#[derive(PartialEq,Clone)]
enum Cell{
    Number(i64),    // 数字
    Block,          // ブロック
    Light,          // 照明
    Space,          // スペース(何もない場所)
}


struct Game{
    // board[x][y]は(x,y)にあるものをしめす
    pub board : Vec<Vec<Cell>>,
    // puttable[x][y]は(x,y)に置けるならtrue
    pub puttable : Vec<Vec<bool>>,
    // bright[x][y]は上下左右どこかに証明があって明るければtrue
    pub bright : Vec<Vec<bool>>,
    // board,puttable,brightの履歴(undo用)
    pub board_hist : Vec<Vec<Vec<Cell>>>,
    pub puttable_hist : Vec<Vec<Vec<bool>>>,
    pub bright_hist : Vec<Vec<Vec<bool>>>,
}

impl Game{
    pub fn new(board:Vec<Vec<Cell>>)->Game{
        // 最初はSpaceとなっている場所が置ける場所
        let puttable ={
            let mut temp = Vec::new();
            for i in 0..board.len(){
                let temp2 : Vec<bool> = board[i]
                    .iter()
                    .map(|x| *x == Cell::Space)
                    .collect();
                temp.push(temp2);
            }

            temp
        };
        // ブロックや数字のセルは明るくなっているとみなす
        // 初期ではスペース以外は全て明るいとみなす
        let bright ={
            let mut temp = Vec::new();
            for i in 0..board.len(){
                let temp2 : Vec<bool> = board[i]
                    .iter()
                    .map(|x| *x != Cell::Space)
                    .collect();
                temp.push(temp2);
            }

            temp
        };


        let mut ret = Game{
            board:board,
            puttable:puttable,
            bright:bright,
            board_hist:Vec::new(),
            puttable_hist:Vec::new(),
            bright_hist:Vec::new(),
        };

        for (x,y) in ret.scan_all(){
            // 数字の周りにはおけないようにする
            ret.number_protection(x,y);
        }

        ret
    }

    // ボードを表示する
    pub fn display_board(&self){
        // 5->space
        // 6->block
        let board = &self.board;

        println!("---------------- board ----------------");
        for x in 0..board.len(){
            for y in 0..board[0].len(){
                print!("{}",match board[x][y] {
                    Cell::Number(v) => format!("{}",v),
                    Cell::Space => format!(" "),
                    Cell::Light => format!("o"),
                    Cell::Block => format!("x"),
                });
            }
            println!("");
        }
        println!("---------------- board ----------------");
    }

    // 置ける場所を表示する
    pub fn display_puttable_place(&self){
        let puttable = &self.puttable;

        println!("--------------- puttable --------------");
        for x in 0..puttable.len(){
            for y in 0..puttable[0].len(){
                print!("{}",if puttable[x][y] {' '}else{'*'});
            }
            println!("");
        }
        println!("--------------- puttable --------------");
    }

    // 明るい場所を表示する
    pub fn display_bright(&self){
        let bright = &self.bright;

        println!("---------------- bright ---------------");
        for x in 0..bright.len(){
            for y in 0..bright[0].len(){
                print!("{}",if bright[x][y] {'o'}else{'x'});
            }
            println!("");
        }
        println!("---------------- bright ---------------");
    }

    // (x,y)が配列の範囲以外ならtrue
    fn out_bound(&self,x:i64,y:i64) -> bool{
        x < 0 || x as usize >= self.board.len()
                || y < 0 || y as usize >= self.board[0].len()
    }


    // 全要素の座標一覧
    fn scan_all(&self) -> Vec<(usize,usize)>{
        let mut ret = Vec::new();
        for x in 0..self.board.len(){
            for y in 0..self.board[0].len(){
                ret.push( (x,y));
            }
        }

        ret

    }

    // (x,y)まわりの座標一覧
    fn scan_around(&self,x:usize,y:usize) -> Vec<(usize,usize)>{
        let mut ret = Vec::new();

        for i in 0..4{
            let x = x as i64 + DXS[i];
            let y = y as i64 + DYS[i];

            if self.out_bound(x,y){
                continue;
            }

            ret.push( (x as usize,y as usize) );
        }
        
        ret
    }

    // (x,y)の(dx,dy)方向の座標一覧
    fn scan_space_line(&self,x:usize,y:usize,dx:i64,dy:i64) -> Vec<(usize,usize)>{
        let mut ret = Vec::new();

        for j in 1..{
            let x = x as i64 + dx * j;
            let y = y as i64 + dy * j;

            if self.out_bound(x,y){
                break;
            }

            if self.board[x as usize][y as usize] != Cell::Space{
                break;
            }

            ret.push( (x as usize,y as usize) );
        }
        
        ret
    }

    // (x,y)周りのセルのタイプがtargetの物の数を数える
    fn count_cell_around(&self,x:usize,y:usize,target:Cell) -> i64{
        let mut ret = 0;
        for (x,y) in self.scan_around(x,y){
            if self.board[x][y] == target{
                ret += 1;
            }
        }
        ret
    }

    // (x,y)周りの置ける場所の数を数える
    fn count_puttable_around(&self,x:usize,y:usize) -> i64{
        let mut ret = 0;
        for (x,y) in self.scan_around(x,y){
            if self.puttable[x][y] {
                ret += 1;
            }
        }
        ret
    }

    // 数字の周りに置かれた照明の数が条件を満たした場合
    // 数字の周囲におけないようにする
    fn number_protection(&mut self,x:usize,y:usize){
        if let Cell::Number(v) = self.board[x][y]{
            let n_light = self.count_cell_around(x,y,Cell::Light);

            if n_light != v{
                return;
            }

            // もう周囲はライトで埋まっている場合は
            // 周囲のputtableをfalseにする
            for (x,y) in self.scan_around(x,y){
                self.puttable[x][y]=false;
            }
        }
    }

    // (x,y)に明かりが置かれた場合に呼び出す
    // 上下左右のputtable,brightを更新し，
    // 上下左右のセルが明るくなったこと，置けなくなったことを示す
    fn light_protection(&mut self,x:usize,y:usize){
        self.puttable[x][y]=false;
        self.bright[x][y] = true;
        for i in 0..4{
            for (x,y) in self.scan_space_line(x,y,DXS[i],DYS[i]){
                self.puttable[x][y] = false;
                self.bright[x][y] = true;
            }
        }
    }
    
    // (x,y)に照明を置く
    // bright,puttableは勝手にやってくれる
    fn put(&mut self,x:usize,y:usize){
        if ! self.puttable[x][y]{
            panic!("Cannot put at ({},{}). Something wrong.",x,y);
        }
        // undoできるように履歴をとる
        self.board_hist.push(self.board.clone());
        self.puttable_hist.push(self.puttable.clone());
        self.bright_hist.push(self.bright.clone());

        self.board[x][y] = Cell::Light;
        self.light_protection(x,y);

        // 上下左右に数字があるかを確認
        // あった場合はおけない場所のputtableをfalseにする
        for (x,y) in self.scan_around(x,y){
            self.number_protection(x,y);
        }
    }

    // (dx,dy)方向に置ける場所があるか探す
    // あったらtrue
    fn search_puttable_line(&self,x:usize,y:usize,dx:i64,dy:i64)->bool{
        for (x,y) in self.scan_space_line(x,y,dx,dy){
            if self.puttable[x][y]{
                return true;
            }
        }

        false
    }

    // おかしなところがないか探す
    // あったらtrue
    fn is_wrong(&self)->bool{
        for (x,y) in self.scan_all(){
            if let Cell::Number(v) =  self.board[x][y]{
                let n_light = self.count_cell_around(x,y,Cell::Light);
                let n_puttable = self.count_puttable_around(x,y);

                // Numberの周りに指定された数をおけない事が判明した場合
                // →おかしいところがあるのでtrue
                if v - n_light > n_puttable{
                    return true;
                }
            }

            // 暗くて自分の場所に置けないことが判明している場合
            if ! self.bright[x][y] && ! self.puttable[x][y]{
                // 上下左右における場所がないか探す
                let found_puttable = (0..4)
                    .map(|i| self.search_puttable_line(x,y,DXS[i],DYS[i]))
                    .fold(false,|x,y| x | y );

                // なかったら何かがおかしい
                if ! found_puttable {
                    return true;
                }
            }
        }

        false
    }

    // 完成していたらtrue    
    pub fn finished(&self)->bool{
        // 明るくなっていないマスがあったらダメ
        for (x,y) in self.scan_all(){
            if ! self.bright[x][y] {
                return false;
            }
        }
        
        // おかしいところがあったらダメ
        if self.is_wrong(){
            return false;
        }
        
        return true;
    }

    // (x,y)が数字で，その周囲におけるマスの数が限られている場合
    // 置ける場所の数＝置く必要がある照明の数のとき，置ける場所全部に照明を置く
    // おけなかったらtrueを返す
    fn put_around_number(&mut self,x:usize,y:usize)->bool{
        if let Cell::Number(v) = self.board[x][y]{
            let n_puttable = self.count_puttable_around(x,y);

            // 置ける場所がないなら飛ばす
            if n_puttable == 0{
                return false;
            }

            let n_light = self.count_cell_around(x,y,Cell::Light);
            
            // 置かないといけない照明の数と置ける場所の数が一致
            // →置ける場所には全部置ける
            if v - n_light == n_puttable{
                for (x,y) in self.scan_around(x,y){
                    if self.puttable[x][y]{
                        self.put(x,y);
                    }
                }
                
                true
            }else{
                false
            }
        }else{
            false
        }
    }

    // 暗いのに上下左右における場所がないときはそこにおける
    // おけなかったらtrueを返す
    fn put_solo_light(&mut self,x:usize,y:usize)->bool{
        // 暗いが自分の場所に置ける場合
        if ! self.bright[x][y] && self.puttable[x][y]{
            // 上下左右における場所がないか探す
            let found_puttable = (0..4)
                .map(|i| self.search_puttable_line(x,y,DXS[i],DYS[i]))
                .fold(false,|x,y| x | y );

            // なかったらここに置く
            if ! found_puttable {
                self.put(x,y);

                return true;
            }
        }

        return false;
    }

    // 論理的に考えて，確実に置ける場所にのみライトを置く
    // 変化があったらtrueを返す
    fn put_logical(&mut self)->bool{
        let mut changed_all = false;
        loop {
            let mut changed = false;

            for (x,y) in self.scan_all(){
                changed |= self.put_around_number(x,y);
                // 遅くなることもあるし早くなる場合もある
                // changed |= self.put_solo_light(x,y);
            }

            changed_all |= changed;

            // もう変化しないなら終わり
            if ! changed{
                break;
            }
        }

        changed_all
    }

    // ひとつ巻き戻すメソッド
    fn undo(&mut self){
        self.board = self.board_hist.pop().unwrap();
        self.puttable = self.puttable_hist.pop().unwrap();
        self.bright = self.bright_hist.pop().unwrap();
    }

    // 探索木の深さがyearのところまで状態を戻す
    fn back_to_the_year(&mut self,year:usize){
        while self.puttable_hist.len() != year{
            self.undo();
        }
    }

    // 問題を解く関数
    // 解けたらtrueを返す
    pub fn solve(&mut self) ->bool{
        let year = self.puttable_hist.len();

        self.put_logical();

        if self.is_wrong(){
            // エラーがあったらダメ
            self.back_to_the_year(year);
            return false;
        }else if self.finished(){
            // 終わったらおわり
            return true;
        }else{
            // 照明を1つ置いてみて，矛盾した場合は置けない場所となる
            // 1手先だけ見るイメージ
            for (x,y) in self.scan_all(){
                if self.puttable[x][y]{
                    let year = self.puttable_hist.len();

                    // 1つだけ照明を置いてみて
                    self.put(x,y);
                    self.put_logical();
                    let wrong = self.is_wrong();
                    self.back_to_the_year(year);

                    // 矛盾するようなものが出てきたらおけない場所
                    if wrong{
                        self.puttable[x][y] = false;
                    }
                }
            }

            // 数字の周りを優先的に探索
            for (x,y) in self.scan_all(){
                if let Cell::Number(_) = self.board[x][y]{
                    for (x,y) in self.scan_around(x,y){
                        if ! self.puttable[x][y]{
                            continue;
                        }
                        self.put(x,y);
                        if self.solve(){
                            return true;
                        }
                        self.undo();
                        self.puttable[x][y]=false;
                    }
                }
            }

            // 全探索
            for (x,y) in self.scan_all(){
                if ! self.puttable[x][y]{
                    continue;
                }
                self.put(x,y);
                if self.solve(){
                    return true;
                }
                self.undo();
                self.puttable[x][y]=false;
            }
            
            if self.finished(){
                return true;
            }else{
                self.back_to_the_year(year);
                return false;
            }
        }
    }
}


fn main(){
    let mut game = Game::new({
        let mut temp = Vec::new();
        loop{
            let line : Vec<Cell> =
                read_ints()
                .iter()
                .map(|&x| match x {
                    n if 0 <= n && n <= 4 
                        => Cell::Number(n),
                    5   => Cell::Space,
                    6   => Cell::Block,
                    n   => panic!("Unexpected number: {}",n),
                })
                .collect();
            if line.len() == 0{
                break;
            }
            temp.push(line)
        }
        temp
    });
    
    let start = Instant::now();
    game.solve();
    let end = start.elapsed();
    game.display_board();
    println!("time:{}.{:03}",end.as_secs(), end.subsec_nanos() / 1_000_000);
    // game.display_puttable_place();
    // game.display_bright();
}

output01.txt

---------------- board ----------------
 o        
o4o x  o2o
 ox o   x 
    x0    
        o 
    o     
    1x    
 1o    0  
 1 o 1o x 
 o        
---------------- board ----------------
time:0.006

output05.txt

---------------- board ----------------
  o1     o1 o     
o1 x o1x1 x 1xxxx 
 xxx  x o x x  ox 
    o xxxxx xo1xx 
1xxx1      o1    o
o    1o      1xxx1
 x1xox xx1xx o    
 xo  x x o x  xx1o
 1xxxx x xx1o 1ox 
 o     1o     x o 
---------------- board ----------------
time:0.101

output10.txt

---------------- board ----------------
o 2o          x      o    1o        
  o2    o3o    x    o3o    xo    1o 
xo  2o  3o  xo  x o 1  o2  o2  o1  o
    o 11o x     o 11 o1 o     11 o1 
 x o21o      x o21 o     1o 11o     
 o 2   x   0  o2 o xo  x   1o  1o  x
  1o    0    o3    o2    o1     1 o 
o2  o    xo  3o      xo  1       1  
2o    1o  xo2o    0  o3o1    o1  o2o
1   1o      1   x   o   1o  1  o    
o      1o  1o      1  o1    o  1  o1
 xo  x    o1 x  ox o   1o3o  1o    1
  1      o3   xo      1  o3o      1o
   xo    2o    1  o  1o    1    o1  
1o  2 o 1  o2o  0   1  o2 o x  o3 o 
    o 21o x      o11o x o     12o x 
 1o 21o      2o 11    o  0 o21o     
o  1o  x  ox o 1o  1   x   2o  x   x
 o2  o  1o    1    oxo    0  o  1o  
  o      1    o      1   o       2o 
---------------- board ----------------
time:3.597

problem01.txt

5 5 5 5 5 5 5 5 5 5
5 4 5 5 6 5 5 5 2 5
5 5 6 5 5 5 5 5 6 5
5 5 5 5 6 0 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 1 6 5 5 5 5
5 1 5 5 5 5 5 0 5 5
5 1 5 5 5 1 5 5 6 5
5 5 5 5 5 5 5 5 5 5

problem05.txt

5 5 5 1 5 5 5 5 5 5 1 5 5 5 5 5 5 5
5 1 5 6 5 5 1 6 1 5 6 5 1 6 6 6 6 5
5 6 6 6 5 5 6 5 5 5 6 5 6 5 5 5 6 5
5 5 5 5 5 5 6 6 6 6 6 5 6 5 1 6 6 5
1 6 6 6 1 5 5 5 5 5 5 5 1 5 5 5 5 5
5 5 5 5 5 1 5 5 5 5 5 5 5 1 6 6 6 1
5 6 1 6 5 6 5 6 6 1 6 6 5 5 5 5 5 5
5 6 5 5 5 6 5 6 5 5 5 6 5 5 6 6 1 5
5 1 6 6 6 6 5 6 5 6 6 1 5 5 1 5 6 5
5 5 5 5 5 5 5 1 5 5 5 5 5 5 6 5 5 5

problem10.txt

5 5 2 5 5 5 5 5 5 5 5 5 5 5 6 5 5 5 5 5 5 5 5 5 5 5 1 5 5 5 5 5 5 5 5 5
5 5 5 2 5 5 5 5 5 3 5 5 5 5 5 6 5 5 5 5 5 3 5 5 5 5 5 6 5 5 5 5 5 1 5 5
6 5 5 5 2 5 5 5 3 5 5 5 6 5 5 5 6 5 5 5 1 5 5 5 2 5 5 5 2 5 5 5 1 5 5 5
5 5 5 5 5 5 1 1 5 5 6 5 5 5 5 5 5 5 1 1 5 5 1 5 5 5 5 5 5 5 1 1 5 5 1 5
5 6 5 5 2 1 5 5 5 5 5 5 5 6 5 5 2 1 5 5 5 5 5 5 5 1 5 5 1 1 5 5 5 5 5 5
5 5 5 2 5 5 5 6 5 5 5 0 5 5 5 2 5 5 5 6 5 5 5 6 5 5 5 1 5 5 5 1 5 5 5 6
5 5 1 5 5 5 5 5 0 5 5 5 5 5 3 5 5 5 5 5 2 5 5 5 5 5 1 5 5 5 5 5 1 5 5 5
5 2 5 5 5 5 5 5 5 6 5 5 5 3 5 5 5 5 5 5 5 6 5 5 5 1 5 5 5 5 5 5 5 1 5 5
2 5 5 5 5 5 1 5 5 5 6 5 2 5 5 5 5 5 0 5 5 5 3 5 1 5 5 5 5 5 1 5 5 5 2 5
1 5 5 5 1 5 5 5 5 5 5 5 1 5 5 5 6 5 5 5 5 5 5 5 1 5 5 5 1 5 5 5 5 5 5 5
5 5 5 5 5 5 5 1 5 5 5 1 5 5 5 5 5 5 5 1 5 5 5 1 5 5 5 5 5 5 5 1 5 5 5 1
5 6 5 5 5 6 5 5 5 5 5 1 5 6 5 5 5 6 5 5 5 5 5 1 5 3 5 5 5 1 5 5 5 5 5 1
5 5 1 5 5 5 5 5 5 5 3 5 5 5 6 5 5 5 5 5 5 5 1 5 5 5 3 5 5 5 5 5 5 5 1 5
5 5 5 6 5 5 5 5 5 2 5 5 5 5 5 1 5 5 5 5 5 1 5 5 5 5 5 1 5 5 5 5 5 1 5 5
1 5 5 5 2 5 5 5 1 5 5 5 2 5 5 5 0 5 5 5 1 5 5 5 2 5 5 5 6 5 5 5 3 5 5 5
5 5 5 5 5 5 2 1 5 5 6 5 5 5 5 5 5 5 1 1 5 5 6 5 5 5 5 5 5 5 1 2 5 5 6 5
5 1 5 5 2 1 5 5 5 5 5 5 5 2 5 5 1 1 5 5 5 5 5 5 5 0 5 5 2 1 5 5 5 5 5 5
5 5 5 1 5 5 5 6 5 5 5 6 5 5 5 1 5 5 5 1 5 5 5 6 5 5 5 2 5 5 5 6 5 5 5 6
5 5 2 5 5 5 5 5 1 5 5 5 5 5 1 5 5 5 5 5 6 5 5 5 5 5 0 5 5 5 5 5 1 5 5 5
5 5 5 5 5 5 5 5 5 1 5 5 5 5 5 5 5 5 5 5 5 1 5 5 5 5 5 5 5 5 5 5 5 2 5 5