---
# System prepended metadata

title: sudoku
tags: [week8, dfs, back-tracking]

---

# sudoku
###### tags: `week8` `back-tracking` `dfs`

## Solution 1
> [name=子恩]
```python=
k = int(input())
n = k**2
l = list(map(int,input().split()))
sudoku = [l[i:i+n] for i in range(0,len(l),n)]
areas = [[(i+x,j+y) for x in range(k) for y in range(k)] for i in range(0,n,k) for j in range(0,n,k)]

def test(x,y,t):    # 確認在x,y的位置能不能填進數字t
    for j in range(n):    # 檢查橫行
        if sudoku[x][j] == t:return False
    for i in range(n):    # 檢查直列
        if sudoku[i][y] == t:return False
    for area in areas:    # 檢查區域
        if (x,y) not in area:continue    # 找出x,y所在的區域
        for (i,j) in area:               # 如果區域中已經有數字t回傳False
            if sudoku[i][j] == t:return False
    return True

def solve(a=0):    # a = 要填入的格子
    global sudoku
    i = a//n ;j = a%n    # 把a換算成sudoku座標
    if sudoku[i][j] !=0:    # 如果這格已經填上數字
        if a+1 == k**4:return True    # 如果已經到最後一格，且這格已經填上數字，整個數獨都正確
        if solve(a+1):return True     # 如果如果之後的格子都正確，這格也正確
        return False                  # 否則就是錯的
    for x in range(1,n+1):    #將數字輪流帶入
        if not test(i,j,x):continue
        sudoku[i][j] = x                # 可以填就填
        if a+1 == k**4:return True      # 如果已經到最後一格，且這格可以填入x，整個數獨都正確
        if solve(a+1):return True       # 如果之後的格子都正確，這格也正確
        sudoku[i][j] = 0                # 有錯就復原，試下一個數字
    return False    #所有數字都不能填，這格是錯的

'''
不能解無解的數獨
如果不只一個解，這只能找到一個解
'''

solve()

# 想看數獨的結果就執行這行
# for u in sudoku:print(u)

for u in sudoku:
  for i in u:print(i ,end = ' ')
```
### Solution 2
> [name=Jason Lin]
#### Main Idea:
- I use three dicts of sets: *vertical*, *horizontal*, and *block* to keep numbers that have been used
- The 2-dimensional list *puzzle* stores the status quo
- Every time calling *solve()*, we give a number(if possible) to a unfilled small block

```python=
def solve(board):
    for i in range(k**2):
        for j in range(k**2):
            if board[i][j]: continue
            for n in range(1,k**2+1):
                if n in horizontal[i]: continue
                if n in vertical[j]: continue
                if n in block[(i//k,j//k)]: continue
                
                board[i][j] = n
                horizontal[i].add(n)
                vertical[j].add(n)
                block[(i//k,j//k)].add(n)
                
                if solve(board):
                    return True
                
                board[i][j] = 0
                horizontal[i].remove(n)
                vertical[j].remove(n)
                block[(i//k,j//k)].remove(n)
            return False
    return True
#pre-process
k = eval(input())
inp = list(map(int,input().split()))
puzzle = [[j for j in inp[i:i+k**2]] for i in range(0,len(inp),k**2)]
#init
block = {(i,j):set() for i in range(k) for j in range(k)}
vertical = {i:set() for i in range(k**2)}
horizontal = {i:set() for i in range(k**2)}
for i in range(k**2):
    for j in range(k**2):
        n = puzzle[i][j]
        if not n: continue
        block[(i//k,j//k)].add(n)
        vertical[j].add(n)
        horizontal[i].add(n)
#solve and print
solve(puzzle)
print(*[j for i in puzzle for j in i])
```