4574 스도미노쿠 ( 자바스크립트 )

문제

스도쿠가 세계적으로 유행이 된 이후에, 비슷한 퍼즐이 매우 많이 나왔다. 게임 매거진 2009년 7월호에는 스도쿠와 도미노를 혼합한 게임인 스도미노쿠가 소개되었다. 

이 퍼즐은 스도쿠 규칙을 따른다. 스도쿠는 9×9 크기의 그리드를 1부터 9까지 숫자를 이용해서 채워야 한다. 스도쿠는 다음과 같은 조건을 만족하게 숫자를 채워야 한다.

• 각 행에는 1부터 9까지 숫자가 하나씩 있어야 한다.
• 각 열에는 1부터 9까지 숫자가 하나씩 있어야 한다.
• 3×3크기의 정사각형에는 1부터 9가지 숫자가 하나씩 있어야 한다.

스도미노쿠의 그리드에는 1부터 9까지 숫자가 쓰여져 있고, 나머지 72칸은 도미노 타일 36개로 채워야 한다. 도미노 타일은 1부터 9까지 서로 다른 숫자의 가능한 쌍이 모두 포함되어 있다. (1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ...) 1+2와 2+1은 같은 타일이기 때문에, 따로 구분하지 않는다. 도미노 타일은 회전 시킬 수 있다. 또, 3×3 크기의 정사각형의 경계에 걸쳐서 놓여질 수도 있다.

왼쪽 그림은 퍼즐의 초기 상태를 나타내고, 오른쪽은 퍼즐을 푼 상태이다.

 

스도미노쿠의 퍼즐의 초기 상태가 주어졌을 때, 퍼즐을 푸는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 주어진다. U는 도미노에 쓰여 있는 한 숫자이고, LU는 길이가 2인 문자열로 U의 위치를 나타낸다. V와 LV는 도미노에 쓰여 있는 다른 숫자를 나타낸다. 도미노의 위치는 문제에 나와있는 그림을 참고한다. 입력으로 주어지는 도미노의 각 숫자 위치는 항상 인접해 있다.

N개의 도미노의 정보가 주어진 다음 줄에는 채워져 있는 숫자의 위치가 1부터 9까지 차례대로 주어진다. 위치는 도미노의 위치를 나타낸 방법과 같은 방법으로 주어진다.

모든 도미노와 숫자가 겹치는 경우는 없다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 퍼즐에 대해서, 스도쿠를 푼 결과를 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

====

문제 분석

이전에 풀었던 스도쿠 문제에서 좌표상 오른쪽 또는 아래쪽과 연결되어 있다는 점과 숫자쌍이 1번씩만 등장한다는 특징이 있는 문제이다.

우선 숫자쌍이 한번씩만 존재하므로 이것을 기록하기 위해 이차원 배열을 만들어줬다.

const numbersPair = Array.from({ length: 10 }, () =>
        Array.from({ length: 10 }, () => false)
);

만약 1,9 가 짝을 이룬 상태라면 numbersPair[1][9] 는 true 인 상태가 될 것이다.

이후 각 그래프에 적힌 숫자를 기록할 gr과 각 인덱스별로 입력이 가능한 숫자를 기록할 usedNumber 그래프를 선언해준다.

const gr = Array.from({ length: 9 }, () =>
        Array.from({ length: 9 }, () => 0)
);

const usedNumber = Array.from({ length: 9 }, () =>
    Array.from({ length: 9 }, () => Array.from({ length: 10 }, () => true))
);

usedNumber의 각 인덱스에는 한 그리드 (3*3), 같은 행, 같은 열을 탐색해서 이미 사용 된 1부터 9까지 수는 true 처리가 될 것이고, 아직 사용되지 않는 숫자라면 false로 기록될 것이다.

위의 탐색을 위해 필요한 함수를 작성해준다.

const isPossible = (r, c, value) => {
        const rs = Math.floor(r / 3) * 3;
        const cs = Math.floor(c / 3) * 3;
        for (let i = rs; i < rs + 3; i++) {
            for (let j = cs; j < cs + 3; j++) {
                if (i === r && j === c) continue;
                if (gr[i][j] === value) {
                    return false;
                }
            }
        }

        for (let cs = 0; cs < 9; cs++) {
            if (cs === c) continue;
            if (gr[r][cs] === value) {
                return false;
            }
        }
        for (let rs = 0; rs < 9; rs++) {
            if (rs === r) continue;
            if (gr[rs][c] === value) {
                return false;
            }
        }

        return true;
};

이제 입력값에 주어진 것들을 그래프에 등록해두고 각 점들을 탐색해나가면서 usedNumber를 채워준다.

( 입력값의 행이 알파벳으로 주어져서 이를 아스키코드 대문자 A값 65를 빼주는 것으로 숫자화 해줌 )

const convertCoordinate = (char) => {
    const [charRow, charCol] = char.split('');
    const row = charRow.charCodeAt() - 65;
    const col = +charCol - 1;
    return [row, col];
};
const convert = (str) => {
    const [fn, fc, sn, sc] = str.split(' ');
    return [+fn, convertCoordinate(fc), +sn, convertCoordinate(sc)];
};


for (let i = 0; i < n; i++) {
        const [fn, [fr, fc], sn, [sr, sc]] = convert(input.shift());
        numbersPair[fn][sn] = true;
        numbersPair[sn][fn] = true;
        gr[fr][fc] = fn;
        gr[sr][sc] = sn;
    }
input
    .shift()
    .split(' ')
    .forEach((v, idx) => {
        const [r, c] = convertCoordinate(v);
        gr[r][c] = idx + 1;
    });
    
for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
        if (gr[i][j] !== 0) continue;
        for (let num = 1; num < 10; num++) {
            if (isPossible(i, j, num)) {
                usedNumber[i][j][num] = false;
            }
        }
    }
}

이제 인덱스 0,0부터 시작하여 만약 현재 좌표가 0 이라는 아직 입력이 안된 위치라면,

1. usedNumber를 통해 그 자리에 올 수 있는 숫자를 찾는다.

2. 각 인덱스는 오른쪽 또는 아래와 연결되어 있어야 하므로 현재 좌표에 각각 [ [+0,+1] , [+1,+0] ]에 위치한 좌표를 탐색한다.

이 좌표가 9*9 그래프를 벗어나지 않고, gr에는 0으로 기록되어 있어야 한다. (0이 아니라면 이미 사용된 좌표라는 것이므로 )

또한, 연결 된 좌표에 올 수 있는 숫자는  ( usedNumber[다음 좌표] 에서 false인 값 && [현재 좌표]에 쓰일 값과 다른 값 && isPossible 함수를 돌려서 올 수 있는 수  && numbersPair[현재좌표에 올 수][다음 좌표에 올 수] 가 false ) 이를 만족해야 한다.

이를 코드화 하면

const dx = [0, 1];
const dy = [1, 0];

for (let value = 1; value < 10; value++) {
                if (usedNumber[r][c][value] === true) continue;
                if (!isPossible(r, c, value)) continue;

                for (let i = 0; i < 2; i++) {
                    const nx = r + dx[i];
                    const ny = c + dy[i];
                    if (nx >= 9 || ny >= 9) continue;
                    if (gr[nx][ny] !== 0) continue;
                    for (let num = 1; num < 10; num++) {
                        if (usedNumber[nx][ny][num] === true) continue;
                        if (value === num) continue;
                        if (!isPossible(nx, ny, num)) continue;
                        if (numbersPair[value][num] || numbersPair[num][value])
                            continue;

                        numbersPair[value][num] = true;
                        numbersPair[num][value] = true;
                        gr[r][c] = value;
                        gr[nx][ny] = num;
                        dfs(cur + 1);
                        numbersPair[value][num] = false;
                        numbersPair[num][value] = false;
                        gr[nx][ny] = 0;
                        gr[r][c] = 0;
                    }
                }
    }

위의 조건들을 만족한다면 다음 좌표를 탐색하기 위해 dfs( cur+1 ) 를 돌려준다. 여기에서 cur은 9로 나눈 몫은 행, 9로 나눈 나머지는 행이 된다. 

만약 해당 dfs 과정이 불만족시 이전에 만족했던 조건으로 다시 돌아가서 탐색을 할 것이므로 false 처리와 0 처리 하는 것을 잊으면 안된다.

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const dx = [0, 1];
const dy = [1, 0];

const answer = [];

let t = 1;

const convertCoordinate = (char) => {
    const [charRow, charCol] = char.split('');
    const row = charRow.charCodeAt() - 65;
    const col = +charCol - 1;
    return [row, col];
};
const convert = (str) => {
    const [fn, fc, sn, sc] = str.split(' ');
    return [+fn, convertCoordinate(fc), +sn, convertCoordinate(sc)];
};

while (input.length) {
    const n = +input.shift();
    if (n === 0) break;
    answer.push(`Puzzle ${t++}`);

    const numbersPair = Array.from({ length: 10 }, () =>
        Array.from({ length: 10 }, () => false)
    ); // r,c 가 true라면 짝이 확정된 상태라는 뜻

    const gr = Array.from({ length: 9 }, () =>
        Array.from({ length: 9 }, () => 0)
    );

    const usedNumber = Array.from({ length: 9 }, () =>
        Array.from({ length: 9 }, () => Array.from({ length: 10 }, () => true))
    );

    const isPossible = (r, c, value) => {
        const rs = Math.floor(r / 3) * 3;
        const cs = Math.floor(c / 3) * 3;
        for (let i = rs; i < rs + 3; i++) {
            for (let j = cs; j < cs + 3; j++) {
                if (i === r && j === c) continue;
                if (gr[i][j] === value) {
                    return false;
                }
            }
        }

        for (let cs = 0; cs < 9; cs++) {
            if (cs === c) continue;
            if (gr[r][cs] === value) {
                return false;
            }
        }
        for (let rs = 0; rs < 9; rs++) {
            if (rs === r) continue;
            if (gr[rs][c] === value) {
                return false;
            }
        }

        return true;
    };

    for (let i = 0; i < n; i++) {
        const [fn, [fr, fc], sn, [sr, sc]] = convert(input.shift());
        numbersPair[fn][sn] = true;
        numbersPair[sn][fn] = true;
        gr[fr][fc] = fn;
        gr[sr][sc] = sn;
    }
    input
        .shift()
        .split(' ')
        .forEach((v, idx) => {
            const [r, c] = convertCoordinate(v);
            gr[r][c] = idx + 1;
        });

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (gr[i][j] !== 0) continue;
            for (let num = 1; num < 10; num++) {
                if (isPossible(i, j, num)) {
                    usedNumber[i][j][num] = false;
                }
            }
        }
    }

    let isSuccess = false;

    const dfs = (cur) => {
        if (isSuccess === true) return;
        if (cur === 81) {
            isSuccess = true;
            answer.push(...gr.map((r) => r.join('')));
            return;
        }
        const [r, c] = [Math.floor(cur / 9), cur % 9];

        if (gr[r][c] !== 0) {
            dfs(cur + 1);
        } else {
            for (let value = 1; value < 10; value++) {
                if (usedNumber[r][c][value] === true) continue;
                if (!isPossible(r, c, value)) continue;

                for (let i = 0; i < 2; i++) {
                    const nx = r + dx[i];
                    const ny = c + dy[i];
                    if (nx >= 9 || ny >= 9) continue;
                    if (gr[nx][ny] !== 0) continue;
                    for (let num = 1; num < 10; num++) {
                        if (usedNumber[nx][ny][num] === true) continue;
                        if (value === num) continue;
                        if (!isPossible(nx, ny, num)) continue;
                        if (numbersPair[value][num] || numbersPair[num][value])
                            continue;

                        numbersPair[value][num] = true;
                        numbersPair[num][value] = true;
                        gr[r][c] = value;
                        gr[nx][ny] = num;
                        dfs(cur + 1);
                        numbersPair[value][num] = false;
                        numbersPair[num][value] = false;
                        gr[nx][ny] = 0;
                        gr[r][c] = 0;
                    }
                }
            }
        }
    };

    dfs(0);
}

console.log(answer.join('\n'));