노노그램 풀이 알고리즘 찾기

0. 노노그램을 풀이 하는 방법을 아무리 생각해봐도 어렵고 답이 안나오는 거 같다.
 
1. 내가 노노그램을 보면 처음으로 하는 건 큰 수를 의심해보고 가능한 칸을 채우는 것이다.

for(int i = 0; i < n; i++) {
        for(int j = 0; j < n/2; j++) {
            if(row[i][j] != 0) {
                rowNum[i] += row[i][j];
                rowNum[i] ++;
            }
            if(col[i][j] != 0) {
                colNum[i] += col[i][j];
                colNum[i] ++;
            }
        }
        rowNum[i] --;
        colNum[i] --;
    }

다음과 같이 for문을 사용해서 네모를 칠하는 개수와 빈칸의 개수의 합을 구한다.
여기서 한 면의 네모수와 같은 값이 나오면 그 줄은 칠할 수 있다.
그런데, 여기까지는 생각하고 구현할 수 있었지만 그 다음이 어려웠다. 아무래도 항상 칠해지는 것이 일정하지 않아 경우의 수가 너무 많아 지는 것이었다.
 
2. 격자무늬 네모들을 보면 당연히 생각나는 좌표로 접근해 보았다.
좌표로 접근할 때에는 미지수가 필요하다. 
앞 게시물의 하트를 예로 들면 (순서는 항상 0부터 시작한다고 하고 좌표를 (행,열)로 표현한다고 하자.)
0행 (0,p), (0,p+2+q)
1행 (1, r), (1, r+1), (1, r+2), (1, r+3), (1, r+4)  
2행 (2, s), (2, s+1), (2, s+2), (2, s+3), (2, s+4) 
3행 (3, t), (3, t+1), (3, t+2), (3, t+3), (3, t+4)
4행 (4, u)
0열 (v,0), (v+1, 0), (v+2, 0)
1열 (w,1), (w+1, 1), (w+2, 1), (w+3, 1)
2열 (x,2), (x+1, 2), (x+2, 2), (x+3, 2)
3열 (y,3), (y+1, 3), (y+2, 3), (y+3, 3)
4열 (z,4), (z+1, 4), (z+2, 4)
 
1.에 의거하여 r=s=t=0 이다.
1행 -> (1, 0), (1, 1), (1, 2), (1, 3), (1, 4)
2행 -> (2, 0), (2, 1), (2, 2), (2, 3), (2, 4)
3행 ->  (3, 0), (3, 1), (3, 2), (3, 3), (3, 4)
 
v = 1, z = 1이다.
0열 -> (1,0), (2, 0), (3, 0)
4열 -> (1,4), (2, 4), (3, 4)
빈칸 확정 -> (0,0), (0,4), (4,0),(4,4)
 
w>=1 && w+3<=3, x>=1 && x+3<=3, y>=1 && y+3<=3이므로, w=0||w=1, x=0||x=1, y=1||y=0
p=1||p=2||p=3이다.
모든 좌표의 범위는 4이하이므로 p+2+q <= 4, p+q<=2이다. 따라서 p=1||p=2이다.
(0,4)는 빈칸 확정이므로 p+2+q != 0 && p+2+q != 4이다. 따라서 p=1이다.
0행 -> (0,1), (0,3)
빈칸 확정 -> (4,1),(4,3)
 
빈칸확정이 되어서 나머지 (4,2)만 칠 할수 있다.
4행 -> (4,2)