Problem:


パズル

たろう君は 9 &times; 9 のマス目に 1〜9 の数字を配置するパズルで遊んでいます。このパズルでは以下の規則で数字を配置しなければいけません。

   
同じ列に 1 つの数字はちょうど 1 回だけ現われる

   
同じ行に 1 つの数字はちょうど 1 回だけ現われる

   
二重線で区切られた 3 &times; 3 の各範囲には、1 つの数字はちょうど 1 回だけ現われる

例えば、下の図 1 はそのような規則を満たした配置の一つです。しかしたろう君は、図 2 のようによく規則に反した配置を作ってしまいます。左端の列に「2」が 2 回現われて、「1」が 1 回も現われず、左から2 番目の列に「1」が 2 回現われて、「2」が 1 回も現われていません。

図 1 
図 2 

たろう君を助けるために、数字の配置を読み込んで、その配置が規則を満たしているかどうかを調べ、規則に反していたらその場所を出力するプログラムを作成してください。3 つの規則に照らして誤っている (2 回以上現れている) 数字の前には * (半角アスタリスク)を、誤っていない数字の前には空白を表示してください。

Input

複数のデータセットが与えられます。最初の行にデータセットの数 n (n ≤ 20) が与えられます。各データセットとして、パズルの状態を示す 1 行 9 文字、9 行からなる数字列が与えられます。

Output

各データセットについて以下を出力してください。

与えられた数字と * (半角アスタリスク)と空白。誤っている数字の前には *、誤っていない数字の前には半角空白を付加する。

データセットの間に 1 行の空行を入れてください。

Sample Input

2
2 1 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8
2 1 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

Output for the Sample Input

*2*1 3 4 5 6 7 8 9
 4 5 6 7 8 9 1 2 3
 7 8 9 1 2 3 4 5 6
*2 3 4 5 6 7 8 9 1
 5 6 7 8 9 1 2 3 4
 8 9 1 2 3 4 5 6 7
 3 4 5 6 7 8 9 1 2
 6 7 8 9 1 2 3 4 5
 9*1 2 3 4 5 6 7 8

*2*1 3 4 5 6 7 8 9
 4 5 6 7 8 9 1 2 3
 7 8 9 1 2 3 4 5 6
*2 3 4 5 6 7 8 9 1
 5 6 7 8 9 1 2 3 4
 8 9 1 2 3 4 5 6 7
 3 4 5 6 7 8 9 1 2
 6 7 8 9 1 2 3 4 5
 9*1 2 3 4 5 6 7 8



Sample input:
2
2 1 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8
2 1 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8


Sample output:
*2*1 3 4 5 6 7 8 9
 4 5 6 7 8 9 1 2 3
 7 8 9 1 2 3 4 5 6
*2 3 4 5 6 7 8 9 1
 5 6 7 8 9 1 2 3 4
 8 9 1 2 3 4 5 6 7
 3 4 5 6 7 8 9 1 2
 6 7 8 9 1 2 3 4 5
 9*1 2 3 4 5 6 7 8

*2*1 3 4 5 6 7 8 9
 4 5 6 7 8 9 1 2 3
 7 8 9 1 2 3 4 5 6
*2 3 4 5 6 7 8 9 1
 5 6 7 8 9 1 2 3 4
 8 9 1 2 3 4 5 6 7
 3 4 5 6 7 8 9 1 2
 6 7 8 9 1 2 3 4 5
 9*1 2 3 4 5 6 7 8

Submission status: Accepted

Solution code:
def check(h,w):
	s = A[h][w]
	if A[h].count(s) > 1 or RA[w].count(s) > 1 or A9[h/3][w/3].count(s) > 1:
		return "*"
	else:
		return " "
R = range(9)
for r in range(input()):
	if r > 0: print
	A  = [raw_input().split() for i in R]
	RA = [[A[h][w] for h in range(9)] for w in R] 
	A9 = [[A[h][w:w+3]+A[h+1][w:w+3]+A[h+2][w:w+3] for w in [0,3,6]] for h in [0,3,6]]
	P = [[check(h,w) for w in R] for h in R] 
	for h in R:
		print "".join([P[h][w]+A[h][w] for w in R])

Submission status: Accepted

Solution code:
def check(h,w):
	s = A[h][w]
	tf = A[h].count(s) > 1 or B[w].count(s) > 1 or C[h/3][w/3].count(s) > 1
	return "*" if tf else " "
R = range(9)
for r in range(input()):
	if r > 0: print
	A = [raw_input().split() for i in R]
	B = [[A[h][w] for h in R] for w in R] 
	C = [[A[h][w:w+3]+A[h+1][w:w+3]+A[h+2][w:w+3] for w in [0,3,6]] for h in [0,3,6]]
	P = [[check(h,w) for w in R] for h in R] 
	for h in R:
		print "".join([P[h][w]+A[h][w] for w in R])

Submission status: Accepted

Solution code:
n = int(input())

"""
def hor(matrix,y):
    res = [True]*9
    s = set()
    out = set()
    for i in matrix[y]:
        if i in s:
            out.add(i)
        s.add(i)
    for ind,i in enumerate(matrix[y]):
        if i in out:
            res[ind] = False
"""
def so(seq):
    res = [False]*9
    s = set()
    out = set()
    for i in seq:
        if i in s:
            out.add(i)
        s.add(i)
    for ind,i in enumerate(seq):
        if i in out:
            res[ind] = True
    return res

for num in range(n):
    matrix = [list(map(int, input().split())) for _ in range(9)]
    part = []
    for i in range(9):
        t = []
        for j in range(9):
            t.append(matrix[j][i])
        part.append(t)
    section = []
    for i in range(3):
        for j in range(3):
            t = []
            for k in range(3):
                for l in range(3):
                    t.append(matrix[i*3 + k][j*3 + l])
            section.append(t)   
        
    cor = [[False]*9 for _ in range(9)]

    for i in range(9):
        for ind,j in enumerate(so(matrix[i])):
            cor[i][ind] = cor[i][ind] or j
        for ind,j in enumerate(so(part[i])):
            cor[ind][i] = cor[ind][i] or j
        for ind,j in enumerate(so(section[i])):
            x = i % 3
            y = i // 3
            px = ind % 3
            py = ind // 3
            cor[y*3 + py][x*3 + px] = cor[y*3 + py][x*3 + px] or j
    for i,j in zip(cor, matrix):
        for k,l in zip(i,j):
            if k: t = '*'
            else: t = ' '
            print(f'{t}{l}',end='')
        print()
    if num != n-1: print()

Submission status: Accepted

Solution code:
n=int(input())
st=True
for _ in range(n):
    if st==False:
        print()

    puzzle=[]
    for i in range(9):
        row=[int(j) for j in input().split(" ")]
        puzzle.append(row)

    dup=[[False for i in range(9)] for j in range(9)]
    for i in range(9):
        for j in range(9):
            for k in range(9):
                if i!=k and puzzle[i][j]==puzzle[k][j]:
                    dup[i][j]=True
                if j!=k and puzzle[i][j]==puzzle[i][k]:
                    dup[i][j]=True

            for p in range(3):
                for q in range(3):
                    x=(i//3)*3+p
                    y=(j//3)*3+q
                    if (x==i and y==j):
                        continue

                    if puzzle[x][y]==puzzle[i][j]:
                        dup[i][j]=True

    for i in range(9):
        for j in range(9):
            if dup[i][j]:
                print("*", end="")
            else:
                print(" ", end="")
            print(puzzle[i][j], end="")
        print()
    st=False

Submission status: Accepted

Solution code:
n=int(input())
for i in range(n):
    board=[]
    check=[[0 for a in range(9)] for b in range(9)]
    for j in range(9):
        board.append(list(map(int,input().split())))
    board_r = [list(x) for x in zip(*board)]
    for j in range(9):
        for k in range(9):
            if board[j].count(board[j][k])>1:check[j][k]=1
    for j in range(9):
        for k in range(9):
            if board_r[j].count(board_r[j][k])>1:check[k][j]=1
    for j in range(3):
        for k in range(3):
            ch_list=[]
            for l in range(9):
                ch_list.append(board[j*3+l%3][k*3+l//3])
            for l in range(9):
                if ch_list.count(ch_list[l])>1:check[j*3+l%3][k*3+l//3]=1
    for j in range(9):
        for k in range(9):    
            if check[j][k]==1:print("*",end="")
            else:print(" ",end="")
            print(board[j][k],end="")
        print()
    if i<n-1:print()

Submission status: Runtime Error

Solution code:
def f(A): return A.count(a)>1
R=[0,3,6]
N=range(9)
Z=[0]*9

n=input()
while n:
  F=[[" " for _ in Z] for _ in Z]
  M=[map(int,raw_input().split()) for _ in Z]
  M1=[[M[y][x] for y in N] for x in N]
  M2=[M[y][x:x+3]+M[y+1][x:x+3]+M[y+2][x:x+3] for y in R for x in R]
  for y in N:
    p0=y/3*3
    for x in N:
      a=A[x]
      if any(map(f,[M[y],M1[x],M2[p0+x/3]])): F[y][x]="*"
    print "".join([a+b for a,b in zip(F[y],map(str,A))])
  if n>1: print
  n-=1

Submission status: Runtime Error

Solution code:
def f(A): return A.count(a)>1
R=[0,3,6]
N=range(9)
Z=[0]*9

n=input()
while n:
  F=[[" " for _ in Z] for _ in Z]
  M=[map(int,raw_input().split()) for _ in Z]
  M1=[[M[y][x] for y in N] for x in N]
  M2=[M[y][x:x+3]+M[y+1][x:x+3]+M[y+2][x:x+3] for y in R for x in R]
  for y in N:
    p0=y/3*3
    for x in N:
      a=M[y][x]
      if any(map(f,[M[y],M1[x],M2[p0+x/3]])): F[y][x]="*"
    print "".join([a+b for a,b in zip(F[y],map(str,A))])
  if n>1: print
  n-=1

Submission status: WA: Presentation Error

Solution code:
from collections import Counter

CounterKey = ("1", "2", "3", "4", "5", "6", "7", "8", "9")

inputCount = int(input())

for _ in range(inputCount):
    puzzle = []
    mark = []

    for lp in range(9):
        puzzle.append([item for item in input().split(" ")])
        mark.append([item for item in " " * 9])

    # 横
    for rowIndex, row in enumerate(puzzle):
        counter = Counter(row)
        needNum = [num for num in CounterKey if 1 < counter[num]]

        if not needNum:
            continue

        for colIndex, item in enumerate(row):
            if item in needNum:
                mark[rowIndex][colIndex] = "*"

    # 縦
    for colIndex, col in enumerate(
            zip(puzzle[0], puzzle[1], puzzle[2], puzzle[3], puzzle[4], puzzle[5], puzzle[6], puzzle[7], puzzle[8])):
        counter = Counter(col)
        needNum = [num for num in CounterKey if 1 < counter[num]]

        if not needNum:
            continue

        for rowIndex, item in enumerate(col):
            if item in needNum:
                mark[rowIndex][colIndex] = "*"

    # 四角
    for lp in range(3):
        block = []

        for blockCount, col in enumerate(zip(puzzle[lp * 3], puzzle[lp * 3 + 1], puzzle[lp * 3 + 2])):
            block.extend(col)

            if blockCount % 3 - 2 == 0:

                counter = Counter(block)
                needNum = [num for num in CounterKey if 1 < counter[num]]

                if needNum:

                    for index, item in enumerate(block):
                        if item in needNum:
                            rowIndex, colIndex = lp * 3 + index % 3, blockCount - 2 + index // 3
                            mark[rowIndex][colIndex] = "*"

                block = []

    # 出力
    for p, m in zip(puzzle, mark):
        output = []

        for num, state in zip(p, m):
            output.append(state)
            output.append(num)

        print("".join(output))

Submission status: WA: Presentation Error

Solution code:
from __future__ import print_function
from sys import stdin, stdout

try:
    xrange
except NameError:
    pass
else:
    range = xrange

def solve():
    table = []
    for _ in range(9):
        table.append(stdin.readline().split())
    
    check_table = []
    for _ in range(9):
        check_table.append([False] * 9)
    
    # horizontal check
    for i in range(9):
        a = []
        for j in range(9):
            a.append(table[i][j])
        for j in range(9):
            n = table[i][j]
            if a.count(n) > 1:
                check_table[i][j] = True
    
    # vertical check
    for j in range(9):
        a = []
        for i in range(9):
            a.append(table[i][j])
        for i in range(9):
            n = table[i][j]
            if a.count(n) > 1:
                check_table[i][j] = True
    
    # 9x9 check
    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            a = []
            for di in range(3):
                for dj in range(3):
                    a.append(table[i + di][j + dj])
            for di in range(3):
                for dj in range(3):
                    n = table[i + di][j + dj]
                    if a.count(n) > 1:
                        check_table[i + di][j + dj] = True
    
    for i in range(9):
        for j in range(9):
            if check_table[i][j]:
                stdout.write('*')
            else:
                stdout.write(' ')
            stdout.write(table[i][j])
        stdout.write('\n')

if __name__ == '__main__':
    N = int(stdin.readline())
    for _ in range(N):
        solve()

Submission status: WA: Presentation Error

Solution code:
from __future__ import print_function
from sys import stdin, stdout

try:
    xrange
except NameError:
    pass
else:
    range = xrange

def solve():
    table = []
    for _ in range(9):
        table.append(stdin.readline().split())
    
    check_table = []
    for _ in range(9):
        check_table.append([False] * 9)
    
    # horizontal check
    for i in range(9):
        a = []
        for j in range(9):
            a.append(table[i][j])
        for j in range(9):
            n = table[i][j]
            if a.count(n) > 1:
                check_table[i][j] = True
    
    # vertical check
    for j in range(9):
        a = []
        for i in range(9):
            a.append(table[i][j])
        for i in range(9):
            n = table[i][j]
            if a.count(n) > 1:
                check_table[i][j] = True
    
    # 9x9 check
    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            a = []
            for di in range(3):
                for dj in range(3):
                    a.append(table[i + di][j + dj])
            for di in range(3):
                for dj in range(3):
                    n = table[i + di][j + dj]
                    if a.count(n) > 1:
                        check_table[i + di][j + dj] = True
    
    for i in range(9):
        for j in range(9):
            if check_table[i][j]:
                stdout.write('*')
            else:
                stdout.write(' ')
            stdout.write(table[i][j])
        stdout.write('\n')
    stdout.write('\n')

if __name__ == '__main__':
    N = int(stdin.readline())
    for _ in range(N):
        solve()