Created
November 15, 2014 09:50
-
-
Save pocket7878/db26e930b5819f3769bd to your computer and use it in GitHub Desktop.
0hh1-solver writte in Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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 | |
#上下左右とくらべて、3つ連続はできない | |
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.") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
How do I run this?