# 數獨程式破解！！！
最近看到好多人在玩數獨遊戲，玩到腦袋要爆炸啦$!$ :exploding_head:
乾脆用程式寫一個吧$!$

#### ==失敗版==

#include<bits/stdc++.h>
using namespace std ;
#define speed_up ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define pb(a) push_back(a)
#define pii pair<int , int>
#define F first
#define S second
int arr[10][10] , test[10][10] , Num ;
bool usedx[10][10] , usedy[10][10] , usedmid[10][10] , used[10] ;
vector<int> lost ;

void init(){
	memset(used , 0 , sizeof(used)) ;
}

void copy(){
	for(int i = 1 ; i <= 9 ; i++)
		for(int j = 1 ; j <= 9 ; j++)
			test[i][j] = arr[i][j] ;
}

int turn(int i , int j){
	if(i <= 3 && j <= 3) return 1 ;
    else if(i <= 3 && j <= 6) return 2 ;
    else if(i <= 3 && j <= 9) return 3 ;
    else if(i <= 6 && j <= 3) return 4 ;
    else if(i <= 6 && j <= 6) return 5 ;
    else if(i <= 6 && j <= 9) return 6 ;
    else if(i <= 9 && j <= 3) return 7 ;
    else if(i <= 9 && j <= 6) return 8 ;
    else return 9 ;
}

pii turn_back(int num){
	if(num == 1) return {2 , 2} ;
	else if(num == 2) return {2 , 5} ;
	else if(num == 3) return {2 , 8} ;
	else if(num == 4) return {5 , 2} ;
	else if(num == 5) return {5 , 5} ;
	else if(num == 6) return {5 , 8} ;
	else if(num == 7) return {8 , 2} ;
	else if(num == 8) return {8 , 5} ;
	else return {8 , 8} ;
}

void expend(int num){
	for(int i = 1 ; i <= 9 ; i++)
		for(int j = 1 ; j <= 9 ; j++)
			if(arr[i][j] == num){
				for(int k = 1 ; k <= 9 ; k++)
					test[i][k] = test[k][j] = num ;
			}
}


void add(int x , int y , int val){
	usedx[x][val] = 1 ;
	usedy[y][val] = 1 ;
	usedmid[turn(x , y)][val] = 1 ;
}


void ck(int num , int val){
	pii pos = turn_back(num) ;
	int x = pos.F , y = pos.S , c = 0 ;
	for(int i = x - 1 ; i <= x + 1 ; i++)
		for(int j = y - 1 ; j <= y + 1 ; j++)
			if(!test[i][j]) c++ ;
	if(c == 1){
		for(int i = x - 1 ; i <= x + 1 ; i++)
			for(int j = y - 1 ; j <= y + 1 ; j++)
				if(!test[i][j]){
					arr[i][j] = val ;
					Num++ ;
					add(i , j , val) ;
				} 
	}
}

int cc(int x , int y){
	init() ;
	int c = 0 ;
	for(int i = 1 ; i <= 9 ; i++)
		if(usedx[x][i] || usedy[y][i] || usedmid[turn(x , y)][i]) used[i] = 1 ;
	for(int i = 1 ; i <= 9 ; i++)
		if(used[i]) c++ ;
	if(c == 8){
		for(int i = 1 ; i <= 9 ; i++)
			if(!used[i]) return i ;
	}
	return 0 ;
}

void full_in(){
	for(int k = 1 ; k <= 9 ; k++){
		for(int i = 1 ; i <= 9 ; i++)
			if(!usedmid[k][i]) lost.pb(i) ;
		for(int &it : lost){
			copy() ;
			expend(it) ;
			ck(k , it) ;
		}
		lost.clear() ;
	}
}

void print(){
	for(int i = 1 ; i <= 9 ; i++){
		for(int j = 1 ; j <= 9 ; j++){
			cout<<arr[i][j]<<" " ;
		}
		cout<<'\n' ;
	}
}

int main(){
	speed_up ;
    string input ;
    for(int i = 1 ; i <= 9 ; i++){
        for(int j = 1 ; j <= 9 ; j++){
            cin >> input ;
            if(input == ".") continue ;
            arr[i][j] = stoi(input) ;
            usedx[i][arr[i][j]] = 1 ;
            usedy[j][arr[i][j]] = 1 ;
            usedmid[turn(i , j)][arr[i][j]] = 1 ;
            Num++ ;
        }
    }
	int c , pre = Num ;
    while(Num < 81){
    	full_in() ;
    	for(int i = 1 ; i <= 9 ; i++){
	    	for(int j = 1 ; j <= 9 ; j++){
	    		if(arr[i][j]) continue ;
	    		c = cc(i , j) ;
	    		if(c){
	    			arr[i][j] = c ;
		    		add(i , j , c) ; 
		    		Num++ ;
	    		}
	    	}
    	}
    	if(Num == pre) break ;
    	pre = Num ;
    }
    print() ;
}

竟然我剛開始沒有想到遞迴$!!!$ :cry:

#### ==成功版==

#include<bits/stdc++.h>
using namespace std ; 
#define speed_up ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define pii pair<int , int>
#define F first
#define S second
int arr[15][15] , success ;

int turn(int x , int y){
	if(x <= 3 && y <= 3) return 1 ;
	if(x <= 3 && y <= 6) return 2 ;
	if(x <= 3 && y <= 9) return 3 ;
	if(x <= 6 && y <= 3) return 4 ;
	if(x <= 6 && y <= 6) return 5 ;
	if(x <= 6 && y <= 9) return 6 ;
	if(x <= 9 && y <= 3) return 7 ;
	if(x <= 9 && y <= 6) return 8 ;
	return 9 ;
}

pii turn_back(int num){
	if(num == 1) return {2 , 2} ;
	else if(num == 2) return {2 , 5} ;
	else if(num == 3) return {2 , 8} ;
	else if(num == 4) return {5 , 2} ;
	else if(num == 5) return {5 , 5} ;
	else if(num == 6) return {5 , 8} ;
	else if(num == 7) return {8 , 2} ;
	else if(num == 8) return {8 , 5} ;
	else return {8 , 8} ;
}

void print(){
	for(int i = 1 ; i <= 9 ; i++){
		for(int j = 1 ; j <= 9 ; j++){
			cout<<arr[i][j]<<' ' ;
		}
		cout<<'\n' ;
	}
}

bool check(int x , int y , int val){
    for(int i = 1 ; i <= 9 ; i++)
        if(arr[x][i] == val) return 0 ;
    for(int i = 1 ; i <= 9 ; i++)
        if(arr[i][y] == val) return 0 ;
    int pos = turn(x , y) , tx = turn_back(pos).F , ty = turn_back(pos).S ;
    for(int i = tx - 1 ; i <= tx + 1 ; i++){
        for(int j = ty - 1 ; j <= ty + 1 ; j++){
            if(arr[i][j] == val) return 0 ;
        }
    }
    return 1 ;
}

void sol(int x , int y){
	if(success) return ;
	if(arr[x][y]){
            if(y < 9) sol(x , y + 1) ;
            else{
                if(x == 9){
                    print() ;
                    success = 1 ;
                    return ;
                }else sol(x + 1 , 1) ;
            }
	}else{
	    for(int i = 1 ; i <= 9 ; i++)
        	if(check(x , y , i)){
                    arr[x][y] = i ;
                    if(y < 9) sol(x , y + 1) ;
                    else{
                        if(x == 9){
                            print() ;
                            success = 1 ;
                            return ;
                        }else sol(x + 1 , 1) ;
                    }
                    if(success) return ;
    		}
        arr[x][y] = 0 ;
	}
}

int main(){
	speed_up ;
	for(int i = 1 ; i <= 9 ; i++)
		for(int j = 1 ; j <= 9 ; j++)
			cin >> arr[i][j] ; // 空白輸入 0
	sol(1 , 1) ;
}

### 題目
___[Toi 2006 第三題](https://tioj.ck.tp.edu.tw/problems/1235)___ :star: :star::star:

### 解法

#include<bits/stdc++.h>
using namespace std ;
#define fastio ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define pb push_back
#define pii pair<int , int>
#define F first
#define S second
char turn[10] = {'*' , 'R' , 'O' , 'Y' , 'G' , 'B' , 'I' , 'P' , 'L' , 'W'} ; 
int arr[10][10] ;
vector<pii> v ;
bool finish = false ;

pii turn_mid(int x , int y){
    if(x <= 3 && y <= 3) return {2 , 2} ;
    if(x <= 3 && y <= 6) return {2 , 5} ;
    if(x <= 3 && y <= 9) return {2 , 8} ;
    if(x <= 6 && y <= 3) return {5 , 2} ;
    if(x <= 6 && y <= 6) return {5 , 5} ;
    if(x <= 6 && y <= 9) return {5 , 8} ;
    if(x <= 9 && y <= 3) return {8 , 2} ;
    if(x <= 9 && y <= 6) return {8 , 5} ;
    return {8 , 8} ;
}

bool check(int x , int y , int num){
    for(int i = 1 ; i <= 9 ; i++)
        if(arr[x][i] == num) return false ; // check row
    for(int i = 1 ; i <= 9 ; i++)
        if(arr[i][y] == num) return false ; // check col
    int new_x = turn_mid(x , y).F , new_y = turn_mid(x , y).S ;
    for(int i = new_x - 1 ; i <= new_x + 1 ; i++)
        for(int j = new_y - 1 ; j <= new_y + 1 ; j++)
            if(arr[i][j] == num) return false ;
    return true ;
}

void sol(int x , int y){
    if(x == 10){
        finish = true ;
        return ;
    }
    if(arr[x][y]){
        if(y == 9) sol(x + 1 , 1) ;
        else sol(x , y + 1) ;
    }
    else{
        for(int i = 1 ; i <= 9 ; i++){
            if(check(x , y , i)){
                arr[x][y] = i ;
                if(y == 9) sol(x + 1 , 1) ;
                else sol(x , y + 1) ;
            }
            if(finish) return ;
        }
        arr[x][y] = 0 ; // important
    }
    
}

int main(){
    fastio ;
    char input ;
    v.pb({1 , 0}) ;
    // input
    for(int i = 1 ; i <= 9 ; i++){
        for(int j = 1 ; j <= 9 ; j++){
            cin >> input ;
            // * is 0
            for(int k = 0 ; k <= 9 ; k++)
                if(turn[k] == input){
                    if(k == 0) v.pb({i , j}) ; // record the question
                    arr[i][j] = k ;
                    break ;
                }
        }
    }
    sol(1 , 1) ;
    for(int i = 1 ; i < v.size() ; i++){
        if(v[i].F > v[i - 1].F)
            for(int j = 0 ; j < v[i].F - v[i - 1].F ; j++) cout<<'\n' ; // 格式化輸出
        cout<<turn[arr[v[i].F][v[i].S]] ;
    }
}

現在我無敵啦$!!!$ :thumbsup::thumbsup::thumbsup:
###### tags: `solo learn`