0hh1-solver writte in Python

solver.py

#coding: utf-8

import sys

colors = 'rb'


def same_line(l1, l2):
    if len(l1) == len(l2):
        for i in range(len(l1)):
            if len(l1[i]) != 1 or len(l2[i]) != 1 or l1[i] != l2[i]:
                return False
        return True
    else:
        return False

def some(seq):
    """seqの要素からtrueであるものをどれか返す。"""
    for e in seq:
        if e:
            return e
    return False


class Board:
    def __init__(self, n):
        self.size = n
        self.rows = list(range(self.size))
        self.cols = list(range(self.size))
        self.board = [(r, c) for r in self.rows for c in self.cols]
        self.values = dict((s, colors) for s in self.board)
        unit_list = ([[(r, c) for c in self.cols] for r in self.rows] + [[(r, c) for r in self.rows] for c in self.cols])
        self.units = dict((s, [u for u in unit_list if s in u]) for s in self.board)

    def __assign(self, values, idx, s):
        rest_stone = values[idx].replace(s, '')
        if all(self.__eliminate(values, idx, d) for d in rest_stone):
            return values
        else:
            return False

    def __eliminate(self, values, idx, d):
        #範囲外
        if not (0 <= idx[0] < self.size and 0 <= idx[1] < self.size):
            return values
        #もともと取り除かれている
        if d not in values[idx]:
            return values
        values[idx] = values[idx].replace(d, '')
        if len(values[idx]) == 0:
            return False
        if len(values[idx]) == 1:
            v = values[idx]
            #行の半分が同じ色で埋まっていたら残りのセルは決定だね
            for u in self.units[idx]:
                same = [i for i in u if values[i] == v]
                rest = [i for i in u if values[i] != v]
                if len(same) == (self.size / 2):
                    if not all(self.__eliminate(values, r, v) for r in rest):
                        return False
                elif len(same) > (self.size / 2):
                    return False
            #他の行と見比べて同じになっていたらダメ
            my_line = [values[(i, idx[1])] for i in self.cols]
            for i in range(self.size):
                if i != idx[1]:
                    l = [values[(r, i)] for r in self.rows]
                    if same_line(my_line, l):
                        return False
            #上下左右とくらべて、３つ連続はできない
            if idx[0] != 0 and values[(idx[0] - 1, idx[1])] == v and \
                    (not self.__eliminate(values, (idx[0] - 2, idx[1]), v) or
                        not self.__eliminate(values, (idx[0] + 1, idx[1]), v)):
                return False
            if idx[0] < (self.size - 1) and values[(idx[0] + 1, idx[1])] == v and \
                    (not self.__eliminate(values, (idx[0] + 2, idx[1]), v) or
                        not self.__eliminate(values, (idx[0] - 1, idx[1]), v)):
                return False
            if idx[1] < (self.size - 1) and values[(idx[0], idx[1] + 1)] == v and \
                    (not self.__eliminate(values, (idx[0], idx[1] + 2), v) or
                        not self.__eliminate(values, (idx[0], idx[1] - 1), v)):
                return False
            if idx[1] != 0 and values[(idx[0], idx[1] - 1)] == v and \
                    (not self.__eliminate(values, (idx[0], idx[1] - 2), v) or
                        not self.__eliminate(values, (idx[0], idx[1] + 1), v)):
                return False
        return values

    def __grid_values(self, grid):
        chars = [c for c in grid if c in colors or c == '.']
        assert len(chars) == self.size ** 2
        return dict(zip(self.board, chars))

    def __parse_grid(self, grid):
        for idx, c in self.__grid_values(grid).items():
            if c in colors and not self.__assign(self.values, idx, c):
                return False
        return self.values

    def solve(self):
        if self.grid:
            res = self.__search(self.__parse_grid(self.grid))
            if res:
                self.values = res
                return True
            else:
                return False


    def __search(self, values):
        if values is False:
            return False
        if all(len(values[s]) == 1 for s in self.board):
            return values
        #まだ未決定なマスをひとつ見つける(色が2色しかないのでこれでよい)
        undecided = [(len(values[s]), s) for s in self.board if len(values[s]) > 1]
        if len(undecided) == 0:
            return False
        n, s = undecided[0]
        return some(self.__search(self.__assign(values.copy(), s, d)) for d in values[s])

    def display(self):
        for r in self.rows:
            print(''.join("["+self.values[(r, c)]+"]" for c in self.cols))
        print()


def read_board():
    n = int(sys.stdin.readline())
    b = Board(n)
    grid = ""
    for i in range(n):
        grid += sys.stdin.readline().rstrip()
    b.grid = grid
    return b

if __name__ == '__main__':
    b = read_board()
    if b.solve():
        b.display()
    else:
        print("Failed to solve.")

How do I run this?