🧚 N-queens μ•Œκ³ λ¦¬μ¦˜

μ†Œκ°
흠..... λ„ˆλ¬΄ μ–΄λ €μ› κ³  문제λ₯Ό μ΄ν•΄ν•˜λŠ” 것뢀터 νž˜λ“€μ—ˆμŠ΅λ‹ˆλ‹€. ν€Έμ¦ˆκΉŒμ§€λŠ” λͺ» ν•˜μ˜€μ§€λ§Œ Rookκ³Ό λŒ€κ°μ„ μ—
κ΄€ν•œ 것은 μ™„λ£Œν•΄λ³΄μ•˜μŠ΅λ‹ˆλ‹€. solves도 λͺ» ν•˜μ˜€λ‹€λŠ” λΉ„λ°€.....

  • 첫번째 ν–‰
     hasRowConflictAt: function (rowIndex) { // ν–‰ μžμ²΄μ— 
       // console.log("hasRow: ",this.attributes)
       let chass = this.attributes[rowIndex];
       // console.log(this.attributes) 찍어보면 μœ μ‚¬λ°°μ—΄λ‘œ μ•„λž˜κ°€ λ‚˜μ˜΅λ‹ˆλ‹€.
       // μ—¬κΈ°μ„œ, μ°¨κ·Όμ°¨κ·Ό κ°€μ•Όν•©λ‹ˆλ‹€.
       // {0: Array(4), 1: Array(4), 2: Array(4), 3: Array(4), n: 4}
       let count = 0;
         // console.log('first',chass)
          for(let i = 0 ; i < chass.length; i++){ 
           // 각 행을 λŒλ©΄μ„œ 1을 찾게되면 countλ₯Ό λŠ˜λ €μ„œ 2κ°€ 되면 trueλ₯Ό ν„΄μ Έμ„œ λΉ¨κ°›κ²Œ λ§Œλ“­λ‹ˆλ‹€.
           if(chass[i] === 1){  // 0 1 0 0
             count++;           // 0 0 0 1
           }                    // 1 0 0 0
       }                        // 0 0 1 0
       return count > 1; // fixme
     }
  • 전체 행을 관리
  hasAnyRowConflicts: function () { // 판 μžμ²΄μ—μ„œ 체크
      let isConflict = false;       // _.every 처럼 ν•œλ‹€κ³  μƒκ°ν•˜μ˜€μŠ΅λ‹ˆλ‹€.
      let chassLength = this.attributes.n; // 길이만 κ°€μ Έμ˜΅λ‹ˆλ‹€.
        for (let i = 0; i < chassLength; i++) {  // μœ„μ—μ„œ μ‚¬μš©ν•œκ²ƒμ„ ν† λŒ€λ‘œ κ²°κ³Ό 값을 κ°€μ Έμ˜΅λ‹ˆλ‹€.
          this.hasRowConflictAt(i) && (isConflict = true);
        }
      return isConflict; // fixme
    },
  • μ„Έλ‘œ ν–‰

    μ„Έλ‘œ 행은 μ²˜μŒμ— μ΄ν•΄ν•˜λŠ”λ° 쑰금 μ‹œκ°„μ΄ κ±Έλ ΈμŠ΅λ‹ˆλ‹€. key 값을 움직여 μ„Έλ‘œλ‘œ κ°„λ‹€κ³  μƒκ°ν•˜μ˜€μŠ΅λ‹ˆλ‹€.
    μŠ€ν¬λ¦°μƒ·, 2019-08-02 00-57-33.png

 hasColConflictAt: function (colIndex) {
      let chass = this.attributes;
      // console.log(chass)
      let count = 0;
      for(let key in chass){ // key 0, 1, 2, 3
          if(chass[key][colIndex] === 1){
            count++
          }
      }
      return count > 1; // fixme
    },
  • 전체 μ„Έλ‘œ μ—΄
  hasAnyColConflicts: function () { // μœ„μ— ν–ˆλ˜κ±°μ™€ λ˜‘κ°™μ΄ ν•˜λ©΄ λ˜μ—ˆλ‹€.
      let isConflict = false;
      let chassLength = this.attributes.n;
       for (let i = 0; i < chassLength; i++) {
         this.hasColConflictAt(i) && (isConflict = true);
       }
     return isConflict; // fixme
    },
  • λŒ€κ°μ„  (μ™Όμͺ½μ—μ„œ 였λ₯Έμͺ½μœΌλ‘œ)

μŠ€ν¬λ¦°μƒ·, 2019-08-02 01-04-56.png
i(ν–‰)μ—μ„œ j(μ—΄)λΉΌμ„œ

hasMajorDiagonalConflictAt: function (majorDiagonalColumnIndexAtFirstRow) {
      let chass = Object.values(this.attributes)
      let chassLength = chass[4]
      let count = 0;
      // console.log('top', majorDiagonalColumnIndexAtFirstRow)
      for (let i = 0; i < chassLength; i++ ){
        for (let j = 0; j < chassLength; j++) {
          if(i - j === majorDiagonalColumnIndexAtFirstRow && chass[j][i]){
            count++
          }
        }
      }
      // [0, 1, 2, 3]   [0,0,0,1]
      // [-1,0, 1, 2]   [0,0,0,1]
      // [-2,-1,0, 1]   [1,0,0,0]
      // [-3,-2,-1,0]   [0,1,0,0]

      return count > 1  // fixme
    },

λ°±νŠΈλ ‰ν‚Ή μ΄λž€?

νŠΉμ • λ…Έλ“œμ—μ„œ μœ λ§μ„±μ„ μ κ²€ν•˜κ³ , μœ λ§ν•˜μ§€ μ•ŠμœΌλ©΄ λ‹€μ‹œ λ…Έλ“œμ˜ λΆ€λͺ¨λ‘œ λŒμ•„κ°€μ„œ λ‹€μŒ λ…Έλ“œμ— λŒ€ν•œ
검색을 계속 ν•˜κ²Œλ˜λŠ” 절차 μž…λ‹ˆλ‹€.