[Algorithm] 완전탐색 (JS) - 2 : 백트래킹(Back Tracking)

1. 백트래킹이란 ? :

- 완전탐색의 기법으로, 주로 결정문제(경로찾기, 스도쿠, 여덟 퀸 문제 등)를 해결하는 데 사용된다.

- 가능한 모든 해(space of states)를 탐색하여 문제의 해결책을 찾는다.

- 이 과정에서 현재 해가 문제의 조건을 만족하지 않으면 이전 단계로 돌아가서 다른 선택지를 탐색한다.

- 이를 '되돌리기'라는 개념으로 사용한다.

- 가지치기(Pruning)를 통해 탐색 공간을 줄일 수 있어, 불필요한 경우의 수를 줄여 시간복잡도를 개선할 수 있다.

 

2. 구현 : 스도쿠 퍼즐 풀기

- 재귀를 사용하여 9x9 예제의 스도쿠 퍼즐을 백트래킹기법을 사용해 해결하는 예제이다.

 

천천히 읽어보자(뒤에 시각화 있음)

복잡하다 재귀

 

3. 리액트를 통한 시각화하기

- 코드만 읽으면 이해하기 어려우므로 시각화를 하여 함께 보자

- 일단 CRA로 프로젝트를 만들고 App.js를 구조화한다.

 

App.js

구조만 먼저 짜보자.

 

- 스타일도 있어야한다.

 

App.css

간단한 스타일링

 

결과

0은 헷갈려서 색을 칠해서 구분해주었다.

- 이제 로직을 삽입해보자

 

App.js

import {useState} from 'react';
import './App.css';

function App() {

  const [board, setBoard] = useState(
    [
      [5, 3, 0,  0, 7, 0,  0, 0, 0],
      [6, 0, 0,  1, 9, 5,  0, 0, 0],
      [0, 9, 8,  0, 0, 0,  0, 6, 0],
    
      [8, 0, 0,  0, 6, 0,  0, 0, 3],
      [4, 0, 0,  8, 0, 3,  0, 0, 1],
      [7, 0, 0,  0, 2, 0,  0, 0, 6],
    
      [0, 6, 0,  0, 0, 0,  2, 8, 0],
      [0, 0, 0,  4, 1, 9,  0, 0, 5],
      [0, 0, 0,  0, 8, 0,  0, 7, 9]
    ]
    )




    const isSafe = (board, row, col, num)=>{ // num을 (row,col) 위치에 놓을 수 있는지 확인하는 함수
      //가로 체크 (9x9)
      for(let i=0; i<9; i++){ 
        if(board[row][i] === num){ //열을 순회하면서 현재 선택한 num이 가로 중에 존재하는지 확인
          return false; //존재하면 false
        }
      }
      //세로 체크 (9x9)
      for(let i=0; i<9; i++){ 
        if(board[i][col] === num){ //행을 순회하면서 현재 선택한 num이 세로 중에 존재하는지 확인
          return false; //존재하면 false
        }
      }
      // 3x3 그리드 확인 
      const startRow = row - (row % 3); //3x3 작은격자 확인하기 위한 첫번째 좌표(열)
      const startCol = col - (col % 3); //3x3 작은격자 확인하기 위한 첫번째 좌표(행)
      for(let i =0; i<3; i++){
        for(let j =0; j<3; j++){
          if(board[i+startRow][j+startCol] === num){ //3x3 순회하면서 중복숫자 확인
            return false; //중복숫자 있으면 false
          }
        }
      }
      return true; //num을 (row, col) 위치에 놓을 수 있음
    }
    
    const delay = (ms) => new Promise((resolve) => setTimeout(resolve, ms));

const solveSudoku = async (board) => {
  let row = -1;
  let col = -1;
  let isEmpty = true;

  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (board[i][j] === 0) {
        row = i;
        col = j;
        isEmpty = false;
        break;
      }
    }
    if (!isEmpty) {
      break;
    }
  }

  if (isEmpty) {
    return true;
  }

  for (let num = 1; num <= 9; num++) {
    if (isSafe(board, row, col, num)) {
      board[row][col] = num;
      setBoard(JSON.parse(JSON.stringify(board))); // setBoard를 호출하여 바뀐 상태를 시각화합니다.
      await delay(5); 

      if (await solveSudoku(board)) {
        return true;
      }

      board[row][col] = 0;
      setBoard(JSON.parse(JSON.stringify(board))); // setBoard를 호출하여 바뀐 상태를 시각화합니다.
      await delay(5); 
    }
  }

  return false;
};

const handleSolveClick = async () => {
  const newBoard = JSON.parse(JSON.stringify(board));
  if (await solveSudoku(newBoard)) {
    console.log("풀었다");
    console.log(newBoard);
    setBoard(newBoard);
  } else {
    console.log("풀 수 없는 스도쿠다");
  }
};



  return (
    <div className="App">
      {
        board.map((e,idx) => {
          return(
            <div className='col' key={`row-${idx}`}>
              {
                e.map((e2, idx2)=>{
                  return(
                    <div className={`box line${idx}`} key={`cell-${idx}-${idx2}`}>
                      {e[idx2] === 0 ? <div className='empty'></div> : e[idx2]}
                    </div>
                  )
                })
              }
            </div>
          ) 
        })
      }
      <button onClick={()=>{handleSolveClick()}} style={{background:'red', width:200, height:200, color:'#fff'}}>START</button>
    </div>
  );
}

export default App;

- 딜레이를 5ms 로 설정해서 백트래킹의 시각화를 조금이라도 보일 수 있도록 설정했다.

- 딜레이를 조금 늘리면 더 잘보이지만 하루 종일 푼다.

- 근데 5ms도 너무 오래걸리긴 한다. 

 

4. 최종결과

 

백트래킹 노가다

 

이렇게 되었다. 대충 어떤 느낌인지 알겠다.