Puzzle1貌似有点问题

[31core]

Puzzle1应该类似于魔方, 不是所有情况都可以复原, 比如说

2 2 2 2
2 0 2 2
2 2 2 2
2 2 2 2

是不能复原的(应该是, 还没想到方法证明)

[qyl27]

是这样，这是阻碍本文继续更新的问题之一，现在在考虑是吃书还是找出一个部分解……

[qyl27]

根据此前的研究，是因为四种状态的问题，猜想如果状态总数为质数个，就能保证必定有解（如果状态只有2个就退化到关灯问题了）

[31core]

看看这个怎么样, 以4x4的矩阵为例, 由于只要矩阵的第一行的状态确定了, 2, 3行就可以推算出来, 最后一行就用来验证是否成立. 所以只需遍历 $4^N$ 次而不是之前以为的 $(4^N)^N$ 次

#[derive(Debug)]
pub struct Matrix {
    pub size: usize,
    pub items: Vec<isize>,
}

impl Matrix {
    pub fn new(size: usize) -> Self {
        Self {
            size,
            items: vec![0; size.pow(2)],
        }
    }
    pub fn get(&self, row: isize, col: isize) -> isize {
        if row >= 0 && row < self.size as isize && col >= 0 && col < self.size as isize {
            self.items[row as usize * self.size + col as usize]
        } else {
            0
        }
    }
    pub fn set(&mut self, row: isize, col: isize, val: isize) {
        self.items[row as usize * self.size + col as usize] = val;
    }
}

fn adjust_op(op: isize) -> isize {
    let mut op = op % 4;
    if op == 3 {
        op = -1;
    } else if op == -3 {
        op = 1;
    }
    op
}

fn check(origin: &Matrix, op: &mut Matrix) -> bool {
    for row in 1..origin.size as isize - 1 {
        for col in 0..origin.size as isize {
            op.set(
                row,
                col,
                adjust_op(
                    origin.get(row - 1, col) + op.get(row - 1, col)
                        - op.get(row - 1, col - 1)
                        - op.get(row - 1, col + 1)
                        - op.get(row - 2, col)
                        - 2,
                ),
            );
        }
    }

    let last_row = origin.size as isize - 1;
    for col in 0..origin.size as isize {
        op.set(
            last_row,
            col,
            adjust_op(
                origin.get(last_row - 1, col) + op.get(last_row - 1, col)
                    - op.get(last_row - 1, col - 1)
                    - op.get(last_row - 1, col + 1)
                    - op.get(last_row - 2, col)
                    - 2,
            ),
        );
        if col > 0
            && (origin.get(last_row, col - 1) + op.get(last_row, col - 1)
                - op.get(last_row, col)
                - op.get(last_row, col - 2)
                - op.get(last_row - 1, col - 1))
            .abs()
                != 2
        {
            return false;
        }
    }
    true
}

fn get_steps(op: &Matrix) -> usize {
    let mut sum = 0;
    for row in 0..op.size as isize {
        for col in 0..op.size as isize {
            sum += op.get(row, col).abs() as usize;
        }
    }
    sum
}

fn main() -> std::io::Result<()> {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input)?;
    input.pop(); // remove the '\n' character in the end of the string
    let cols = input.parse().unwrap();
    let mut origin = Matrix::new(cols);
    for row in 0..cols as isize {
        input.clear();
        std::io::stdin().read_line(&mut input)?;
        input.pop();
        let cows = input.split(" ").collect::<Vec<&str>>();
        for col in 0..cols as isize {
            origin.set(row, col, cows[col as usize].parse().unwrap());
        }
    }
    let mut op = Matrix::new(cols);

    /* set line 0 to -1 */
    for col in 0..cols as isize {
        op.set(0, col, -1);
    }

    let mut min_steps = 0;
    for _ in 0..4_u32.pow(cols as u32) {
        for col in 0..cols as isize {
            if op.get(0, col) > 2 {
                op.set(0, col, -1);
                op.set(0, col + 1, op.get(0, col + 1) + 1);
            }
        }
        if check(&origin, &mut op) {
            let steps = get_steps(&op);
            if min_steps == 0 || steps < min_steps {
                min_steps = steps;
            }
            //println!("{:?}", op); // uncomment this line to display all the posibilities
        }
        op.set(0, 0, op.get(0, 0) + 1);
    }
    println!("{}", min_steps);
    Ok(())
}

[qyl27]

不太懂rust怎么运行，容我用c#写一份验证一下，我尽量一周之内解决它

[qyl27]

我又考虑了一下，这个事实上可以转换为一个解线性同余方程组的问题。
把输入作为一个 n * n 维的向量，输入到一个线性变换里面，在模 4 的情况下得到全零的输出。
若该方程组的增广矩阵的秩小于阶数，则无解；否则可求出一个n维向量，将其各个维度上的数值相加，就可以得到答案。
（之所以存在无解的情况，是因为我们的模为 4 ，如果模是质数，则必定有解。）