* 출제의도

  출제자가 평소에 자주 즐기는 퍼즐입니다 ㅇ<-<

  * 문제풀이

  이번에 입력으로 주어진 데이터들은 모두 'Trial and Error' 를 거치지 않고서도 풀 수 있는 데이터였습니다. (라고 책에 나와있습니다) 그런데 생각하고 있는 알고리즘을 모두 구현하기가 쉽지 않아서 결국은 Trial-and-Error로 풀게 되었지요 :<

  하지만 모든 경우에 대해서 무작정 Back-Tracking 기법을 사용하는것보다는 확실히 정해진 일부 칸들을 먼저 구합니다. 예를 들어 두 칸이 비어있는데 합이 16인 경우라면 (7, 9) 이외의 숫자는 해당 칸에 사용할 수가 없는 식으로요. 이런식으로 어떤 칸에 사용할 수 없는 숫자들을 테이블로 미리 구해둔다면 꽤나 많은 경우의 수가 단축됩니다.

  저는 우선 이정도의 처리만 했는데요, 좀 더 다양한 알고리즘이 존재하니 도전해 보시면 좋을 듯 합니다 :D

  * 소스코드
#include <cstdio> #include <vector> using namespace std; struct elem {    int x, y, rc, sum; }; struct BACKUP_STATE {    int _allow[30][30];    vector <vector <int> > _table; }; bool found; int allow[30][30]; vector <int> allcase[46][10]; int bit[46][10]; vector <pair<int, int> > state[30][30]; vector <vector <int> > table; vector <elem> data; vector <int> conn[30][30]; // 현재 좌표에 영향을 미치는 data의 index vector <BACKUP_STATE> btable; int dx[4] = {0, 1, -1, 0}; int dy[4] = {1, 0, 0, -1}; int N, M; FILE *in = stdin; void backup() {    BACKUP_STATE tmp;    for (int i = 0; i <= N; ++i)       for (int j = 0; j <= N; ++j)          tmp._allow[i][j] = allow[i][j];    tmp._table = table;    btable.push_back(tmp); } void load() {    BACKUP_STATE tmp = btable[btable.size() - 1];    for (int i = 0; i <= N; ++i)       for (int j = 0; j <= N; ++j)          allow[i][j] = tmp._allow[i][j];    table = tmp._table; } void recover() {    BACKUP_STATE tmp = btable[btable.size() - 1];    for (int i = 0; i <= N; ++i)       for (int j = 0; j <= N; ++j)          allow[i][j] = tmp._allow[i][j];    table = tmp._table;    btable.pop_back(); } void init() {    for (int i = 1; i < (1 << 9); ++i)    {       vector <int> tmp;       int sum = 0;       int cn = 0;       for (int j = 0; j < 9; ++j)          if (i & (1 << j))          {             sum += (j + 1);             cn++;          }       allcase[sum][cn].push_back(i);       bit[sum][cn] |= i;    } } void input() {    fscanf(in, "%d", &N);    table.assign(N + 1, vector <int> (N + 1, -1));    memset(allow, 0, sizeof(allow));    for (int i = 0; i < N; ++i)       for (int j = 0; j < N; ++j)       {          fscanf(in, "%d", &table[i][j]);          if (table[i][j] == 1) allow[i][j] = (1 << 9) - 1;          table[i][j]--;          conn[i][j].clear();       }    fscanf(in, "%d", &M);    data.resize(M);    for (int i = 0; i < M; ++i)    {       fscanf(in, "%d %d %d %d", &data[i].x, &data[i].y, &data[i].rc, &data[i].sum);       data[i].x--;       data[i].y--;    } } int GetCount(int x, int y, int rc, int &must, int &mustnot) {    int ret = 0;    for (;;)    {       x += dx[rc];       y += dy[rc];       if (table[x][y] != -1)       {          ret++;          if (table[x][y] != 0)          {             must |= (1 << (table[x][y] - 1));             mustnot |= (1 << (table[x][y] - 1));          }       }       else       {          break;       }    }    return ret; } int go(int sum, int remain, int must, int mustnot) {    int ret = bit[sum][remain] - mustnot;    int bitmask = 0;    for (int i = 0; i < allcase[sum][remain].size(); ++i)    {         if ((must & allcase[sum][remain][i]) == must)       {          bitmask |= allcase[sum][remain][i];       }    }    return ret & bitmask; } void greedy1() {    for (int i = 0; i < M; ++i)    {       int x = data[i].x, y = data[i].y;       int rc = data[i].rc, sum = data[i].sum;       int must = 0, mustnot = 0;       int gc = GetCount(x, y, rc, must, mustnot);       for (;;)       {          x += dx[rc], y += dy[rc];          if (table[x][y] == -1) break;          allow[x][y] &= go(sum, gc, must, mustnot);       }    } } bool isFinish() {    for (int i = 0; i < N; ++i)       for (int j = 0; j < N; ++j)          if (table[i][j] == 0) return false;    return true; } bool find(int x, int y, int v) {    v++;    for (int i = 0; i < 4; ++i)    {       int xx = x, yy = y;       for (;;)       {          xx += dx[i], yy += dy[i];          if (table[xx][yy] == -1) break;          if (table[xx][yy] == v) return true;       }    }    return false; } bool set() {    bool ret = false;    for (int i = 0; i < N; ++i)    {       for (int j = 0; j < N; ++j)       {          if (table[i][j] == 0)          {             if ((allow[i][j] & (allow[i][j] - 1)) == 0)             {                for (int k = 0; k < 9; ++k)                   if (allow[i][j] & (1 << k))                   {                      if (!find(i, j, k))                      {                         table[i][j] = k + 1;                         ret = true;                      }                   }             }          }       }    }    return ret; } void backtr(int x, int y) {    if (found) return;    while (!isFinish())    {       greedy1();       if (!set()) break;    }    if (isFinish())    {       for (int i = 0; i < N; ++i) {          for (int j = 0; j < N; ++j) {             printf("%d", max(table[i][j], 0));             if (j != N - 1) printf(" ");          }          printf("\n");       }       found = true;       return;    }    backup();    for (;;)    {       y++;       if (y == N) { y = 0, x++; }       if (table[x][y] == 0) break;    }    for (int i = 0; i < 9; ++i)    {       if ((allow[x][y] & (1 << i)) != 0)       {          table[x][y] = i + 1;          backtr(x, y);          table[x][y] = 0;          load();       }    }    recover(); } int main() {    init();    int T;    fscanf(in, "%d", &T);    while (T--)    {       btable.clear();       input();       found = false;       backtr(0, 0);      } }