2580번 스도쿠

단계별로 풀어보기 - 백트래킹- 6단계

https://www.acmicpc.net/problem/2580

#include <iostream>
using namespace std;
int board[10][10];
bool col[10][10],row[10][10],rect[10][10];
void dfs(int key)
{
    int x=key/9;
	int y=key%9;

    if(key==81)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                cout<<board[i][j]<<" ";
            }
            cout<<"\n";
        }
        exit(0);
    }
    
	if(board[x][y]==0)		
    {
        for(int i=1;i<=9;i++)
        {
            if(col[x][i]==false&&row[y][i]==false &&rect[(x/3)*3+(y/3)][i]==false)
            {  
				board[x][y]=i;
                col[x][i]=true;
				row[y][i]=true;
				rect[(x/3)*3+(y/3)][i]=true;				
                
				dfs(key+1);
                
				board[x][y]=0;
				col[x][i]=false;
				row[y][i]=false;
				rect[(x/3)*3+(y/3)][i]=false;
            }
        }
	}
    
    else
    {
        dfs(key+1);
    }
	
}


int main(void){
	
	for(int i=0;i<9;i++)
    {
		for(int j=0;j<9;j++)
        {
			cin>>board[i][j];
			if(board[i][j]!=0){
				col[i][board[i][j]]=true; 
				row[j][board[i][j]]=true;
				rect[(i/3)*3+(j/3)][board[i][j]]=true;
			}
		}
	}
	
	dfs(0);	
    return 0;
}