2239 스도쿠

전에 마천루 문제 푼 적 있어서 음~~ 쏘 이지~~ 하면서 풀려고 했는데..

ㅋㅋㅋ ㅜㅜ ㅁㅁㅋㅋ 막혔음

푸는 건 N퀸이랑 비슷하다. 백트레킹 사용해서 하나 둬 보고 맞는지 확인하고 두고 쭉쭉 하면 풀리는데..! 막혔다.

정확히는 어디서 막혔냐면 0인 부분만 둬야 하는데 0에 1을 두는 순간 이걸 빈칸으로 인지를 못하고 넘어간다. 

 

블로그 적으면서 생각 났는데 그냥 장애물 배열 하나 더 두는 게 좋을 것 같다. 의지가 있으면 오늘 하고 아니면 내일 해야지. 요즘 기력이 없어서 걱정임. 항상 밖에서 공부하거나 아니면 친구랑 공부하거나 하는데 코로나 때문에 아무것도 못하고 혼자 집에만 있음; 내일은 행아웃으로 사이버 인기척이라도 느껴야지. 

 

---

 

#include <iostream>
#include <vector>

using namespace std;
vector <vector<int>> ans(9, vector <int> (9));

void    print_ans()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            printf("%d", ans[i][j]);
        }
        printf("\n");
    }
}

bool    row_check(int i, int j)
{
    vector<int> tmp (9, 0);

    for (int k = 0; k < 9; k++)
    {
        tmp[ans[i][k] - 1]++;
    }
    for (int k = 0; k < 9; k++)
    {
        if (tmp[k] != 1)
            return (false);
    }
    return (true);
}

bool    col_check(int i, int j)
{
    vector<int> tmp (9, 0);

    for (int k = 0; k < j; k++)
    {
        tmp[ans[k][j] - 1]++;
    }
    for (int k = 0; k < j; k++)
    {
        if (tmp[k] != 1)
            return (false);
    }
    return (true);
}

bool    box_check(int i, int j)
{
    vector<int> tmp (9, 0);
    
    for (int k = i - 2; k < i; k++)
    {
        for (int m = j - 2; m < j; m++)
            tmp[ans[k][m] - 1]++;
    }
    for (int k = 0; k < 9; k++)
    {
        if (tmp[k] != 1)
            return (false);
    }
    return (true);
}

bool    check(int i, int j)
{
    if(!col_check(i, j))
        return (false);
    if (j == 8)
    {
        if (!row_check(i, j))
            return (false);
    }
    if (i % 3 == 2 && j % 3 == 2)
    {
        if(box_check(i, j))
            return (false);
    }
    return (true);
}

bool    sudoku(int i, int j)
{
    printf("%d %d\n", i, j);
    print_ans();
    printf("\n");
	if (i == 9)
		return (true);
	else
	{
	    if (ans[i][j] == 0)
	    {
    		for (int k = 1; k <= 9; )
    		{
    			ans[i][j] = k++;
    			if (!check(i, j))
    				continue;
    			
    			int result;
    			if (j == 8)
    			    result = sudoku(i + 1, 0);
    			else
    			    result = sudoku(i, j + 1);
    			if (result)
    				return (true);
    		}
	    }
	    else
	    {
	        if (!check(i, j))
    			return (false);
    				
	        int result;
			if (j == 8)
			    result = sudoku(i + 1, 0);
			else
			    result = sudoku(i, j + 1);
		    if (result)
				return (true);
	    }
	}
	return (false);
}

int     main()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            scanf("%1d ", &ans[i][j]);
        }
    }
    if (sudoku(0, 0))
        print_ans();
    else
        printf("no ans\n");
    return (0);
}

---

#include <iostream>
#include <vector>

using namespace std;
vector <vector<int>> ans(9, vector <int> (9));
vector <vector<int>> map(9, vector <int> (9));

void    print_ans()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            printf("%d", ans[i][j]);
        }
        printf("\n");
    }
}

bool    row_check(int i, int j)
{
    vector<int> tmp (9, 0);

    for (int k = 0; k < 9; k++)
    {
        tmp[ans[i][k] - 1]++;
    }
    for (int k = 0; k < 9; k++)
    {
        if (tmp[k] != 1)
            return (false);
    }
    return (true);
}

bool    col_check(int i, int j)
{
    cout << "col_index " << i << " " << j << endl;
    print_ans();
    printf("\n");
    vector<int> tmp (9, 0);

    for (int k = 0; k <= j; k++)
    {
        tmp[ans[k][j] - 1]++;
    }
    for (int k = 0; k <= j; k++)
    {
        if (tmp[k] != 1)
            return (false);
    }
    return (true);
}

bool    box_check(int i, int j)
{
    vector<int> tmp (9, 0);
    
    for (int k = i - 2; k < i; k++)
    {
        for (int m = j - 2; m < j; m++)
            tmp[ans[k][m] - 1]++;
    }
    for (int k = 0; k < 9; k++)
    {
        if (tmp[k] != 1)
            return (false);
    }
    return (true);
}

bool    check(int i, int j)
{
    if(!col_check(i, j))
        return (false);
    if (j == 8)
    {
        if (!row_check(i, j))
            return (false);
    }
    if (i % 3 == 2 && j % 3 == 2)
    {
        if(box_check(i, j))
            return (false);
    }
    return (true);
}

bool    sudoku(int i, int j)
{
    printf("%d %d\n", i, j);
    print_ans();
    printf("\n");
	if (i == 9)
		return (true);
	else
	{
	    if (map[i][j] == 0)
	    {
    		for (int k = 1; k <= 9; )
    		{
    			ans[i][j] = k++;
    			if (!check(i, j))
    				continue;
    			int result;
    			if (j == 8)
    			    result = sudoku(i + 1, 0);
    			else
    			    result = sudoku(i, j + 1);
    			if (result)
    				return (true);
    		}
	    }
	    else
	    {
	        int result;
			if (j == 8)
			    result = sudoku(i + 1, 0);
			else
			    result = sudoku(i, j + 1);
		    if (result)
				return (true);
	    }
	}
	return (false);
}

int     main()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            scanf("%1d ", &ans[i][j]);
            map[i][j] = ans[i][j];
        }
    }
    print_ans();
    printf("\n");
    if (sudoku(0, 0))
        print_ans();
    else
        printf("no ans\n");
    return (0);
}

음...

체크하는 부분에서 문제 있는 듯

0일 때는 체크 함수 호출 안 하는데 호출해서 인덱스 에러 뜬 건가?? 나머지는 내일로