Cursor と Rust で Ubongo を解いてみた

このプロジェクトとは Ubongo を解くためのものです。

次の方針で Ubongo を解くプログラムを生成してきます。
より良い方法があれば、実装前に提案してください。

----
アルゴリズムは以下で考えています。
1. 全8ピースを定義する
　- 形状、面積、マスの配置を二次元配列で指定する
2. 課題の面積から使うピースのセットを列挙する
3. 各セットについてピースを置く順番、裏表、回転4方向の組み合わせを列挙する
4. 課題に対して1マスずつピースを置けるか試行する
5. 全ピースを置ければクリア

課題の判定は、ボードの状態を二次元配列で持つことで行います。
- 0:マスなし
- 1:マスあり
- 2:ピースあり
3つ置いた時点でボードの全ての状態が0と2になればクリアです。

はい、Ubongoを解くためのプログラムの方針について理解しました。全体的に良い方針だと思いますが、いくつか改善点や補足を提案させていただきます：

1. データ構造の最適化:
    - ピースの表現方法として、二次元配列は直感的ですが、より効率的な表現方法として「ビットボード」を使用することを提案します。
    - 各マスを1ビットで表現することで、以下のメリットがあります：
        - メモリ効率が良い
        - ビット演算  で高速に重なりチェックができる
        - 回転や反転の操作が高速
2. ピースの配置判定の改善:
   - 現在の「1を足して2になる」という方法は機能しますが、ビット演算を使用すると以下のように簡潔になります：
        // ビット演算での例
     if (board & piece) == 0 {  // 重なりがない
         if ((board | piece) & boundary) == 0 {  // はみ出していない
             // 配置可能
         }
     }
これらの改善点を取り入れることで、より効率的で保守性の高いプログラムになると考えます。
実装を始める前に、これらの提案についてご意見をいただけますでしょうか？特に：
1. ビットボードを使用した実装に変更することについて
2. 提案したモジュール構造について
3. 追加したい機能や変更点はありますか？

お考えをお聞かせください。

// ZIPPO
■■■
■■

// Z
■■
 ■■

// T
 ■ 
■■■
// L
■
■■■

// LONG_Z
■■
 ■■■

// LONG_T
 ■
■■■■

// SHORT_BAR
■■■

use crate::utils::bit_ops::BitBoard;

#[derive(Debug, Clone)]
pub struct Piece {
    pub board: BitBoard,
    pub width: usize,
    pub height: usize,
    pub name: String,
}

impl Piece {
    pub fn new(shape: &[&str], name: &str) -> Self {
        let height = shape.len();
        let width = shape[0].len();
        let mut board = BitBoard::new();

        for (y, row) in shape.iter().enumerate() {
            for (x, ch) in row.chars().enumerate() {
                if ch == '1' {
                    board.set(x, y, true);
                }
            }
        }

        Self {
            board,
            width,
            height,
            name: name.to_string(),
        }
    }

    pub fn get_name(&self) -> &str {
        &self.name
    }

    pub fn get_board(&self) -> &BitBoard {
        &self.board
    }

    pub fn get_width(&self) -> usize {
        self.width
    }

    pub fn get_height(&self) -> usize {
        self.height
    }

    pub fn get_all_variants(&self) -> Vec<Piece> {
        let mut variants = Vec::with_capacity(8);
        let mut current = self.clone();

        // Original
        variants.push(current.clone());

        // Rotations
        for _ in 0..3 {
            current = current.rotate();
            variants.push(current.clone());
        }

        // Flipped
        current = self.flip();
        variants.push(current.clone());

        // Flipped rotations
        for _ in 0..3 {
            current = current.rotate();
            variants.push(current.clone());
        }

        variants
    }

    fn rotate(&self) -> Piece {
        let new_width = self.height;
        let new_height = self.width;
        let mut new_board = BitBoard::new();

        for y in 0..self.height {
            for x in 0..self.width {
                if self.board.get(x, y) {
                    new_board.set(new_width - 1 - y, x, true);
                }
            }
        }

        Piece {
            board: new_board,
            width: new_width,
            height: new_height,
            name: self.name.clone(),
        }
    }

    fn flip(&self) -> Piece {
        let mut new_board = BitBoard::new();

        for y in 0..self.height {
            for x in 0..self.width {
                if self.board.get(x, y) {
                    new_board.set(self.width - 1 - x, y, true);
                }
            }
        }

        Piece {
            board: new_board,
            width: self.width,
            height: self.height,
            name: self.name.clone(),
        }
    }

    pub fn area(&self) -> usize {
        let mut count = 0;
        for y in 0..self.height {
            for x in 0..self.width {
                if self.board.get(x, y) {
                    count += 1;
                }
            }
        }
        count
    }
}

pub fn create_all_pieces() -> Vec<Piece> {
    vec![
        Piece::new(&["1110", "1100"], "ZIPPO"),
        Piece::new(&["1100", "0110"], "Z"),
        Piece::new(&["0100", "1110"], "T"),
        Piece::new(&["1000", "1110"], "L"),
        Piece::new(&["1100", "0111"], "LONG_Z"),
        Piece::new(&["0100", "1111"], "LONG_T"),
        Piece::new(&["1110", "0000"], "SHORT_BAR"),
    ]
}

use crate::{
    piece::Piece,
    utils::{bit_ops::BitBoard, types::Position},
};

/// ピースの配置情報を保持する構造体
#[derive(Debug, Clone)]
pub struct PlacedPiece {
    pub piece: Piece,
    pub variant: Piece, // 回転・裏返しを適用した後のピース
    pub position: Position,
}

#[derive(Debug, Clone)]
pub struct Board {
    width: usize,
    height: usize,
    state: BitBoard,
}

impl Board {
    pub fn new(width: usize, height: usize) -> Self {
        Self {
            width,
            height,
            state: BitBoard::new(),
        }
    }

    pub fn get_width(&self) -> usize {
        self.width
    }

    pub fn get_height(&self) -> usize {
        self.height
    }

    pub fn get_state(&self) -> BitBoard {
        self.state
    }

    pub fn can_place_piece(&self, piece: &Piece, pos: Position) -> bool {
        let (x, y) = pos;
        let piece_board = piece.get_board();

        // Check if the piece fits within the board boundaries
        if x + piece.get_width() > self.width || y + piece.get_height() > self.height {
            return false;
        }

        // Check if the piece overlaps with any existing pieces
        for dy in 0..piece.get_height() {
            for dx in 0..piece.get_width() {
                if piece_board.get(dx, dy) && self.state.get(x + dx, y + dy) {
                    return false;
                }
            }
        }

        true
    }

    pub fn place_piece(&mut self, piece: &Piece, pos: Position) {
        let (x, y) = pos;
        let piece_board = piece.get_board();
        for dy in 0..piece.get_height() {
            for dx in 0..piece.get_width() {
                if piece_board.get(dx, dy) {
                    self.state.set(x + dx, y + dy, true);
                }
            }
        }
    }

    pub fn remove_piece(&mut self, piece: &Piece, pos: Position) {
        let (x, y) = pos;
        let piece_board = piece.get_board();
        for dy in 0..piece.get_height() {
            for dx in 0..piece.get_width() {
                if piece_board.get(dx, dy) {
                    self.state.set(x + dx, y + dy, false);
                }
            }
        }
    }

    pub fn display(&self) -> String {
        let mut result = String::new();
        for y in 0..self.height {
            for x in 0..self.width {
                if self.state.get(x, y) {
                    result.push('■');
                } else {
                    result.push('□');
                }
            }
            result.push('\n');
        }
        result
    }

    /// ボード上の1のビットの数（面積）を返します
    pub fn area(&self) -> usize {
        let mut count = 0;
        for y in 0..self.height {
            for x in 0..self.width {
                if self.state.get(x, y) {
                    count += 1;
                }
            }
        }
        count
    }

    /// 各ピースを異なる記号で表示します
    pub fn display_with_pieces(&self, placed_pieces: &[PlacedPiece]) -> String {
        let symbols = ['■', '★', '●', '◆', '▲', '♦', '♠', '♥'];
        let mut board_symbols = vec![vec!['□'; self.width]; self.height];
        let mut piece_indices = vec![vec![None; self.width]; self.height];

        // 各ピースの位置を記録
        for (i, placed) in placed_pieces.iter().enumerate() {
            let piece_board = placed.variant.get_board();
            let (x, y) = placed.position;

            for dy in 0..placed.variant.get_height() {
                for dx in 0..placed.variant.get_width() {
                    if piece_board.get(dx, dy) {
                        piece_indices[y + dy][x + dx] = Some(i);
                    }
                }
            }
        }

        // 記録された位置に基づいて記号を配置
        for y in 0..self.height {
            for x in 0..self.width {
                if let Some(i) = piece_indices[y][x] {
                    board_symbols[y][x] = symbols[i % symbols.len()];
                }
            }
        }

        // 文字列に変換
        let mut result = String::new();
        for row in board_symbols {
            for symbol in row {
                result.push(symbol);
            }
            result.push('\n');
        }
        result
    }
}

use crate::{
    board::{Board, PlacedPiece},
    piece::Piece,
    utils::types::Position,
};

#[derive(Debug)]
pub struct Solver {
    target_board: Board,
    pieces: Vec<Piece>,
    used_pieces: Vec<PlacedPiece>,
    current_board: Board,
    solutions: Vec<Vec<PlacedPiece>>, // 全ての解を保存
    verbose: bool,                    // デバッグ出力を制御するフラグ
}

impl Solver {
    pub fn new(target_board: Board, pieces: Vec<Piece>) -> Self {
        let width = target_board.get_width();
        let height = target_board.get_height();
        // ピースを面積の大きい順にソート
        let mut pieces = pieces;
        pieces.sort_by_key(|p| std::cmp::Reverse(p.area()));

        Self {
            target_board,
            pieces,
            used_pieces: Vec::new(),
            current_board: Board::new(width, height),
            solutions: Vec::new(),
            verbose: false,
        }
    }

    pub fn set_verbose(&mut self, verbose: bool) {
        self.verbose = verbose;
    }

    pub fn solve(&mut self) -> bool {
        if self.used_pieces.len() == self.pieces.len() {
            if self.current_board.get_state() == self.target_board.get_state() {
                // 解が見つかったら保存して探索を続ける
                self.solutions.push(self.used_pieces.clone());
                return false; // 探索を続けるためにfalseを返す
            }
            return false;
        }

        // 未使用のピースのうち、最も面積の大きいものから順に試す
        let current_piece_idx = self.used_pieces.len();
        let piece = self.pieces[current_piece_idx].clone();

        if self.verbose {
            println!("ピース {} を試行中...", piece.get_name());
        }

        for (variant_idx, variant) in piece.get_all_variants().iter().enumerate() {
            if self.verbose {
                println!("  バリエーション {} を試行中...", variant_idx + 1);
            }
            for y in 0..self.target_board.get_height() {
                for x in 0..self.target_board.get_width() {
                    let pos = (x, y);
                    if self.can_place_piece_at_target(variant, pos) {
                        if self.verbose {
                            println!("    位置 ({}, {}) に配置を試行", x, y);
                        }
                        self.place_piece(variant, pos);
                        self.used_pieces.push(PlacedPiece {
                            piece: piece.clone(),
                            variant: variant.clone(),
                            position: pos,
                        });

                        self.solve(); // 結果に関わらず探索を続ける

                        self.remove_piece(variant, pos);
                        self.used_pieces.pop();
                    }
                }
            }
        }

        false
    }

    fn can_place_piece_at_target(&self, piece: &Piece, pos: Position) -> bool {
        let mut temp_board = self.current_board.clone();

        // 1. ピースがボードの範囲内に収まるか確認
        if !temp_board.can_place_piece(piece, pos) {
            return false;
        }

        // 2. ピースを配置
        temp_board.place_piece(piece, pos);

        // 3. 新しく配置されたピースのビットを取得
        let piece_bits = temp_board.get_state() ^ self.current_board.get_state();

        // 4. ピースが目標ボードの1の位置に収まっているか確認
        // piece_bitsの1のビットが全てtarget_boardの1のビットの位置にあることを確認
        if (piece_bits & self.target_board.get_state()) != piece_bits {
            return false;
        }

        // 5. 他のピースと重なっていないか確認
        if !(piece_bits & self.current_board.get_state()).not_any() {
            return false;
        }

        true
    }

    fn place_piece(&mut self, piece: &Piece, pos: Position) {
        self.current_board.place_piece(piece, pos);
    }

    fn remove_piece(&mut self, piece: &Piece, pos: Position) {
        self.current_board.remove_piece(piece, pos);
    }

    fn is_piece_used(&self, piece: &Piece) -> bool {
        self.used_pieces
            .iter()
            .any(|p| p.piece.get_name() == piece.get_name())
    }

    pub fn get_solutions(&self) -> &[Vec<PlacedPiece>] {
        &self.solutions
    }

    pub fn display_all_solutions(&self) -> String {
        if self.solutions.is_empty() {
            return "解が見つかりませんでした。".to_string();
        }

        let mut result = format!("{}個の解が見つかりました！\n", self.solutions.len());

        for (solution_idx, solution) in self.solutions.iter().enumerate() {
            result.push_str(&format!("\n解 {}:\n", solution_idx + 1));
            result.push_str("使用したピース：\n");

            for (i, placed) in solution.iter().enumerate() {
                result.push_str(&format!(
                    "{}. {} at ({}, {})\n",
                    i + 1,
                    placed.piece.get_name(),
                    placed.position.0,
                    placed.position.1
                ));
            }

            result.push_str("\n配置：\n");
            let mut board = Board::new(
                self.target_board.get_width(),
                self.target_board.get_height(),
            );
            result.push_str(&board.display_with_pieces(solution));
            result.push('\n');
        }

        result
    }
}

use itertools::Itertools;
use ubongo_solver::{
    board::Board,
    piece::{create_all_pieces, Piece},
    solver::Solver,
};

struct Problem {
    pattern: Vec<&'static str>,
    num_pieces: usize,
}

impl Problem {
    fn new(pattern: Vec<&'static str>, num_pieces: usize) -> Self {
        Self {
            pattern,
            num_pieces,
        }
    }
}

fn create_target_board(width: usize, height: usize, pattern: &[&str]) -> Board {
    let mut board = Board::new(width, height);

    for (y, row) in pattern.iter().enumerate() {
        for (x, ch) in row.chars().enumerate() {
            if ch == '1' {
                board.place_piece(&Piece::new(&["1"], ""), (x, y));
            }
        }
    }
    board
}

fn solve_problem(problem: &Problem) {
    let width = problem.pattern[0].len();
    let height = problem.pattern.len();
    let target = create_target_board(width, height, &problem.pattern);

    println!("問題：\n{}", target.display());
    println!("使用ピース数: {}", problem.num_pieces);

    let all_pieces = create_all_pieces();
    let target_area = target.area();

    for pieces in all_pieces.into_iter().combinations(problem.num_pieces) {
        let total_area: usize = pieces.iter().map(|p| p.area()).sum();
        if total_area != target_area {
            continue;
        }

        let mut solver = Solver::new(target.clone(), pieces.clone());
        solver.solve();
        if !solver.get_solutions().is_empty() {
            println!("\n使用するピース:");
            for piece in &pieces {
                println!("- {} (面積: {})", piece.get_name(), piece.area());
            }
            println!("{}", solver.display_all_solutions());
        }
    }
}

fn main() {
    let problems = vec![
        Problem {
            pattern: vec!["10000", "11100", "11110", "11111"],
            num_pieces: 3,
        },
    ];

    for (i, problem) in problems.iter().enumerate() {
        println!("\n問題 {}:", i + 1);
        solve_problem(problem);
    }

    println!("\n探索が完了しました。");
}

■□□□□
■■■□□
■■■■□
■■■■■

合計3個の解が見つかりました！

解 1:
使用したピース：
1. ZIPPO at (0, 2)
2. Z at (1, 2)
3. L at (0, 0)

配置：
●□□□□
●●●□□
■■★★□
■■■★★

解 2:
使用したピース：
1. ZIPPO at (0, 2)
2. T at (1, 2)
3. L at (0, 0)

配置：
●□□□□
●●●□□
■■■★□
■■★★★

解 3:
使用したピース：
1. LONG_T at (0, 0)
2. Z at (1, 0)
3. T at (1, 2)

配置：
■□□□□
■■★□□
■★★●□
■★●●●