TypeScript를 이용해서 스도쿠 게임을 만들어보자 !

 

스도쿠 게임을 만들어보자 !

 

그냥 재미삼아 만들었습니다.

 

사람이 머리를 써서 만드는 게 아닌 컴퓨터 연산의 힘을 빌려 랜덤하게 모든 빈칸에 수를 넣어 문제를 만드는 탓에 빈칸이 많은 문제는 생성하지 못합니다.

 

빈칸과 난이도가 반드시 일치하는 것은 아니지만 어쨌든 저는 빈칸이 그리 많지 않은 문제를 랜덤하게 생성하는 데 쓰고, 빈칸이 적은 문제는 직접 하드코딩해서 메모리에 로드해둔 방식으로 완성했습니다.

 

여기서는 스도쿠 문제를 생성하는 데까지 진행하고, 이후 스도쿠 테이블을 눌렀을 때 어떻게 반응하는지와 같은 게임적인 요소는 생략하겠습니다.

 

빈칸이 하나 늘어날 때마다 많은 검증을 해야 하기 때문에 유저가 게임을 시작할 때 큰 기다림 없이 1, 2초 내에 실행되기 위해서는 숫자칸이 22개 정도가 한계인 것 같습니다. 지금은 그냥 프런트에 생성기 코드를 js로 만들고 바로  import해서 쓰려고 이렇게 했지만, 서버로 요청해서 Java로 만들어 리턴하는 식으로 했을 적엔 18개까지는 괜찮았던 것 같습니다. 아마 C로 만들어서 애드온을 이용하는 식으로 하면 숫자칸이 15, 6개까지는 더 줄어들 수 있지 않을까 싶습니다..

 

 

전체 코드: https://github.com/Hyeonnam-J/sudoku-generator

GitHub - Hyeonnam-J/sudoku-generator: sudoku generator

 

 

package.json

 

tsconfig.json

 

 

위와 같이 설정하고 시작하겠습니다.

 

 

 

 

간단하게 클래스를 만들고 터미널에 npm start를 입력해서 build가 잘 되는지 테스트.

 

 

 

 

전역변수입니다.

 

row, col, subgrid는 스도쿠 문제를 만드는 과정에서 행, 열, 서브그리드에 중복된 숫자 입력을 체크하는 용도로 사용합니다.

 

제가 방법을 모르는 건지... 배열 길이를 고정하고 값을 모두 0으로 할당하는 과정이 타입스크립트는 좀 복잡하더라고요. 따로 메서드를 만들어서 처리했습니다.

 

 

 

 

자주 쓰일 함수는 따로 빼줄까 싶어 func.ts를 만들었습니다만, 굳이... 간단한 프로젝튼데 그냥 한 페이지에 두는 게 나은 것 같습니다.

 

 

 

 

 

generate()의 첫 번째 순서는 보드를 초기화하는 것입니다.

 

 

 

 

initBoard()을 짜기 전에 전체적인 구조 파악을 위한 이미지를 보여드리면,

 

 

 

 

위와 같이 됩니다.

 

3x3의 작은 사각형 하나가 서브그리드고, 이 서브그리드 9개가 보여 9x9 스도쿠 보드가 됩니다.

 

9개 서브그리드 번호는 좌상단을 0으로 시작해서 하나씩 증가하게 됩니다. 그럼 지금 사진에서 offset은 0, 4, 8번 서브그리드의 좌상단이 되겠죠.

 

스도쿠 문제를 만드는 과정에서 0, 4, 8번 서브그리드를 먼저 초기화하는 이유는,

 

1 ~ 9까지 랜덤하게 섞인 배열 하나를 만들어서 0, 4, 8번 서브그리드에 넣게 되면 같은 행과 같은 열에 같은 번호가 있는지 중복 검사를 하지 않아도 되기 때문입니다. 한마디로 백트래킹의 부하 감소를 위함입니다.

 

 

 

 

offset은 0, 3, 6으로 뜁니다. 각 offset은 서브그리드 0, 4, 8번의 좌상단 행, 열의 값입니다.

 

 

 

 

각 offset을 기준으로 1 ~ 9의 숫자가 담긴 배열을 만들고 랜덤하게 섞습니다.

 

 

 

 

 

func.ts로 가서 작성해줍니다. 피셔-예이츠 셔플 알고리즘으로 섞었습니다.

 

 

 

 

서브그리드 초기화가 끝나고, 스도쿠 문제를 만드는 과정에서 특정 행, 열, 서브그리드에 숫자를 넣을 때 중복 체크를 해야 하기 때문에 특정 숫자를 넣었다면 2차원 배열 row, col, subgrid의 값을 1로 바꿔줍니다.

 

초기화가 끝나고 스도쿠를 만드는 과정에서 만약 5번째 행, 2번째 열에 7이라는 값을 넣고자 하면,

row[5][7] == 0 && col[2][7] == 0 && subgrid[2][7] == 0이 참이어야 하는 식입니다.

 

끝으로 board에 값을 넣어주고 출력을 해보면,

 

[
  [ 3, 8, 1, 0, 0, 0, 0, 0, 0 ],
  [ 2, 4, 6, 0, 0, 0, 0, 0, 0 ],
  [ 9, 7, 5, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 7, 4, 6, 0, 0, 0 ],
  [ 0, 0, 0, 8, 5, 9, 0, 0, 0 ],
  [ 0, 0, 0, 1, 2, 3, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 3, 9, 7 ],
  [ 0, 0, 0, 0, 0, 0, 8, 5, 4 ],
  [ 0, 0, 0, 0, 0, 0, 1, 2, 6 ]
]

 

이런 식으로 0, 4, 8번 서브그리드에 번호가 잘 채워져 있습니다.

 

 

 

 

다음은 9x9 스도쿠 보드 전체에 숫자를 넣어줘야 합니다.

makeBoard 로직을 구현합니다.

 

 

 

 

makeBoard는 재귀적으로 작동하는 메서드입니다.

 

boardIdx는 0 ~ 80의 9x9 스도쿠 한 칸 한 칸을 의미합니다. 그래서 그 값이 81이면 0부터 80의 모든 보드 칸에 값이 채워졌다는 의미이므로 로직을 더 진행하지 않고 참값으로 리턴합니다.

 

 

 

 

makeBoard 전에 initBoard에서 서브그리드 0, 4, 8번은 초기화가 됐었습니다. 해서 현재 보드 인덱스로 현재 행렬을 구해 값이 존재하면 로직을 진행하지 않고 다음 칸으로 이동합니다.

 

 

 

 

이제 값을 랜덤하게 넣어주면 됩니다.

 

1 ~ 9 사이 랜덤한 수를 하나 생성하고, 그 수를 기준으로 배열을 만듭니다.

 

스도쿠 칸에 숫자가 랜덤하게 채워지다 보면 중복 때문에 넣을 수 없는 경우가 생기는데 그런 경우 계속해서 다음 수를 넣어서 검증을 시도해야 합니다.

 

 

 

 

numbers 배열에서 하나씩 값을 뽑아 넣어봅니다.

 

randomNumber를 먼저 넣고 유효하지 않다면 for문의 idx를 이용해 다음 값을 만들어 넣는 식의 방법이 메모리 비용을 절약할 수 있지만 저는 가독성 측면에서 저렇게 구현했습니다.

 

중복 체크 후, 진입하여 중복 변수들을 업데이트하고 board에 값을 할당한 후 재귀적으로 이동합니다. 다음 칸에서 참값이 리턴된다면 이번 칸도 참값을 리턴하지만 다음 칸에서 거짓 값이 리턴된다면 중복 변수들과 보드 값을 다시 0으로 초기화합니다.

 

 

 

 

값을 찍어 확인합니다.

 

여기까지하면 보드가 완성되었습니다. 완성된 보드는 답안으로 쓰고, 여기에서 숫자를 랜덤하게 제거해 문제를 만들 예정입니다.

 

generate 메서드를 수정합니다.

 

 

 

 

결국 generate()가 리턴해야 하는 것은 스도쿠 답안과 문제입니다. 그걸 통해 프런트에서는 문제를 보여주고 유저의 입력에 반응해 답안을 체크하는 등 처리를 할 수 있습니다.

 

따라서 우선 answer에 완성된 board를 저장하고, 다시 removeBoardValue 메서드를 통해 board의 숫자를 랜덤하게 제거한 뒤 question에 할당하겠습니다.

 

 

 

 

removeBoardValue 메서드는 보드에서 지울 숫자의 개수를 인자로 받습니다.

 

저는 numToRemove를 60정도로 마지노선을 잡았습니다. 조금 더 높여도 되지만 일단 보수적으로 잡아보겠습니다.

 

positions는 보드를 랜덤하게 제거하는 데 쓰일 변수입니다. 타입을 Position이라 명명하고 클래스를 새로 만들어주겠습니다.

 

 

 

 

 

 

좌표를 가지고 있습니다.

 

suffleArray는 미리 정의했던 메서드인데 원래는 number[] 타입을 받았었습니다. 지금 positions의 타입은 Position[] 입니다. 같이 나눠 쓰기 위해서 suffleArray의 파라미터 타입을 제네릭으로 수정합니다.

 

 

 

 

이제 removeWithBackTracking 로직을 구현합니다.

 

 

 

 

재귀적으로 호출될 메서드입니다. 제거를 지시받은 수 numToRemove가 0이 되면 종료합니다.

 

 

 

 

for문 루프로 positions의 앞부분부터 가져와 거기 쓰인 좌표로 보드를 삭제합니다.

 

앞에서 배열 positions를 미리 섞어뒀기 때문에 for문에서 순차적으로 처리해도 결과적으로 랜덤하게 삭제한 모양새가 됩니다.

 

hasUniqueSolution은 유일해를 검증합니다.

 

removeWithBackTracking에서 값을 제거한 후 hasUniqueSolution으로 유일해가 검증되었다면, 재귀적으로 다시 removeWithBackTracking를 호출합니다. 제거를 했기 때문에 numToRemove와 positions 값을 조정하여 호출합니다.

 

그러나 유일해가 검증되지 않는다면 제거한 값을 복구합니다.

 

 

 

 

removeNumber, restoreNumber 메서드 구현입니다.

 

 

 

 

유일해를 검증할 메서드입니다. 

 

proveWithBackTracking을 실행해서 그 값이 1, 즉 유일해면 참을 리턴합니다.

 

 

 

 

countSolution은 해의 개수를 담을 변수입니다. 지금 0이고, 유일해라면 1이 리턴될 것이고 만약 2를 넘어간다면 유일해가 아니기 때문에 메서드를 더 진행하지 않고 종료합니다.

 

여기선 먼저 findNextEmptyCell 메서드로 탐색할 빈칸 좌표를 받아옵니다.

 

 

 

 

남아있는 빈칸 중에서 1 ~ 9까지의 숫자를 하나씩 넣는다고 했을 때, 가능한 경우의 수가 가장 적은 것을 탐색해서 그 행, 열의 값을 리턴합니다.

 

이렇듯 가능한 경우의 수가 적은 빈칸부터 처리를 해야 조금이라도 성능을 높일 수 있을 것 같습니다.

 

 

 

 

isValid 메서드입니다. 간단하게 중복 체크를 합니다.

 

이제 다시 proveWithBackTracking 메서드로 돌아갑니다.

 

 

 

 

탐색할 빈칸 좌표를 가져와서 수를 하나씩 넣어봅니다.

 

수가 유효하다면 값을 저장하고 재귀적으로 다시 proveWithBackTracking을 호출합니다.

 

그렇게 계속 다음 빈칸을 탐색해서 끝까지 가 더 탐색할 빈칸이 없으면 해를 하나 찾았다는 의미로 1을 리턴합니다. 그러나 루프를 돌며 끝까지 가 완성된 해가 하나 이상이 나오면 유일해가 아니기 때문에 루프를 마치고 메서드를 종료합니다.