nRooksDraft

nrooks.js

window.countNRooksSolutions = function(n) {
  var realSolution = [];
  var iT = [];
  var realBoardSize = n-1;

  if(n === 1){
    return 1;
  }
  
  for(var masterRookIndex = 0; masterRookIndex < n; masterRookIndex++) {
    //create new board
    var board = new Board({'n': n});
    //start initial rook position
    board.togglePiece(0, masterRookIndex);
    iT[0] = masterRookIndex;

    //iterating through every row of array
    //PER first row position.
    for(var row = 1; row < n; row++) {

      //iterating through every column in that row
      for (var col = 0; col < n; col++) {

        // if((0, masterRoo...) === (row, col)) {
        //   //we might not need this line since we 
        //   //always start on row = 1 in the previous
        //   //loop, no?

              //NOTE: THIS DOES NOT WORK AS EXPECTED,
              //DO NOT USE; ACTS LIKE AN 'OR' STATEMENT.
        //   continue;
        // }

        // OBSOLETE: fixed source of glitch by preventing moving i on the last loop.
        //(this paragraph)
        // //to prevent a glitch; forces us to 'double break'
        // //whenever we've done our rook incrementation on the last
        // //row, meaning a second loop from that room isn't necessary,
        // //so we can actually just reset the board (because this 'doube break'
        // // will actually be a 'triple break' once the row loop sees it is
        // //too high.)
        // // if (row > realBoardSize) break;

        //toggling piece and then see if it's conflict-free
        board.togglePiece(row, col);
        iT[row] = col; 

        if(board.hasAnyRowConflicts(row) || board.hasAnyColConflicts(col)){
          //if conflicts are flagged, we toggle the piece back to zero
          board.togglePiece(row, col);
          iT[row] = undefined;
          //and ignore rest of code and reloop with this position reset to zero
        } else {
          //this runs if both tests above return false, meaning 'if' condition
          //was not met, meaning there are no conflicts and it could be a solution.
          if(row === realBoardSize) {
            //if we're in this last row, and both tests were false,
            //we have a solution and push it out. Otherwise, just continue with 
            //the loop onto the next row. (?) NEEDS TO BREAK HERE IF NOT LAST
            //ROW (the 'else' of this evaluation) AND JUMP TO NEXT ROW!
            realSolution.push(board);
            //now we need to 'backtrack', the loop version of
            //recursing. We're going to look for the first *previous*
            //row where the rook is not currently on the far
            //right of that row AND we will reset any row where the rook 
            //IS on the far right.

            //start function? maybe lines 125-217 should go within a function?
            for (var recursingRow = realBoardSize; recursingRow >= 0; recursingRow--){
              //runs on every row BACKWARDS, from BOTTOM TO TOP.
              //does one of three things:
              //0. if we're in the last row, clear yourself and
              //continue the loop. (Don't adjust yourself. Prevents glitches.)
              //1. if we're not in the far right of the current row,
              //then we shift the position of '1' one position right
              //within that row... 
              //(NOTE: do we need to reset 'row'?)
              //2. if we ARE in the far right, we check if we're then
              //in the far right of the FIRST (0) ROW, which would indicate
              //that we've reached the end of the search and can exit
              //the function altogether.
              //3. if we ARE in the far right, but NOT in the 0 row, then
              //we simple 'reset' the row to all zeroes, and let the loop
              //jump up to a PREVIOUS row.
              if (recursingRow === realBoardSize) {
                board.togglePiece( recursingRow, (iT[recursingRow]) );
                iT[recursingRow] = undefined;
                continue;
              }


              else if(iT[recursingRow] < realBoardSize){ 
              //this block runs if we're NOT on the far right of the recursing row.

              //This is where my glitch lies. For some reason, after these operations,
              //things go wrong. Seems we need to jump the row, but it doesn't seem
              //to be working when I do that either... if I don't do anything about the 
              //row loop, though, it will "double flip" the most recently adjusted row's
              //rook position, taking it off the board for that row, I think.

                //these two lines toggle the current rook position 'off',
                //and toggle the position to the right of the rook 'on'.
                board.togglePiece( recursingRow, (iT[recursingRow]) ) //toggle current position off
                board.togglePiece( recursingRow, (iT[recursingRow]+1) ) //toggle new position on
                iT[recursingRow]++

                                //bug is HERE for 4x4; see gist notes.
                            //maybe a 'while' loop that checks for conflicts before continuing?
                            //Note: so, if I add the following while loop, it breaks 3x3, barely...
                            //probably because it doesn't check if i is all the way right.
                            //hmmm....
                var loopEscape = false;
                while(board.hasAnyRowConflicts(row) || board.hasAnyColConflicts(col)){
                if (iT[recursingRow] === realBoardSize) {loopEscape = true;}
                  board.togglePiece( recursingRow, (iT[recursingRow]) ) //toggle current position off
                  board.togglePiece( recursingRow, (iT[recursingRow]+1) ) //toggle new position on
                  iT[recursingRow]++
                }

                //do we now need to do row = a ?
                //CHECK HERE FOR PROBLEMS!-------(not currently active, so nm )
                //I think we need to jump to the row AFTER(below) the recursing row, since 
                //that's the one we modified, and we're now
                //checking for permutations of it...
                
                // col = realBoardSize; //this used to allow line allows "2" to function, but not "3"

                //we need to make it so that the row test doesn't 'pop', causing it to reset our board!

                row = recursingRow +1//when we jump out to the collumn loop, we want our background 
                //'row' value to be the row we just adjusted, +1

                col = -1 //we want to go through starting at the last clean row, on col position 0.
                //however, this will get incremented immediately after we break, so we set to -1 to
                //get the 0 position desired.
                
                if (!loopEscape) break; // we've now adjusted the recursing row, and toggled
                // the row we're going to start running at again, so now we need to exit
                // this loop, and run as normal with our newly right-adjusted rook.

              }
              else if ( recursingRow === 0){
                //this block runs if we're ON the far right of the MASTER (0) ROW.

                //here we should exit, because this means
                //that we've checked every possible permutation.
                //(because this row just failed prev test and 
                //is therefore on the far right @ first row)
                console.log(realSolution)
                var solutionCount = realSolution.length;
                console.log('Number of solutions for ' + n + ' rooks:', solutionCount); 
                return solutionCount;
              }

              else {
                //we're on the far right, but not on first row, so:
                //clean up the row, reloop on a row further up.
                board.togglePiece(recursingRow,realBoardSize); 
                iT[recursingRow] = undefined;
              }
            }
            //end function?
          } else {
            break; 
            //break out of collumn loop so that
            //a non-conflicted, non-last-row situation forces out
            //to the next row. (Seems to work!)
          }//end of 'last row AND non conflict' if loop

        }//end of 'non conflict' else loop (?)

      } //end of col loop
    } //end of row loop
  } //end of MasterRook/board generation loop

  console.log(realSolution)
  var solutionCount = realSolution.length;
  console.log('Number of solutions for ' + n + ' rooks:', solutionCount); 
  return solutionCount;
};

Now passes up to n3, gets 8/24 on n4.

Current fail on 4x4---

Won't try 0,2,3,undefined;

when it increments 0,2,1,3 into 0,2,2,undefined, and then recurses, it just starts looping the last row, instead of trying to loop the second to last row.

Should probably instantiate an evaluation for conflicts on 0,2,2, instead of just blindly incrementing 0,2,1 up to it and then breaking the loop.

SOLVED.

collapses

solution to last bug was to wrap it in a 'while' loop, and escape the 'break' statement with a flag that we set IF we find ourself run into the wall in the course of the while loop. Originally tried wrapping the entire condition in a function and calling it recursively, but that made things worse.