Source

wd_pys60 / hebai.py

Full commit
#!/usr/bin/env python
#coding=utf-8

class Matrix(object):
    '''矩阵,用来表示n*n方格'''
    def __init__(self, n):
        self.n = n
        self._matrix = [[-1 for j in range(n)] for i in range(n)]
        # 初始化

        self._guess_list = [] # 猜测列表

    def display(self):
        # 打印矩阵
        for i in range(self.n):
            output = ''
            for j in range(self.n):
                output += str(self._matrix[i][j]) + '\t'
            print output

    def _check_rec(self, i, j):
        # 检查某个方格是否反转
        result = 0
        if i > 0:
            result += self._matrix[i-1][j]
        if i < self.n-1:
            result += self._matrix[i+1][j]
        if j > 0:
            result += self._matrix[i][j-1]
        if j < self.n-1:
            result += self._matrix[i][j+1]
        result += self._matrix[i][j]

        return result % 2 == 1

    def _check_result(self):
        # 检查最后得出的矩阵是否全部反转
        for i in range(self.n):
            for j in range(self.n):
                assert self._matrix[i][j] >= 0
                if not self._check_rec(i, j):
                    return False
        return True

    def _define_rec_val(self, i, j):
        # 确定(i, j)方格的值
        # return 0: 值是否是猜测
        # return 1:值
        guess = True
        
        above_val = -1
        if i > 0:
            above_val = 0
            if i > 1:
                above_val += self._matrix[i-2][j]
            if j > 0:
                above_val += self._matrix[i-1][j-1]
            if j < self.n-1:
                above_val += self._matrix[i-1][j+1]
            above_val += self._matrix[i-1][j]

        if above_val != -1:
            guess = False
            result = 0 if above_val%2==1 else 1
            return guess, result

        return guess, 0

    def _clear(self, i, j):
        # 将(i, j)之后的方块重置-1值
        for k in range(self.n):
            for l in range(self.n):
                if k>i or (k==i and l>=j):
                    self._matrix[k][l] = -1         

    def _run(self, i, j, start=True):
        # 主运行函数
        if not start: self._clear(i, j)
        else:
            self._guess_list.append((i, j))
        
        guess = 0 if start else 1
        self._matrix[i][j] = guess
        
        for k in range(self.n):
            for l in range(self.n):
                if k > i or (k==i and l>j):
                    temp = self._define_rec_val(k, l)
                    if temp[0] == True:
                        # 如果为猜测
                        self._matrix[k][l] = temp[1]
                        self._guess_list.append((k, l)) #添加至猜测列表
                    else:
                        self._matrix[k][l] = temp[1]

        if self._check_result():
            print 'Result: '
            self.display()
        else:
            if len(self._guess_list) > 0:
                self._run(*(self._guess_list.pop()), start=False)
        
        
    def __call__(self):
        self._run(0, 0)


if __name__ == '__main__':
    import sys
    n = 5
    if len(sys.argv) > 1:
        n = int(sys.argv[1])
    m = Matrix(n)
    m()