ナンプレ(6)

こんなデータがあったとする。

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 = "

\n" for row in self.a: buff += "" for j in range(len(row)): cell = row[j] if type(cell) is int: buff += "" else: buff += "" buff += "\n" buff += "
"
buff += " " + str(cell) + "
"
for i in range(len(cell)):
if i % self.short_length == 2:
buff += str(cell[i]) + "
"
else:
buff += str(cell[i]) + " "
buff += "
\n"
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();