[알고리즘] 스도쿠

구현 방식

• 백트래킹 알고리즘 적용
• 원래는 자리마다 올 set = {1,2,3,4,5,6,7,8,9} 를 만들고, 오지 못하는 수를 행, 렬 , 3x3 큐브에 걸쳐서 추려내면서 진행했다.
• 그랬더니 자리마다 연산을 하므로 (9 x 9 x 27) x … x (9 x 9 x 27) 총 빈자리 수만큼 해버리게 되어 시간 초과가 발생했다.
• 그래서 아래와 같이 코드를 고쳤다.
  • 빈자리의 위치 벡터를 받아낸다.
  • 빈자리 일 때만 0 - 9 중 올 수 있는 숫자를 체크하고, 넘겨준다.
    • 3x3 큐브 자리를 탐색하는 방법은 아래와 같다.
      • 먼저 3x3 큐브 자리는 총 9 개 인데, 가장 처음 시작하는 인덱스 번호들을 CubeStartrPos 에 저장한다.
      • CubeStartrPos 벡터를 처음부터 돌면서, +SIZE 까지 해봤을 때 현재 위치보다 처음으로 작은 값을 반환한다.

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

class SudokuSolver
{
	const static int SIZE = 3;
	const static int LENGTH = SIZE * SIZE;
	int board[LENGTH][LENGTH] = {};

	vector<pair<int, int>> emptyList;

	bool bFinished = false;

	int CubeStartrPos[LENGTH] = { 0, SIZE, SIZE * 2,
								  LENGTH * SIZE , LENGTH * SIZE + SIZE, LENGTH * SIZE + SIZE * 2,
								  LENGTH * 2 * SIZE * SIZE, LENGTH * 2 * SIZE + SIZE, LENGTH * 2 * SIZE + SIZE * 2 };

public:
	void Input()
	{
		for (int i = 0; i < LENGTH; i++)
		{
			for (int j = 0; j < LENGTH; j++)
			{
				cin >> board[i][j];
				if (board[i][j] == 0)
				{
					emptyList.push_back({ i,j });
				}

			}
		}
	}


	void Solve()
	{
		backtrk(0);
	}

	void Print()
	{
		for (int i = 0; i < LENGTH; i++)
		{
			for (int j = 0; j < LENGTH; j++)
			{
				cout << board[i][j] << " ";
			}
			cout << "\n";
		}

	}

private:
	void backtrk(int curr)
	{
		if (emptyList.size() <= curr)
		{
			Print();
			bFinished = true;
		}

		if (bFinished)
			return;

		pair<int, int>& target = emptyList[curr];
		for (int i = 1; i <= LENGTH; i++)
		{
			if (CanFill(target, i))
			{
				board[target.first][target.second] = i;
				backtrk(curr + 1);
			}
		}

		board[target.first][target.second] = 0;

	}

	bool CanFill(pair<int,int>& pos, int K)
	{
		if (!CanFillRowColumn(pos, K))
		{
			return false;
		}
		if (!CanFillCube(pos, K))
		{
			return false;
		}

		return true;
	}

	bool CanFillRowColumn(pair<int, int>& pos, int K)
	{
		int y = pos.first;
		int x = pos.second;

		for (int i = 0; i < LENGTH; i++)
		{
			if (board[y][i] == K)
			{
				return false;
			}
			if (board[i][x] == K)
			{
				return false;
			}
		}

		return true;
	}

	bool CanFillCube(pair<int, int>& pos, int K)
	{
		int cube_start_pos = GetCubeStartrPos(pos);

		int start_y, start_x, y, x;

		start_x = cube_start_pos % LENGTH;
		start_y = cube_start_pos / LENGTH;

		for (int y = start_y; y < start_y + SIZE; y++)
		{
			for (int x = start_x; x < start_x + SIZE; x++)
			{
				if (board[y][x] == K)
				{
					return false;
				}
			}
		}

		return true;
	}

	int GetCubeStartrPos(pair<int,int>& pos)
	{
		int pos_y, pos_x, start_y, start_x;
		pos_y = pos.first;
		pos_x = pos.second;
		for (auto start_pos : CubeStartrPos)
		{
			start_x = start_pos % LENGTH;
			start_y = start_pos / LENGTH;
			if (pos_y < start_y + SIZE && pos_x < start_x + SIZE)
			{
				return start_pos;
			}
		}
		return -1; // error;
	}


};

int main() {

	SudokuSolver ss;
	ss.Input();
	ss.Solve();

	return 0;
}