こんなデータがあったとする。
| 1 | 2 | 3 | 4 5 6 8 9 | 4 5 6 8 9 | 4 5 6 8 9 | 6 8 9 | 7 | 4 6 8 9 |
| 4 6 | 5 | 4 6 | 1 2 3 4 6 7 8 9 | 1 2 3 4 6 7 8 9 | 1 2 3 4 6 7 8 9 | 1 3 6 8 9 | 1 3 4 6 8 9 | 1 3 4 6 8 9 |
| 7 | 8 | 9 | 1 3 4 6 | 1 3 4 6 | 1 3 4 6 | 1 3 6 | 2 | 5 |
| 2 3 5 6 8 9 | 1 3 6 7 9 | 1 2 5 6 7 8 | 1 2 3 5 6 7 8 9 | 1 2 3 5 6 7 8 9 | 1 2 3 5 6 7 8 9 | 4 | 1 3 5 6 8 9 | 1 2 3 6 7 8 9 |
| 2 3 4 5 6 8 9 | 1 3 4 6 7 9 | 1 2 4 5 6 7 8 | 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 6 7 8 9 | 1 3 5 6 8 9 | 1 2 3 6 7 8 9 |
| 2 3 4 5 6 8 9 | 1 3 4 6 7 9 | 1 2 4 5 6 7 8 | 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 6 7 8 9 | 1 3 5 6 8 9 | 1 2 3 6 7 8 9 |
| 2 3 4 5 6 8 9 | 1 3 4 6 7 9 | 1 2 4 5 6 7 8 | 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 6 7 8 9 | 1 3 4 5 6 8 9 | 1 2 3 4 6 7 8 9 |
| 2 3 4 5 6 8 9 | 1 3 4 6 7 9 | 1 2 4 5 6 7 8 | 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 6 7 8 9 | 1 3 4 5 6 8 9 | 1 2 3 4 6 7 8 9 |
| 2 3 4 5 6 8 9 | 1 3 4 6 7 9 | 1 2 4 5 6 7 8 | 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 6 7 8 9 | 1 3 4 5 6 8 9 | 1 2 3 4 6 7 8 9 |
2行目の左は、4と6のどちらかが入る。したがって、その左には4と6は入らない。右上の大きなセルで、4は7の右隣しか入りえない。
行・列・大きなセルを見て、上のようなペアがあったときに、そのペアに使われた数字はほかではもう使えない。これを組み入れてみた。
この程度のロジックで、雑誌の☆☆☆☆の問題があっさり解けた。あとで自力でやってみると、かなり時間がかかった。
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)
def __str__(self):
buff = ""
for row in self.a:
buff += str(row) + "\n"
return buff;
def strHTML(self):
buff = "<table border>\n"
for row in self.a:
buff += "<tr>"
for j in range(len(row)):
cell = row[j]
if type(cell) is int:
buff += "<td style=\"font-size:24;text-align:center\">"
buff += " " + str(cell) + " </td>"
else:
buff += "<td style=\"font-size:10\">"
for i in range(len(cell)):
if i % self.short_length == 2:
buff += str(cell[i]) + "<br>"
else:
buff += str(cell[i]) + " "
buff += "</td>"
buff += "</tr>\n"
buff += "</table>\n"
return buff;
def run(self):
counter = 0
while True:
self.update = False
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(r, c)
self.run_to_fix()
if not self.update:
break
def run_to_remove(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()
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:
self.a[i/3*3+pos[x]/3][(i%3)*3+pos[x]%3] = 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 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 % 3)
c_start = c0 - (c0 % 3)
for r in range(r_start, r_start + 3):
for c in range(c_start, c_start + 3):
yield self.a[r][c]
def gen_in_large_cell2(self, i):
r_start = i / 3 * 3
c_start = (i % 3) * 3
for r in range(r_start, r_start + 3):
for c in range(c_start, c_start + 3):
yield self.a[r][c]
def remove(self, cell, num):
for i in range(len(cell)):
if cell[i] == num:
cell[i:i+1] = [ ]
self.update = True
breaknp = cNumberPlace("numplace3.csv")
np.run()
print np.strHTML();
