sudoku-rust/sudoku/src/sudoku.rs

// pub mod group;
use crate::group::*;

// use std::collections::HashSet;
use std::string::String;

const SIZE: u8 = 3;
/// Width of the sudoku board.
const WIDTH: u8 = SIZE*SIZE;
/// Size (width * height) of the board.
const MAX_SIZE: u8 = WIDTH * WIDTH; // 81;

// Use bitfields instead of HashSets.
use bit_field::BitField;

extern crate rand_chacha;
// use rand::prelude::*;
use rand::seq::SliceRandom;
use rand_chacha::rand_core::SeedableRng;
use rand_chacha::ChaCha20Rng;
use rand::distributions::{Distribution, Uniform};

// If I wanted to do 4x4 or 5x5, I would need more bits. (u32).

#[derive(Debug, Copy, Clone, PartialEq)]
pub struct Bits(u16);

/// Set bits number of bits to 1 (true)
pub const fn set_bits(bits: u8) -> u16 {
    (1 << (bits)) - 1
}

impl Bits {
    /// clear all bits
    pub fn clear(&mut self) {
        self.0 = 0;
    }

    /// set bit to state of value.
    pub fn set(&mut self, bit: u8, value: bool) {
        self.0.set_bit(bit as usize, value);
    }

    /// get state of bit.
    pub fn get(&self, bit: u8) -> bool {
        self.0.get_bit(bit as usize)
    }

    /// set bits on, given number of bits initially to set.
    pub fn set_bits(&mut self, bits: u8) {
        self.0 = set_bits(bits);
    }

    /// count number of bits set.
    pub fn count_set(&self) -> u8 {
        let mut count = 0;
        for i in 0..u16::BIT_LENGTH {
            if self.get(i as u8) {
                count += 1;
            }
        }
        count
    }
}

struct BitsIterator<'a> {
    possible: &'a Bits,
    index: u8,
}

impl Bits {
    fn iter(&self) -> BitsIterator {
        BitsIterator {
            possible: self,
            index: 1,
        }
    }
}

impl<'a> Iterator for BitsIterator<'a> {
    type Item = u8;

    fn next(&mut self) -> Option<u8> {
        while (self.index < u16::BIT_LENGTH as u8) && (!self.possible.get(self.index)) {
            self.index += 1;
            // println!("index = {}", self.index);
        }
        if self.index == u16::BIT_LENGTH as u8 {
            None
        } else {
            self.index += 1;
            Some(self.index - 1)
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::sudoku::*;

    #[test]
    fn check_possible_bitset() {
        let mut p = Bits(0);

        p.clear();

        for i in 0..9 {
            let mut result = p.get(i);
            assert_eq!(result, false);
            p.set(i, true);
            result = p.get(i);
            assert_eq!(result, true);
        }
    }

    #[test]
    fn check_possible_iter() {
        let mut p = Bits(0);
        p.set(3, true);
        p.set(5, true);
        p.set(6, true);
        assert_eq!(3, p.count_set());
        let values: Vec<u8> = p.iter().collect();
        assert_eq!(values, vec!(3, 5, 6));
        assert_eq!(3, p.count_set());
        p.set(0, true);
        assert_eq!(4, p.count_set());
    }

    #[test]
    fn check_bits() {
        // Set bits 0-5 (6 bits total)
        let p = Bits(set_bits(6));

        for i in 0..6 {
            let result = p.get(i);
            assert_eq!(result, true);
        }
        assert_eq!(p.get(6), false);
    }
}

pub type SudokuBoard = [u8; MAX_SIZE as usize];
pub type Possible = [Bits; MAX_SIZE as usize];
pub type SudokuPossible = [Bits; MAX_SIZE as usize];

#[derive(Debug, Clone, Copy)]
pub struct Board([u8; MAX_SIZE as usize]);
#[derive(Debug, Clone, Copy)]
pub struct BoardPossible([Bits; MAX_SIZE as usize]);

/*
I probably should keep board and possible separate from one another.
Possible is only used when solving the puzzles, and only used by the
logic solver.  Not needed by brute-force.

Ok, the problem is that the possible doesn't make any sense to be
unlinked in any way from the board.  I think they have to be together.
 */

 /*
#[derive(Debug, Clone, Copy)]
pub struct SudokuPossible {
    pub possible: [Possible; MAX_SIZE as usize];
}
*/

impl BoardPossible {
    /// Display the possibles.
    /// This should be in the Possible struct, not here.
    pub fn display(&self) {
        for y in 0..WIDTH {
            for x in 0..WIDTH {
                // print!("p={:?}", self.possible[pos(x, y) as usize]);
                let mut possible = String::new();

                for p in self.0[pos(x, y) as usize].iter() {
                    // print!("{},", p);
                    possible += format!("{},", p).as_str();
                }

                // for i in 0..SIZE {
                // let &pos = self.possible[pos(x, y) as usize];
                print!("({},{}):", x, y);
                // print!("{:20}", format!("{:?}", self.possible[pos(x, y) as usize]));
                print!("{:9}", possible);
                /*
                if pos == 0 {
                    print!(" ");
                } else {
                    print!("{}", pos);
                }
                */
                // }
                // print!(" ");
            }
            println!("");
        }
    }
}


#[derive(Debug, Clone, Copy)]
pub struct Sudoku {
    pub board: [u8; MAX_SIZE as usize], // Board
    pub possible: [Bits; MAX_SIZE as usize], // BoardPossible
}

/// Translate x,y to position in board.
pub const fn pos(x: u8, y: u8) -> u8 {
    x + (y * WIDTH as u8)
}

/// Translate x,y (with starting index of 1) to position in board.
pub const fn pos1(x: u8, y: u8) -> u8 {
    (x - 1) + ((y - 1) * WIDTH as u8)
}

/// Translate post to x,y in board.
pub const fn xy(pos: u8) -> (u8, u8) {
    ((pos % WIDTH), (pos / WIDTH))
}

const DEBUG_OUTPUT: bool = false;

/*
(0 .. 10)
                        .map(|_| HashSet::<usize>::new())
                        .collect();

let arr: [Vec<u32>; 10] = [(); 10].map(|_| Vec::with_capacity(100));

*/

impl Sudoku {
    pub fn new() -> Self {
        // 10 = WIDTH + 1
        // This would need to be changed in order to handle 4x4 or 5x5.
        // NOTE: We ignore bit 0, we use bits 1-9 (for 3x3).
        let mut initial: Bits = Bits(set_bits(10));
        initial.set(0, false);

        let s = Sudoku {
            board: [0; MAX_SIZE as usize],
            possible: [initial; MAX_SIZE as usize],
        };
        s
    }

    pub fn clear_possible(&mut self) {
        let mut initial = Bits(set_bits(10));
        initial.set(0, false);
        self.possible = [initial; MAX_SIZE as usize];
    }

    pub fn clear(&mut self) {
        let mut initial = Bits(set_bits(10));
        initial.set(0, false);

        self.board = [0; MAX_SIZE as usize];
        self.possible = [initial; MAX_SIZE as usize];
    }

    /// Load puzzle from a string.
    /// Note, we load from (top,left) going down, to (bottom,left) by columns.
    pub fn load_from_tld(&mut self, start_ch: char, blank: char, s: &str) {
        self.clear();
        let mut x: u8 = 0;
        let mut y: u8 = 0;

        for ch in s.chars() {
            if ch != blank {
                self.set(x, y, (ch as u8 - start_ch as u8) + 1);
            }
            y += 1;
            if y >= WIDTH {
                y = 0;
                x += 1;
            }
        }
    }

    /// Load puzzle from a string.
    /// This loads from (top,left) going right, to (top,right), by rows.
    pub fn load_from_tlr(&mut self, start_ch: char, blank: char, s: &str) {
        self.clear();
        let mut i: u8 = 0;

        for ch in s.chars() {
            if ch != blank {
                self.set(xy(i).0, xy(i).1, (ch as u8 - start_ch as u8) + 1);
            }
            i += 1;
        }
    }

    pub fn save_to_tld(&self, mut start_ch: char, blank: char) -> String {
        let mut result = String::new();
        result.reserve(MAX_SIZE as usize);
        start_ch = (start_ch as u8 - 1) as char;
        let mut x: u8 = 0;
        let mut y: u8 = 0;

        for _i in 0..MAX_SIZE {
            if self.board[pos(x, y) as usize] == 0 {
                result.push(blank);
            } else {
                result.push((start_ch as u8 + self.board[pos(x,y) as usize]) as char);
            }
            y += 1;
            if y >= WIDTH {
                y = 0;
                x += 1;
            }
        }
        result
    }

    pub fn save_to_tlr(&self, mut start_ch: char, blank: char) -> String {
        let mut result = String::new();
        result.reserve(MAX_SIZE as usize);
        start_ch = (start_ch as u8 - 1) as char;
        for i in 0..MAX_SIZE {
            if self.board[i as usize] == 0 {
                result.push(blank);
            } else {
                result.push((start_ch as u8 + self.board[i as usize]) as char);
            }
        }
        result
    }

    pub fn get(&self, x:u8, y:u8) -> u8 {
        self.board[pos(x,y) as usize]
    }

    /*
    This set does more then it needs to.
    When setting a location, it also updates the possible.
    This needs to be moved into something else.  Putting it into Possible?
     */

    pub fn set(&mut self, x: u8, y: u8, value: u8) {
        self.board[pos(x, y) as usize] = value;
        // Ok, update the possible
        let mut g = for_row(y);
        // g.for_row(x, y);
        for g in g.0 {
            // remove value from these sets.
            self.possible[g as usize].set(value, false);
            // self.possible[g as usize].take(&value);
        }
        g = for_column(x);
        // g.for_column(x, y);
        for g in g.0 {
            // remove value from these sets.
            self.possible[g as usize].set(value, false);
            // self.possible[g as usize].take(&value);
        }
        g = for_cell(which_cell(x, y));
        // g.for_block(x, y);
        for g in g.0 {
            // remove value from these sets.
            self.possible[g as usize].set(value, false);
            // self.possible[g as usize].take(&value);
        }
        self.possible[pos(x, y) as usize].clear();
    }

    /// Reset the Possible
    /// - For when a new puzzle has been loaded.
    /// - When something has changed, and the possibles are out of sync.
    pub fn reset_possible(&mut self) {
        // Reset the possible.
        self.clear_possible();
        for y in 0..WIDTH {
            for x in 0..WIDTH {
                let item: u8 = self.board[pos(x as u8, y as u8) as usize];
                if item != 0 {
                    let mut g: &Group = for_row(y);
                    for g in g.0 {
                    self.possible[g as usize].set(item, false);
                    }
                    g = for_column(x);
                    for g in g.0 {
                    self.possible[g as usize].set(item, false);
                    }
                    g = for_cell(which_cell(x,y));
                    for g in g.0 {
                    self.possible[g as usize].set(item, false);
                    }
                    self.possible[pos(x,y) as usize].clear();
                }
            }
        }
    }

    /// Display the sudoku puzzle.
    pub fn display(&self) {
        println!("╔═══╦═══╦═══╗");
        for y in 0..WIDTH {
            print!("║");
            for x in 0..WIDTH {
                let item = self.board[pos(x as u8, y as u8) as usize];
                if item == 0 {
                    print!(" ");
                } else if (item >= 1) && (item <= 9) {
                    print!("{}", item);
                }
                if x % 3 == 2 {
                    print!("║");
                }
            }
            println!("");
            if y % 3 == 2 {
                if y + 1 == WIDTH {
                    println!("╚═══╩═══╩═══╝");
                } else {
                    println!("╠═══╬═══╬═══╣");
                }
            }
        }
    }

    /// Display the possibles.
    /// This should be in the Possible struct, not here.
    pub fn display_possible(&self) {
        for y in 0..WIDTH {
            for x in 0..WIDTH {
                // print!("p={:?}", self.possible[pos(x, y) as usize]);
                let mut possible = String::new();

                for p in self.possible[pos(x, y) as usize].iter() {
                    // print!("{},", p);
                    possible += format!("{},", p).as_str();
                }

                // for i in 0..SIZE {
                // let &pos = self.possible[pos(x, y) as usize];
                print!("({},{}):", x, y);
                // print!("{:20}", format!("{:?}", self.possible[pos(x, y) as usize]));
                print!("{:9}", possible);
                /*
                if pos == 0 {
                    print!(" ");
                } else {
                    print!("{}", pos);
                }
                */
                // }
                // print!(" ");
            }
            println!("");
        }
    }

    /// Is the puzzle complete?
    /// Have all of the locations been filled with a value?
    /// - This does not validate that it is a correct puzzle,
    ///   - It doesn't check for duplicate digits (for example).
    pub fn puzzle_complete(&self) -> bool {
        for i in 0..MAX_SIZE {
            if self.board[i as usize] == 0 {
                return false;
            }
        }
        true
    }

    /// Recursive brute-force solver
    /// - As possibilities are tried, it recursively calls itself to see
    ///   if there are any solutions with the given possibility.
    fn calculate_possible(&mut self, total_solutions: &mut u16, solutions: &mut Vec<SudokuBoard>) -> bool {
        for idx in 0..MAX_SIZE {
            if self.board[idx as usize] == 0 {
                // Ok, there's a blank here

                let (x, y) = xy(idx);
                if DEBUG_OUTPUT {
                    println!("idx={} ({},{})", idx, x, y);
                    self.display();
                }

                'outer: for possible in 1..=9 {
                    let mut g = for_row(y);
                    for p in g.0 {
                        if self.board[p as usize] == possible {
                            continue 'outer;
                        }
                    }
                    g = for_column(x);
                    for p in g.0 {
                        if self.board[p as usize] == possible {
                            continue 'outer;
                        }
                    }
                    // check cell
                    let cell = which_cell(x, y);
                    g = for_cell(cell);
                    for p in g.0 {
                        if self.board[p as usize] == possible {
                            continue 'outer;
                        }
                    }

                    // Ok, it could go here!
                    if DEBUG_OUTPUT {
                        println!("({},{})={}", x, y, possible);
                    }

                    self.board[idx as usize] = possible;
                    if self.puzzle_complete() {
                        if *total_solutions < solutions.capacity() as u16 {
                            solutions.push(self.board);
                        }
                        *total_solutions += 1;
                        /*
                        println!("**SOLUTION**");
                        self.display();
                        println!("***");
                         */
                        break;
                    } else {
                        if self.calculate_possible(total_solutions, solutions) {
                            return true;
                        }
                    }
                }
                self.board[idx as usize] = 0;
                return false;
            }
        }

        false
    }

    /// Brute-force solver
    /// - Prints out a (one) solution.
    /// - Returns the number of solutions found.
    pub fn bruteforce_solver(&self) -> u16 {
        let mut workset = Sudoku {
            board: self.board,
            possible: [Bits(0); MAX_SIZE as usize],
        };

        let mut total_solutions: u16 = 0;
        let mut solutions = Vec::new();
        solutions.reserve(1);
        workset.calculate_possible(&mut total_solutions, &mut solutions);

        // return number of solutions.
        if solutions.len() > 0 {
            println!("*** A solution:");
            workset.board = solutions[0];
            workset.display();
            println!("***");
        }
        total_solutions
    }

    /// Make a sudoku puzzle.
    /// This gives us a fully solved puzzle.
    pub fn make(&mut self) {
        let mut rng = ChaCha20Rng::from_entropy();

        self.fill_board(&mut rng);
        // Ok, this gives us a random (but fully solved) puzzle.
    }

    /// Fill puzzle with random
    /// - This is like the brute-force solver, it calls itself recursively 
    ///   and backtraces if a solution can't be found.
    fn fill_board(&mut self, rng: &mut ChaCha20Rng) -> bool {
        let backup = Sudoku {
            board: self.board,
            possible: self.possible,
        };

        for idx in 0..MAX_SIZE {
            if self.board[idx as usize] == 0 {
                let (x, y) = xy(idx);
                let mut available: [u8; WIDTH as usize] = [0; WIDTH as usize];
                let mut total_available: u8 = 0;

                for t in self.possible[idx as usize].iter() {
                    available[total_available as usize] = t;
                    total_available += 1;
                }

                if total_available == 0 {
                    // No possible moves remain.
                    /*
                    self.board = backup.board;
                    self.possible = backup.possible;
                     */
                    return false;
                }

                // Randomize the possible items.
                available[0..total_available as usize].shuffle(rng);
                for v_idx in 0..total_available {
                    let value = available[v_idx as usize];
                    self.set(x, y, value);
                    if self.fill_board(rng) {
                        return true;
                    }
                    // failure
                    self.board = backup.board;
                    self.possible = backup.possible;
                }

                // We've run out of possible.
                return false;
            }
        }

        // We've visited everything, and it isn't 0.
        return true;
    }

    /// Puzzle generation
    /// - Removes a number, tests to see if the puzzle can still be solved by logic.
    /// - Returns true when still a valid, solvable puzzle.
    /// - Otherwise, restores number and returns false.
    pub fn remove(&mut self) -> bool {
        // Find a number, remove it. Save position.
        let mut rng = ChaCha20Rng::from_entropy();
        let puzrange = Uniform::new(0, WIDTH);
        let mut x = 0;
        let mut y = 0;
        let mut value: u8 = 0;

        while value == 0 {
            x = puzrange.sample(&mut rng);
            y = puzrange.sample(&mut rng);
            value = self.get(x,y);
        }

        self.set(x,y,0);

        // Clone, and solve by logic.
        let mut puzcopy = self.clone();

        puzcopy.reset_possible();
        /*
        puzcopy.display();
        puzcopy.display_possible();
         */
        // If solvable, return true.
        while puzcopy.solve(false) {};

        /*
        puzcopy.display();
        puzcopy.display_possible();
        */

        if puzcopy.puzzle_complete() {
            return true;
        }
        
        // If not solvable, restore number, return false.
        self.set(x,y,value);
        return false;
    }

    /*
    fn make_(&mut self) {
        self.clear();

        let mut rng = ChaCha20Rng::from_entropy();

        let pick_one = |this: &Self, rng: &mut ChaCha20Rng, idx: u8| -> Option<u8> {
            let mut available: [u8; WIDTH as usize] = [0; WIDTH as usize];
            let mut total_available: u8 = 0;

            for t in this.possible[idx as usize].iter() {
                available[total_available as usize] = t;
                total_available += 1;
            }
            if total_available == 1 {
                return Some(available[0]);
            }
            if total_available == 0 {
                return None;
            }
            Some(available[rng.gen_range(0..total_available as usize)])
        };

        for i in 0..MAX_SIZE {
            let (x, y) = xy(i);
            if self.board[i as usize] == 0 {
                // Ok, we found a blank space.
                let value = pick_one(self, &mut rng, i);
                if value.is_some() {
                    let value = value.unwrap();
                    if DEBUG_OUTPUT {
                        println!("Set({},{})={}", x, y, value);
                    }
                    self.set(x, y, value);
                }
            }
        }
    }
    */

    /// Solve, using logic alone
    /// - Returns true when something was added to the board.
    /// - Call solve until it returns false.
    pub fn solve(&mut self, debug: bool) -> bool {
        // Pass 1: Look for singles in the possible sets.
        let mut found_something = false;

        for i in 0..MAX_SIZE {
            if self.possible[i as usize].count_set() == 1 {
                // Get the value
                let value = self.possible[i as usize].iter().next().unwrap();
                // Found one!
                if debug {
                    println!("Set1 {:?} to {}", xy(i), value);
                }
                self.set(xy(i).0, xy(i).1, value);
                found_something = true;
            }
        }

        let mut g = Group::new();
        let mut values = Bits(0); // HashSet<u8> = HashSet::new();

        let mut group_process = |this: &mut Self, grp: &Group| {
            // Collect all the possible values within the group.
            values.clear();
            for gidx in 0..WIDTH {
                // println!("possible: {:?}", this.possible[grp.items[gidx as usize] as usize]);
                for v in this.possible[grp.0[gidx as usize] as usize].iter() {
                    values.set(v, true);
                }
                // values.extend(this.possible[grp.0[gidx as usize] as usize]);
                // println!("now     : {:?}", this.possible[grp.items[gidx as usize] as usize]);
            }

            // println!("values {:?}", values);

            // Now, check for singles.
            for v in values.iter() {
                let mut count = 0;
                let mut pos = 0;
                for gidx in 0..WIDTH {
                    if this.possible[grp.0[gidx as usize] as usize].get(v) {
                        // if this.possible[grp.0[gidx as usize] as usize].contains(&v) {
                        count += 1;
                        pos = grp.0[gidx as usize];
                        if count > 1 {
                            break;
                        }
                    }
                }
                if count == 1 {
                    // don't need this, it was v!
                    // let value = this.possible[pos as usize].iter().next().cloned().unwrap();
                    if debug {
                        println!("Set2 {:?} to {}", xy(pos), v);
                    }
                    this.set(xy(pos).0, xy(pos).1, v);
                    found_something = true;
                }
            }
        };

        // Change to 0..WIDTH ...  Keep it simple.
        for i in 0..WIDTH {
            let mut g = for_column(i);
            // g.for_column(i, 1);
            group_process(self, &g);
            g = for_row(i);
            // g.for_row(1, i);
            group_process(self, &g);
            g = for_cell(i);
            // g.for_iter(i);
            group_process(self, &g);
        }

        if found_something {
            return found_something;
        }

        if debug {
            println!("Looking for pairs...");
        }
        // PAIR processing.
        for i in 0..WIDTH {
            g.for_iter(i);

            for gidx in 0..WIDTH - 1 {
                let gpos = g.0[gidx as usize];
                if self.possible[gpos as usize].count_set() == 2 {
                    // Found a pair
                    for fidx in gidx + 1..WIDTH {
                        let fpos = g.0[fidx as usize];
                        if self.possible[fpos as usize].count_set() == 2 {
                            // Ok, there's another pair
                            // if self.possible[gpos as usize].is_subset(&self.possible[fpos as usize])
                            if self.possible[gpos as usize] == self.possible[fpos as usize] {
                                // Ok, they have the same values!
                                // Ok, remove the items in the pair from the cell.
                                // Don't touch the gpos/fpos records.  Keep those!
                                let mut values: [u8; 2] = [0, 0];
                                let mut vpos = 0;
                                for z in self.possible[gpos as usize].iter() {
                                    values[vpos] = z;
                                    vpos += 1;
                                }

                                let mut pair_removed = false;

                                // Check to see if anything was removed.

                                for remove in 0..WIDTH {
                                    if (gidx == remove) || (fidx == remove) {
                                        continue;
                                    }
                                    // Ok, these aren't the ones to save, so:
                                    let rpos = g.0[remove as usize];
                                    if self.possible[rpos as usize].get(values[0]) {
                                        self.possible[rpos as usize].set(values[0], false);
                                        found_something = true;
                                        pair_removed = true;
                                    }

                                    if self.possible[rpos as usize].get(values[1]) {
                                        self.possible[rpos as usize].set(values[1], false);
                                        found_something = true;
                                        pair_removed = true;
                                    }
                                }

                                // Check the x's and y's to see if we can also process a row/column too.
                                if xy(gpos).0 == xy(fpos).0 {
                                    // Matching X - process column
                                    let column = xy(gpos).0;

                                    vpos = 0;
                                    for z in self.possible[gpos as usize].iter() {
                                        values[vpos] = z;
                                        vpos += 1;
                                    }
                                    for remove in 0..WIDTH {
                                        if (remove == xy(gpos).1) || (remove == xy(fpos).1) {
                                            continue;
                                        }

                                        if self.possible[pos(column, remove) as usize]
                                            .get(values[0])
                                        {
                                            self.possible[pos(column, remove) as usize]
                                                .set(values[0], false);
                                            found_something = true;
                                            pair_removed = true;
                                        }

                                        if self.possible[pos(column, remove) as usize]
                                            .get(values[1])
                                        {
                                            self.possible[pos(column, remove) as usize]
                                                .set(values[1], false);
                                            found_something = true;
                                            pair_removed = true;
                                        }
                                    }
                                }

                                if xy(gpos).1 == xy(fpos).1 {
                                    // Matching Y - process row
                                    let row = xy(gpos).1;

                                    vpos = 0;
                                    for z in self.possible[gpos as usize].iter() {
                                        values[vpos] = z;
                                        vpos += 1;
                                    }
                                    for remove in 0..WIDTH {
                                        if (remove == xy(gpos).0) || (remove == xy(fpos).0) {
                                            continue;
                                        }
                                        if self.possible[pos(remove, row) as usize].get(values[0]) {
                                            self.possible[pos(remove, row) as usize]
                                                .set(values[0], false);
                                            found_something = true;
                                            pair_removed = true;
                                        }

                                        if self.possible[pos(remove, row) as usize].get(values[1]) {
                                            self.possible[pos(remove, row) as usize]
                                                .set(values[1], false);
                                            found_something = true;
                                            pair_removed = true;
                                        }
                                    }
                                }

                                if pair_removed {
                                    if debug {
                                        println!(
                                            "Pair found! {} {}: {} {:?} and {} {:?} !",
                                            gidx,
                                            fidx,
                                            gpos,
                                            xy(gpos),
                                            fpos,
                                            xy(fpos)
                                        );
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        found_something
    }
}