sudoko/

strategies.rs

use crate::sudoku::Sudoku;

pub trait SolvingStrategy {
    fn apply(&self, sudoku: &mut Sudoku) -> bool;
    fn name(&self) -> &'static str;
}

/// Naked Singles: If a cell has only one possible candidate, fill it
pub struct NakedSingles;

impl SolvingStrategy for NakedSingles {
    fn apply(&self, sudoku: &mut Sudoku) -> bool {
        let mut progress = false;
        
        for row in 0..sudoku.size {
            for col in 0..sudoku.size {
                if sudoku.grid[row][col].is_empty() {
                    let candidates = sudoku.get_candidates(row, col);
                    if candidates.len() == 1 {
                        let value = *candidates.iter().next().unwrap();
                        sudoku.set(row, col, value).unwrap();
                        progress = true;
                    }
                }
            }
        }
        
        progress
    }

    fn name(&self) -> &'static str {
        "Naked Singles"
    }
}

/// Hidden Singles: If a value can only go in one cell in a unit (row, column, or box)
pub struct HiddenSingles;

impl SolvingStrategy for HiddenSingles {
    fn apply(&self, sudoku: &mut Sudoku) -> bool {
        let mut progress = false;
        
        // Check rows
        for row in 0..sudoku.size {
            progress |= self.apply_to_row(sudoku, row);
        }
        
        // Check columns
        for col in 0..sudoku.size {
            progress |= self.apply_to_col(sudoku, col);
        }
        
        // Check boxes
        for box_row in 0..sudoku.box_size {
            for box_col in 0..sudoku.box_size {
                progress |= self.apply_to_box(sudoku, box_row, box_col);
            }
        }
        
        progress
    }

    fn name(&self) -> &'static str {
        "Hidden Singles"
    }
}

impl HiddenSingles {
    fn apply_to_row(&self, sudoku: &mut Sudoku, row: usize) -> bool {
        let mut progress = false;
        
        for value in 1..=sudoku.size as u8 {
            let mut possible_cells = Vec::new();
            
            for col in 0..sudoku.size {
                if sudoku.grid[row][col].is_empty() {
                    let candidates = sudoku.get_candidates(row, col);
                    if candidates.contains(&value) {
                        possible_cells.push(col);
                    }
                }
            }
            
            if possible_cells.len() == 1 {
                let col = possible_cells[0];
                sudoku.set(row, col, value).unwrap();
                progress = true;
            }
        }
        
        progress
    }
    
    fn apply_to_col(&self, sudoku: &mut Sudoku, col: usize) -> bool {
        let mut progress = false;
        
        for value in 1..=sudoku.size as u8 {
            let mut possible_cells = Vec::new();
            
            for row in 0..sudoku.size {
                if sudoku.grid[row][col].is_empty() {
                    let candidates = sudoku.get_candidates(row, col);
                    if candidates.contains(&value) {
                        possible_cells.push(row);
                    }
                }
            }
            
            if possible_cells.len() == 1 {
                let row = possible_cells[0];
                sudoku.set(row, col, value).unwrap();
                progress = true;
            }
        }
        
        progress
    }
    
    fn apply_to_box(&self, sudoku: &mut Sudoku, box_row: usize, box_col: usize) -> bool {
        let mut progress = false;
        
        for value in 1..=sudoku.size as u8 {
            let mut possible_cells = Vec::new();
            
            for row in box_row * sudoku.box_size..(box_row + 1) * sudoku.box_size {
                for col in box_col * sudoku.box_size..(box_col + 1) * sudoku.box_size {
                    if sudoku.grid[row][col].is_empty() {
                        let candidates = sudoku.get_candidates(row, col);
                        if candidates.contains(&value) {
                            possible_cells.push((row, col));
                        }
                    }
                }
            }
            
            if possible_cells.len() == 1 {
                let (row, col) = possible_cells[0];
                sudoku.set(row, col, value).unwrap();
                progress = true;
            }
        }
        
        progress
    }
}

/// Naked Pairs: If two cells in a unit have the same two candidates, eliminate those from other cells
pub struct NakedPairs;

impl SolvingStrategy for NakedPairs {
    fn apply(&self, _sudoku: &mut Sudoku) -> bool {
        // This is a more complex strategy that would modify candidate lists
        // For now, we'll implement a simplified version
        false
    }

    fn name(&self) -> &'static str {
        "Naked Pairs"
    }
}

/// Pointing Pairs/Triples: If all candidates for a value in a box are in the same row/column
pub struct PointingPairs;

impl SolvingStrategy for PointingPairs {
    fn apply(&self, _sudoku: &mut Sudoku) -> bool {
        // This is a candidate elimination strategy
        // For simplicity, we'll implement basic logic
        false
    }

    fn name(&self) -> &'static str {
        "Pointing Pairs"
    }
}

/// Box/Line Reduction: If all candidates for a value in a row/column are in the same box
pub struct BoxLineReduction;

impl SolvingStrategy for BoxLineReduction {
    fn apply(&self, _sudoku: &mut Sudoku) -> bool {
        // This is a candidate elimination strategy
        false
    }

    fn name(&self) -> &'static str {
        "Box/Line Reduction"
    }
}

/// X-Wing: Advanced pattern recognition strategy
pub struct XWing;

impl SolvingStrategy for XWing {
    fn apply(&self, _sudoku: &mut Sudoku) -> bool {
        // Advanced strategy - simplified for now
        false
    }

    fn name(&self) -> &'static str {
        "X-Wing"
    }
}

/// Swordfish: Even more advanced pattern recognition
pub struct Swordfish;

impl SolvingStrategy for Swordfish {
    fn apply(&self, _sudoku: &mut Sudoku) -> bool {
        // Very advanced strategy - simplified for now
        false
    }

    fn name(&self) -> &'static str {
        "Swordfish"
    }
}

/// Y-Wing: A powerful advanced strategy using three cells with specific candidate patterns
pub struct YWing;

impl YWing {
    fn cells_see_each_other(&self, row1: usize, col1: usize, row2: usize, col2: usize, box_size: usize) -> bool {
        // Same row, column, or box
        row1 == row2 || 
        col1 == col2 || 
        (row1 / box_size == row2 / box_size && col1 / box_size == col2 / box_size)
    }
    
    fn apply_y_wing_elimination(&self, sudoku: &mut Sudoku, pivot: (usize, usize), wing1: (usize, usize), wing2: (usize, usize), value1: u8, value2: u8) -> bool {
        let mut progress = false;
        
        // Find cells that see both wings but not the pivot
        for row in 0..sudoku.size {
            for col in 0..sudoku.size {
                if sudoku.grid[row][col].is_empty() && 
                   (row, col) != pivot && (row, col) != wing1 && (row, col) != wing2 {
                    
                    if self.cells_see_each_other(row, col, wing1.0, wing1.1, sudoku.box_size) &&
                       self.cells_see_each_other(row, col, wing2.0, wing2.1, sudoku.box_size) {
                        
                        // Remove the intersection values from candidates
                        let mut candidates = sudoku.get_candidates(row, col);
                        let original_size = candidates.len();
                        
                        candidates.remove(&value1);
                        candidates.remove(&value2);
                        
                        if candidates.len() < original_size {
                            progress = true;
                            // In a full implementation, we'd update the candidate cache
                            // For now, this serves as a detection mechanism
                        }
                    }
                }
            }
        }
        
        progress
    }
}

impl SolvingStrategy for YWing {
    fn apply(&self, sudoku: &mut Sudoku) -> bool {
        let mut progress = false;
        
        // Find all cells with exactly 2 candidates (bi-value cells)
        let mut bi_value_cells = Vec::new();
        for row in 0..sudoku.size {
            for col in 0..sudoku.size {
                if sudoku.grid[row][col].is_empty() {
                    let candidates = sudoku.get_candidates(row, col);
                    if candidates.len() == 2 {
                        let values: Vec<u8> = candidates.into_iter().collect();
                        bi_value_cells.push((row, col, values[0], values[1]));
                    }
                }
            }
        }
        
        // Look for Y-Wing patterns
        for i in 0..bi_value_cells.len() {
            let (pivot_row, pivot_col, pivot_a, pivot_b) = bi_value_cells[i];
            
            for j in i + 1..bi_value_cells.len() {
                let (wing1_row, wing1_col, wing1_a, wing1_b) = bi_value_cells[j];
                
                // Check if wing1 shares exactly one value with pivot
                let shared_value = if pivot_a == wing1_a || pivot_a == wing1_b {
                    Some(pivot_a)
                } else if pivot_b == wing1_a || pivot_b == wing1_b {
                    Some(pivot_b)
                } else {
                    None
                };
                
                if let Some(shared) = shared_value {
                    let pivot_other = if pivot_a == shared { pivot_b } else { pivot_a };
                    let wing1_other = if wing1_a == shared { wing1_b } else { wing1_a };
                    
                    // Find wing2 that completes the Y-Wing
                    for k in j + 1..bi_value_cells.len() {
                        let (wing2_row, wing2_col, wing2_a, wing2_b) = bi_value_cells[k];
                        
                        // Wing2 should have pivot_other and wing1_other as candidates
                        if (wing2_a == pivot_other && wing2_b == wing1_other) ||
                           (wing2_a == wing1_other && wing2_b == pivot_other) {
                            
                            // Check if pivot sees both wings
                            if self.cells_see_each_other(pivot_row, pivot_col, wing1_row, wing1_col, sudoku.box_size) &&
                               self.cells_see_each_other(pivot_row, pivot_col, wing2_row, wing2_col, sudoku.box_size) &&
                               !self.cells_see_each_other(wing1_row, wing1_col, wing2_row, wing2_col, sudoku.box_size) {
                                
                                // Apply Y-Wing elimination
                                progress |= self.apply_y_wing_elimination(
                                    sudoku,
                                    (pivot_row, pivot_col),
                                    (wing1_row, wing1_col),
                                    (wing2_row, wing2_col),
                                    pivot_other,
                                    wing1_other
                                );
                            }
                        }
                    }
                }
            }
        }
        
        progress
    }

    fn name(&self) -> &'static str {
        "Y-Wing"
    }
}

/// XY-Wing: A variation of Y-Wing with different cell relationships
pub struct XYWing;

impl XYWing {
    fn cells_see_each_other(&self, row1: usize, col1: usize, row2: usize, col2: usize, box_size: usize) -> bool {
        // Same row, column, or box
        row1 == row2 || 
        col1 == col2 || 
        (row1 / box_size == row2 / box_size && col1 / box_size == col2 / box_size)
    }
    
    fn apply_xy_wing_elimination(&self, sudoku: &mut Sudoku, _pivot: (usize, usize), xz_wing: (usize, usize), yz_wing: (usize, usize), z_value: u8) -> bool {
        let mut progress = false;
        
        // Find cells that see both XZ and YZ wings
        for row in 0..sudoku.size {
            for col in 0..sudoku.size {
                if sudoku.grid[row][col].is_empty() && 
                   (row, col) != xz_wing && (row, col) != yz_wing {
                    
                    if self.cells_see_each_other(row, col, xz_wing.0, xz_wing.1, sudoku.box_size) &&
                       self.cells_see_each_other(row, col, yz_wing.0, yz_wing.1, sudoku.box_size) {
                        
                        // Remove Z value from candidates
                        let mut candidates = sudoku.get_candidates(row, col);
                        if candidates.contains(&z_value) {
                            candidates.remove(&z_value);
                            progress = true;
                            // In a full implementation, we'd update the candidate cache
                        }
                    }
                }
            }
        }
        
        progress
    }
}

impl SolvingStrategy for XYWing {
    fn apply(&self, sudoku: &mut Sudoku) -> bool {
        let mut progress = false;
        
        // Find all cells with exactly 2 candidates
        let mut bi_value_cells = Vec::new();
        for row in 0..sudoku.size {
            for col in 0..sudoku.size {
                if sudoku.grid[row][col].is_empty() {
                    let candidates = sudoku.get_candidates(row, col);
                    if candidates.len() == 2 {
                        let values: Vec<u8> = candidates.into_iter().collect();
                        bi_value_cells.push((row, col, values[0], values[1]));
                    }
                }
            }
        }
        
        // Look for XY-Wing patterns: XY pivot, XZ and YZ wings
        for i in 0..bi_value_cells.len() {
            let (pivot_row, pivot_col, x, y) = bi_value_cells[i];
            
            // Find XZ wing (shares X with pivot)
            for j in 0..bi_value_cells.len() {
                if i == j { continue; }
                let (xz_row, xz_col, xz_a, xz_b) = bi_value_cells[j];
                
                // Check if this cell shares X with pivot and has Z
                let z_value = if xz_a == x {
                    Some(xz_b)
                } else if xz_b == x {
                    Some(xz_a)
                } else {
                    None
                };
                
                if let Some(z) = z_value {
                    if z == y { continue; } // Z must be different from Y
                    
                    // Find YZ wing (shares Y with pivot and Z with XZ wing)
                    for k in 0..bi_value_cells.len() {
                        if k == i || k == j { continue; }
                        let (yz_row, yz_col, yz_a, yz_b) = bi_value_cells[k];
                        
                        // Check if this cell has Y and Z
                        if (yz_a == y && yz_b == z) || (yz_a == z && yz_b == y) {
                            // Check cell relationships: pivot must see both wings
                            if self.cells_see_each_other(pivot_row, pivot_col, xz_row, xz_col, sudoku.box_size) &&
                               self.cells_see_each_other(pivot_row, pivot_col, yz_row, yz_col, sudoku.box_size) {
                                
                                // Apply XY-Wing elimination
                                progress |= self.apply_xy_wing_elimination(
                                    sudoku,
                                    (pivot_row, pivot_col),
                                    (xz_row, xz_col),
                                    (yz_row, yz_col),
                                    z
                                );
                            }
                        }
                    }
                }
            }
        }
        
        progress
    }

    fn name(&self) -> &'static str {
        "XY-Wing"
    }
}

pub fn get_all_strategies() -> Vec<Box<dyn SolvingStrategy>> {
    vec![
        Box::new(NakedSingles),
        Box::new(HiddenSingles),
        Box::new(NakedPairs),
        Box::new(PointingPairs),
        Box::new(BoxLineReduction),
        Box::new(XWing),
        Box::new(YWing),
        Box::new(XYWing),
        Box::new(Swordfish),
    ]
}