こんなデータがあったとする。
1 2 3 5 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 |
1 2 3 5 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 |
1 2 3 5 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 | 1 2 3 4 5 6 7 8 9 |
4 | 1 2 3 5 7 8 9 | 1 2 3 5 7 8 9 | 1 2 5 6 7 8 9 | 1 2 5 6 7 8 9 | 1 2 5 6 7 8 9 | 1 2 3 5 6 7 8 9 | 1 2 3 5 6 7 8 9 | 1 2 3 5 6 7 8 9 |
1 2 5 | 1 2 5 7 8 9 | 1 2 5 7 8 9 | 3 | 1 2 4 5 6 7 8 9 | 1 2 4 5 6 7 8 9 | 1 2 4 5 6 7 8 9 | 1 2 4 5 6 7 8 9 | 1 2 4 5 6 7 8 9 |
6 | 1 2 3 5 7 8 9 | 1 2 3 5 7 8 9 | 1 2 4 5 7 8 9 | 1 2 4 5 7 8 9 | 1 2 4 5 7 8 9 | 1 2 3 4 5 7 8 9 | 1 2 3 4 5 7 8 9 | 1 2 3 4 5 7 8 9 |
7 | 1 2 3 4 5 6 | 1 2 3 4 5 6 | 1 2 4 5 6 8 9 | 1 2 3 4 5 6 8 9 | 1 2 3 4 5 6 8 9 | 1 2 3 4 5 6 8 9 | 1 2 3 4 5 6 8 9 | 1 2 3 4 5 6 8 9 |
8 | 1 2 3 4 5 6 | 1 2 3 4 5 6 | 1 2 4 5 6 7 9 | 1 2 3 4 5 6 7 9 | 1 2 3 4 5 6 7 9 | 1 2 3 4 5 6 7 9 | 1 2 3 4 5 6 7 9 | 1 2 3 4 5 6 7 9 |
9 | 1 2 3 4 5 6 | 1 2 3 4 5 6 | 1 2 4 5 6 7 8 | 1 2 3 4 5 6 7 8 | 1 2 3 4 5 6 7 8 | 1 2 3 4 5 6 7 8 | 1 2 3 4 5 6 7 8 | 1 2 3 4 5 6 7 8 |
一番左の列で3が入る可能性があるのは上3つ。だから、左上の3*3の中で左の列以外からは3が消える。
このロジックを入れれば、かなりの問題が解けるようになるのではないかと思う。
from math import *class cNumberPlace:
def __init__(self, n):
if type(n) is int:
self.a = [ [ -1 for i in range(n) ] for j in range(n) ]
elif type(n) is str:
self.a = [ ]
f = open(n, "r")
self.a = [ line.strip('\n').split(',') for line in f.readlines() ]
f.close()
if type(self.a) is int:
print self.a
for row in self.a:
for j in range(len(row)):
if len(row[j]) == 0:
row[j] = -1
else:
row[j] = int(row[j])
self.length = len(self.a)
self.short_length = int(sqrt(self.length))
for row in self.a:
for j in range(len(row)):
if row[j] == -1:
row[j] = range(1, self.length + 1)
self.counter = 0; # erase after
def __str__(self):
buff = ""
for row in self.a:
buff += str(row) + "\n"
return buff;
def strHTML(self):
buff = "
" buff += " " + str(cell) + " | "
else:
buff += "" for i in range(len(cell)): if i % self.short_length == 2: buff += str(cell[i]) + " " else: buff += str(cell[i]) + " " buff += " | "
buff += "
return buff;
def run(self):
while True:
self.update = False
self.run_to_remove()
self.run_to_fix()
if not self.update:
break
self.counter += 1
def run_to_remove(self):
for r in range(self.length):
for c in range(self.length):
cell = self.a[r][c]
if type(cell) is int:
self.run_to_remove_core(r, c)
def run_to_remove_core(self, r, c):
num = self.a[r][c]
for cell in self.gen_in_row(r):
if type(cell) is list:
self.remove(cell, num)
for cell in self.gen_in_column(c):
if type(cell) is list:
self.remove(cell, num)
for cell in self.gen_in_large_cell(r, c):
if type(cell) is list:
self.remove(cell, num)
def run_to_fix(self):
self.run_to_fix_single()
for r in range(self.length):
self.run_to_fix_in_row(r)
for c in range(self.length):
self.run_to_fix_in_column(c)
for i in range(self.length):
self.run_to_fix_in_large_cell(i)
if not self.update:
self.run_to_fix_pair()
self.run_to_fix_group()
def run_to_fix_single(self):
for row in self.a:
for c in range(self.length):
cell = row[c]
if type(cell) is list:
if len(cell) == 1:
row[c] = row[c][0]
self.update = True
def run_to_fix_in_row(self, r):
pos = self.set_single_num_pos(self.gen_in_row(r))
for x in range(1, self.length + 1):
if pos[x] >= 0:
self.a[r][pos[x]] = x
self.update = True
def run_to_fix_in_column(self, c):
pos = self.set_single_num_pos(self.gen_in_column(c))
for x in range(1, self.length + 1):
if pos[x] >= 0:
self.a[pos[x]][c] = x
self.update = True
def run_to_fix_in_large_cell(self, i):
pos = self.set_single_num_pos(self.gen_in_large_cell2(i))
for x in range(1, self.length + 1):
if pos[x] >= 0:
s = self.short_length
r = i / s * s + pos[x] / s
c = (i % s) * s + pos[x] % s
self.a[r][c] = x
self.update = True
def set_single_num_pos(self, gen):
pos = [ -1 for i in range(self.length + 1) ]
counter = 0
for cell in gen:
if type(cell) is list:
for x in cell:
if pos[x] == -1:
pos[x] = counter
else:
pos[x] = -2
else:
pos[cell] = -2
counter += 1
return pos
def run_to_fix_pair(self):
for r in range(self.length):
self.run_to_fix_pair_core(self.gen_in_row, r)
for c in range(self.length):
self.run_to_fix_pair_core(self.gen_in_column, c)
for i in range(self.length):
self.run_to_fix_pair_core(self.gen_in_large_cell2, i)
def run_to_fix_pair_core(self, f_gen, k):
pair = self.find_pair(f_gen(k))
if pair:
gen = f_gen(k)
for cell in gen:
if type(cell) is list and cell != pair:
self.remove(cell, pair[0])
self.remove(cell, pair[1])
if self.update:
return
def find_pair(self, gen):
pos = [ -1 for i in range(self.length + 1) ]
pairs = [ ]
for cell in gen:
if type(cell) is list and len(cell) == 2:
pairs.append(cell)
if len(pairs) >= 2:
for i in range(len(pairs) - 1):
for j in range(i + 1, len(pairs)):
if pairs[i] == pairs[j]:
return pairs[i]
return False
def run_to_fix_group(self):
for r in range(self.length):
for c0 in range(0, self.length, self.short_length):
gen1 = self.gen_in_small_row(r, c0)
gen2 = self.gen_in_except_row(r, c0)
gen3 = self.gen_in_except_cell_row(r, c0)
gen4 = self.gen_in_except_row(r, c0)
gen5 = self.gen_in_except_cell_row(r, c0)
self.run_to_fix_group_core(gen1, gen2, gen3, gen4, gen5)
for c in range(self.length):
for r0 in range(0, self.length, self.short_length):
gen1 = self.gen_in_small_column(r0, c)
gen2 = self.gen_in_except_column(r0, c)
gen3 = self.gen_in_except_cell_column(r0, c)
gen4 = self.gen_in_except_column(r0, c)
gen5 = self.gen_in_except_cell_column(r0, c)
self.run_to_fix_group_core(gen1, gen2, gen3, gen4, gen5)
def run_to_fix_group_core(self, gen1, gen2, gen3, gen4, gen5):
ary_bit = [ 0 for i in range(self.length + 1) ]
for cell in gen1:
self.set_bit_to_ary(ary_bit, cell, 1)
for cell in gen2:
self.set_bit_to_ary(ary_bit, cell, 2)
for cell in gen3:
self.set_bit_to_ary(ary_bit, cell, 4)
for i in range(1, self.length + 1):
if ary_bit[i] == 3:
for cell in gen4:
self.remove(cell, i)
elif ary_bit[i] == 5:
for cell in gen5:
self.remove(cell, i)
def set_bit_to_ary(self, ary_bit, cell, bit):
if type(cell) is list:
for i in cell:
ary_bit[i] |= bit;
else:
ary_bit[cell] |= bit;
def gen_in_row(self, r):
for c in range(self.length):
yield self.a[r][c]
def gen_in_column(self, c):
for r in range(self.length):
yield self.a[r][c]
def gen_in_large_cell(self, r0, c0):
r_start = r0 - (r0 % self.short_length)
c_start = c0 - (c0 % self.short_length)
for r in range(r_start, r_start + self.short_length):
for c in range(c_start, c_start + self.short_length):
yield self.a[r][c]
def gen_in_large_cell2(self, i):
r_start = i / self.short_length * self.short_length
c_start = (i % self.short_length) * self.short_length
for r in range(r_start, r_start + self.short_length):
for c in range(c_start, c_start + self.short_length):
yield self.a[r][c]
def gen_in_small_row(self, r, c0):
for c in range(c0, c0 + self.short_length):
yield self.a[r][c]
def gen_in_except_row(self, r, c0):
for c in range(self.length):
if c - c0 < 0 or self.short_length <= c - c0:
yield self.a[r][c]
def gen_in_except_cell_row(self, r1, c0):
r0 = r1 - r1 % self.short_length
for r in range(r0, r0 + self.short_length):
if r == r1:
continue
for c in range(c0, c0 + self.short_length):
yield self.a[r][c]
def gen_in_small_column(self, r0, c):
for r in range(r0, r0 + self.short_length):
yield self.a[r][c]
def gen_in_except_column(self, r0, c):
for r in range(self.length):
if r - r0 < 0 or self.short_length <= r - r0:
yield self.a[r][c]
def gen_in_except_cell_column(self, r0, c1):
c0 = c1 - c1 % self.short_length
for c in range(c0, c0 + self.short_length):
if c == c1:
continue
for r in range(r0, r0 + self.short_length):
yield self.a[r][c]
def remove(self, cell, num):
if type(cell) is list:
for i in range(len(cell)):
if cell[i] == num:
cell[i:i+1] = [ ]
self.update = True
break
np = cNumberPlace("numplace5.csv")
np.run()
print np.strHTML();