스도미노쿠

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

let ans = null;

// 스도쿠 칸을 넘어가는지 검사하는 함수
const isPossibleRoute = (x, y) => 0 <= x && x < 9 && 0 <= y && y < 9;

// 재귀 함수
const solveSdoku = (blanks, sdoku, row, col, grid, domino, depth) => {
	if (ans !== null) return;

	// 빈 칸을 모두 채웠으면 문자열 기록
	if (depth === blanks.length) {
		ans = sdoku.map((v) => v.join("")).join("\n");
		return;
	}

	const [x1, y1] = blanks[depth];

	if (sdoku[x1][y1] !== 0) {
		// 스도쿠 칸이 이미 채워져 있다면, 재귀 함수 수행
		solveSdoku(blanks, sdoku, row, col, grid, domino, depth + 1);
	} else {
		// 채워져 있지 않다면 36 개의 도미노 적용
		for (let i = 1; i < 9; i++) {
			for (let j = i + 1; j < 10; j++) {
				// 도미노 체크
				if (domino[i][j] === true) continue;

				// 정방향과 역방향 도미노
				const dom = [
					[i, j],
					[j, i],
				];

				// 정방향과 역방향 도미노에 대해
				for (let k = 0; k < 2; k++) {
					const [n1, n2] = dom[k];

					if (row[x1][n1] === true) continue;
					if (col[y1][n1] === true) continue;
					if (grid[3 * parseInt(x1 / 3) + parseInt(y1 / 3)][n1] === true)
						continue;

					sdoku[x1][y1] = n1;
					row[x1][n1] = true;
					col[y1][n1] = true;
					grid[3 * parseInt(x1 / 3) + parseInt(y1 / 3)][n1] = true;

					// 가로와 세로
					const dir = [
						[x1, y1 + 1],
						[x1 + 1, y1],
					];

					// 가로와 세로에 대해
					for (let l = 0; l < 2; l++) {
						const [x2, y2] = dir[l];

						if (!isPossibleRoute(x2, y2)) continue;
						if (sdoku[x2][y2] !== 0) continue;

						if (row[x2][n2] === true) continue;
						if (col[y2][n2] === true) continue;
						if (grid[3 * parseInt(x2 / 3) + parseInt(y2 / 3)][n2] === true)
							continue;

						// 행, 열, 격자, 도미노 체크를 모두 통과했다면, 스도쿠에 기록 후 재귀
						sdoku[x2][y2] = n2;
						row[x2][n2] = true;
						col[y2][n2] = true;
						grid[3 * parseInt(x2 / 3) + parseInt(y2 / 3)][n2] = true;

						domino[i][j] = true;

						solveSdoku(blanks, sdoku, row, col, grid, domino, depth + 1);

						// 재귀함수에서 나올 때, 기록했던 정보 다시 초기화
						domino[i][j] = false;

						sdoku[x2][y2] = 0;
						row[x2][n2] = false;
						col[y2][n2] = false;
						grid[3 * parseInt(x2 / 3) + parseInt(y2 / 3)][n2] = false;
					}

					sdoku[x1][y1] = 0;
					row[x1][n1] = false;
					col[y1][n1] = false;
					grid[3 * parseInt(x1 / 3) + parseInt(y1 / 3)][n1] = false;
				}
			}
		}
	}
};

const solution = (input) => {
	let res = "";

	let testCase = 1;
	let index = 0;

	// 각 테스트케이스에 대해서
	while (true) {
		let n = Number(input[index++]);
		if (n === 0) break;

		// 스도쿠, 행, 열, 격자, 도미노 체크를 위한 배열 생성
		const sdoku = Array.from({length: 9}, () => Array(9).fill(0));
		const row = Array.from({length: 9}, () => Array(10).fill(false));
		const col = Array.from({length: 9}, () => Array(10).fill(false));
		const grid = Array.from({length: 9}, () => Array(10).fill(false));
		const domino = Array.from({length: 10}, () => Array(10).fill(false));

		// 주어진 n 개의 퍼즐 입력
		while (n-- > 0) {
			const str = input[index++].split(" ");
			const [n1, n2] = [str[0], str[2]].map(Number);
			const [[x1, y1], [x2, y2]] = [str[1], str[3]]
				.map((v) => v.split(""))
				.map((v) => [v[0].charCodeAt(0) - "A".charCodeAt(0), Number(v[1]) - 1]);

			const arr = [
				[x1, y1, n1],
				[x2, y2, n2],
			];

			if (n1 <= n2) domino[n1][n2] = true;
			else domino[n2][n1] = true;

			for (let i = 0; i < 2; i++) {
				const [x, y, n] = arr[i];

				sdoku[x][y] = n;
				row[x][n] = true;
				col[y][n] = true;
				grid[3 * parseInt(x / 3) + parseInt(y / 3)][n] = true;
			}
		}

		// 주어지는 9 개의 수 입력
		const base = input[index++].split(" ");
		for (let i = 0; i < 9; i++) {
			let [x, y] = base[i].split("");
			[x, y] = [x.charCodeAt(0) - "A".charCodeAt(0), Number(y) - 1];

			sdoku[x][y] = i + 1;
			row[x][i + 1] = true;
			col[y][i + 1] = true;
			grid[3 * parseInt(x / 3) + parseInt(y / 3)][i + 1] = true;
		}

		// 스도쿠에서 빈 칸 모두 찾기
		const blanks = [];
		for (let i = 0; i < 9; i++) {
			for (let j = 0; j < 9; j++) {
				if (sdoku[i][j] === 0) blanks.push([i, j]);
			}
		}

		// 재귀 함수 수행
		ans = null;
		solveSdoku(blanks, sdoku, row, col, grid, domino, 0);

		res += `Puzzle ${testCase++}\n${ans}\n`;
	}

	return res;
};

console.log(solution(input));