LeetCode N 황후와 수독의 귀속 사고방식 분석

분석은 리코드#51N황후와 리코드#37을 바탕으로 단독으로 해답을 구한다.

1. 귀속 변수 찾기

N황후 문제는 변수는 방치된 황후의 수량이고 변수는 level이 0에서 N으로 최종적으로 귀속된다. 위코드는 다음과 같다.

func(level) {
  loop col 0 -> n {
    func(level + 1);
  }
}

Sukodu 문제, 변수는 숫자가 제대로 배치되지 않은 모든 칸입니다. 위코드는 다음과 같습니다.

w = board.length;

func() {
    loop i 0 -> w {
       loop j 0 -> w {
            func();  
       }
    }   
}

2. 언제 해답을 찾을까

N황후 문제는 N층으로 귀속되어 모든 황후가 이미 자리를 잡았다는 것을 설명한다.
합리적인 데이터 구조를 설정하여 결과를 저장하는 데이터는 여기서 특히 중요하다. 여기서 우리는 그룹을 세어 다음에 i의 위치로 표시된 i행 황후의 배치 위치를 저장한다. 예를 들어 match[0]는 1이고 1행의 황후가 2열의 위치에 놓여 있음을 나타낸다.
N층으로 돌아가 구조를 저장된 결과의 변수에 채우면 됩니다. 위조 코드는 다음과 같습니다.

var result = [];

func(level, match) {
+ if(level == n) result.push(match);
  loop col 0 -> n {
+   func(level + 1, [...match, col]);
  }
}

func(0, []);

Sukodu 문제는 약간 특수하다. 왜냐하면 결과가 하나만 있다고 가정하면 우리는 결과를 초기의 바둑판board에 저장하고 모든 칸에 귀속시킨 후board가 최종 결과이기 때문이다. 여기dosomething 코드는 다음에 소개한다.

func(board) {
   w = board.length;
    loop i 0 -> w {
       loop j 0 -> w {
         if(board[i][j]=== '.') {
             // dosomething
              func(board);  
             // dosomething
          }
       }
    }   
}

3. 어떻게 거슬러 올라가는가

가장 어려운 부분은 실행 과정이 어떻게 거슬러 올라가는가이다. 해를 찾는 과정에서 반드시 일부 조건이 귀속을 앞당겨 중지시키고 귀속을 하고 다른 옵션의 귀속을 한다.
예를 들어 우리는 N황후의 바둑판에서 첫 번째 줄(0,0)에 황후를 배치한 다음에 두 번째 줄(1,2)의 위치에 두 번째 황후를 배치한 다음에 세 번째 줄에 황후를 배치할 수 없다는 것을 발견하면 순서대로 방치한 결과를 철회해야 한다. 먼저 두 번째 줄의 황후 방식을 (1,3), 세 번째 줄은 합리적인 배치 위치를 찾을 수 없고 첫 번째 줄의 황후를 배치(0,1)할 때까지 계속 거슬러 올라간다.
여기에는 두 가지 관건이 관련되어 있다

첫 번째는 조건에 만족하지 않는 윤훈을 어떻게 판정하는가

두 번째는 어떻게 귀속 후 기입한 데이터를 거슬러 올라가는가

N황후의 위조번호는 다음과 같다.

첫 번째 문제는 N황후의 규칙은 가로세로 삐죽거리는 방향에서 황후가 충돌할 수 없다는 것이다. 황후 간의 x좌표, y좌표, x+y, x-y가 같지 않으면 된다.

두 번째 문제.교묘하게 결과를 match에 저장했기 때문에 매번 func를 호출하는 match는 모두 새것이므로 부급 호출 결과에 영향을 주지 않고 거슬러 올라갈 필요가 없다.

var result = [];

func(level, match) {
 if(level == n) result.push(match);
  loop col 0 -> n {
+   if(isValid(match, col)) {
        func(level + 1, [...match, col]);
+   }
  }
}

func(0, []);

고유한 위조 코드는 다음과 같습니다.

매번 바둑판에 귀속되어 기입하지 않은 숫자 위치를 발견

있으면'1'부터'9'까지 이 위치에 기입해 보세요

다음 계층 귀속을 시작하고 함수 끝에 있는 return true 대표 바둑판이 두루 돌아다니면서 모든 위치에 숫자를 채웠다는 것을 알아차렸다

만if(func()){ return true;}은 밑바닥에서 돌아가는 결과에서 위로 돌아가는 것이고, return false는 한 칸에 숫자를 채우려는 시도가 모두 실패했다는 것을 의미한다.

바둑판을 돌려서 모든 숫자가 놓여 있는 것을 발견하면true로 바로 돌아갑니다.

func(board) {
   w = board.length;
    loop i 0 -> w {
       loop j 0 -> w {
+           if(board[i][j] === '.') {
+               for k '1' -> '9' {
+                   if(isValid(i, j, k) {
+                       board[i][j] = k;
+                       if(func()) {
+                        return true;
+                      } else {
+                        board[i][j] = '.';
+                      }
+                   }
+               }
+               return false;
+           }
       }
    }   
+   return true;
}

4. JavaScript 버전 구현

N황후

cols,pie,la로 황후를 방치한col,x-y,x+의 값을 각각 저장한 것을 볼 수 있어 교묘하다.

var solveNQueens = function(n) {
  var cols = [], pie = [], la = [];
  var result = [];
  function nthQueue(level, match) {
    if(level === n) result.push(match);
    for (let i = 0; i < n; i++) {
      if(cols.indexOf(i) === -1 && pie.indexOf(level + i) === -1 && la.indexOf(level - i) === -1) {
        cols.push(i);
        pie.push(level + i);
        la.push(level - i);
        nthQueue(level + 1, [...match, i])
        cols.pop();
        pie.pop();
        la.pop();
      }
    }
  } 
  nthQueue(0, []);
  return result.map(d => {
    return d.map(dd => {
      let s = '';
      for(let i = 0; i < n; i++) {
        s += ((i == dd) ? 'Q' : '.')
      }
      return s;
    })
  })
}

console.log(JSON.stringify(solveNQueens(4))=='[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]');

홀로

  var input = [
      ["5","3",".",".","7",".",".",".","."],
      ["6",".",".","1","9","5",".",".","."],
      [".","9","8",".",".",".",".","6","."],
      ["8",".",".",".","6",".",".",".","3"],
      ["4",".",".","8",".","3",".",".","1"],
      ["7",".",".",".","2",".",".",".","6"],
      [".","6",".",".",".",".","2","8","."],
      [".",".",".","4","1","9",".",".","5"],
      [".",".",".",".","8",".",".","7","9"],
  ];

  var output = [
      ["5","3","4","6","7","8","9","1","2"],
      ["6","7","2","1","9","5","3","4","8"],
      ["1","9","8","3","4","2","5","6","7"],
      ["8","5","9","7","6","1","4","2","3"],
      ["4","2","6","8","5","3","7","9","1"],
      ["7","1","3","9","2","4","8","5","6"],
      ["9","6","1","5","3","7","2","8","4"],
      ["2","8","7","4","1","9","6","3","5"],
      ["3","4","5","2","8","6","1","7","9"]
  ];

  var solveSudoku = function(board) {
    let w = board.length;
    var isValid = function(x, y, v){
      for (let i = 0; i < w; i++) {
        if(board[x][i] == v || board[i][y] == v) return false;
        for (let j = Math.floor(x/3)*3; j < (Math.floor(x/3)+1)*3; j++) {
          for (let k = Math.floor(y/3)*3; k < (Math.floor(y/3)+1)*3; k++) {
            if(board[j][k] == v) return false;
          }
        }
      }
      return true;
    }
    var visitSudoku = function() {
      for (let i = 0; i < w; i++) {
        for (let j = 0; j < w; j++) {
          if(board[i][j] === '.')  {
            for (let k = 1; k <= w; k++) {
              if(isValid(i, j, k+'')) {
                board[i][j] = k+'';
                if(visitSudoku()) {
                  return true;
                } else {
                  board[i][j] = '.';
                }
              }
            }
            return false;
          }

        }
      }
      return true;
    }
    visitSudoku()
    return board;
  }
  
  console.log(JSON.stringify(solveSudoku(input))===JSON.stringify(output))