Pen Settings

HTML

CSS

CSS Base

Vendor Prefixing

Add External Stylesheets/Pens

Any URL's added here will be added as <link>s in order, and before the CSS in the editor. If you link to another Pen, it will include the CSS from that Pen. If the preprocessor matches, it will attempt to combine them before processing.

+ add another resource

JavaScript

Babel includes JSX processing.

Add External Scripts/Pens

Any URL's added here will be added as <script>s in order, and run before the JavaScript in the editor. You can use the URL of any other Pen and it will include the JavaScript from that Pen.

+ add another resource

Packages

Add Packages

Search for and use JavaScript packages from npm here. By selecting a package, an import statement will be added to the top of the JavaScript editor for this package.

Behavior

Save Automatically?

If active, Pens will autosave every 30 seconds after being saved once.

Auto-Updating Preview

If enabled, the preview panel updates automatically as you code. If disabled, use the "Run" button to update.

Format on Save

If enabled, your code will be formatted when you actively save your Pen. Note: your code becomes un-folded during formatting.

Editor Settings

Code Indentation

Want to change your Syntax Highlighting theme, Fonts and more?

Visit your global Editor Settings.

HTML

              
                <div id="sketch"></div>
<form id="sleep-time-form">
  <input id="sleep-time-input" type="number" value="200" min="20" required />
  <button type="submit">Update sleep duration (millisecs)</button>
</form>
<p>This visualisation demonstrates one way of solving the N-Queens problem, which is the problem of placing N queens on an NxN "chess" board such that no queen could attack any other queen. The algorithm here runs lazily &mdash; after every step, it sleeps for a bit to let us see what the board looks like after performing that step. You can change the value of the sleep duration to speed it up or slow it down using the input box (set it to 20 I love how flashy it gets). You can also change the size of the board through some variables in the code.</p>
<p>The rendering here is done through <a href="https://p5js.org/" target="_blank">p5.js</a>. I tried to do state management React-style, where each state update causes a re-render of the view. At first I thought it wasn't possible to get manual control over p5's render function (which they call "draw"), but a quick look at the docs gave me the answer (who knew!). Unfortunately though, there isn't a chess queen emoji so we'll have to settle for the crown emoji for rendering the queens 🙁.</p>
<p>This demonstration is basically a slowed down run of the algorithm. To achieve this, each step of the algorithm (a step that's visually relevant) sends a state update to the state handler. It then sleeps for a certain duration before performing the next step so we could see what's going on in the screen. If we didn't sleep, the algorithm would just whiz by and we'd only see the final state of the board. The sleep is async, because JS is a single-threaded language and so a sync sleep would block the main thread. Hence, the entire algorithm is run asyncronously. The state updates, however, are not async. So at the end of every call to a state update, we are guaranteed an updated state. Every state update triggers a re-render, which is performed in an async fashion by p5.</p>
<p>I'm so stoked that async/await turned out to be the perfect tool for this async version of the algorithm! The problem it solves is it gives us a graceful interleaving of the algorithmic steps with the re-rendering steps with a sleep after each re-rendering. At first, I thought of using p5's draw function to achieve this interleaving + sleeping loop. That is, I would put both the algorithm code and the rendering code in the same loop (interleaving), and set the framerate of p5's draw function to a low value (sleeping). But that would mean after each algorithmic step, I would have to break off from the algorithm code and jump to the rendering code. It would lead to an explosion of crazy control flow branches using breaks and returns. It was a tough reminder that in a stateful app, the app logic and render logic must live in separate loops, with a state in between them. App logic reads and writes to that state, and render logic reads from that state. Async/await provided just enough syntactic clarity to let me hack this model, albeit with synchronous state reads/writes.</p>
<p>Another lesson I learned about state management here: consider the possibility of "missing intermediate states". While writing this N-Queens program, I had a bug where the next cell to be explored wouldn't be reflected correctly in the state. Turns out, I was too eager to update the state when exploring the next cell. I figured out later that I would have to be aware of this future cell before actually moving on to it. Creating an intermediate variable (called "next" in the code) which would represent the future cell acted as the intermediate state that was missing all along. I didn't put the "next" variable in the state in this case, however, because I don't see any use in rendering it to the view. So a local variable it stays.</p>
<p>Ideally, each step of the algorithm would simply emit an event to the state handler and the handler would then decide whether to apply and how to apply state updates. In this approach, we'd have to perform state updates asynchronously. But we don't do that here, because async state management is difficult to implement. People should use a tried-and-tested state management solution for that. Something like <a href="https://reactjs.org/" target="_blank">React</a>.</p>

              
            
!

CSS

              
                
              
            
!

JS

              
                /*
BUG - the clash path "overflows" during rendering. Change the way I render the path. Render by walking along vector instead.
*/
// world parameters
const numRows = 10;
const numCols = 10;

// world state
const state = {
  queens: [],  // indices represent columns, values represent rows
  current: null,
  queenInQuestion: null,
  clashedQueen: null,
  
  setQueens: function(newQueens) {
    this.queens = newQueens;
    redraw();
  },
  setCurrent: function(newCurrent) {
    this.current = newCurrent;
    redraw();
  },
  setQueenInQuestion: function(newQueenInQuestion) {
    this.queenInQuestion = newQueenInQuestion;
    redraw();
  },
  setClashedQueen: function(newClashedQueen) {
    this.clashedQueen = newClashedQueen;
    redraw();
  }
};
let sleepTime = parseInt(document.querySelector('#sleep-time-input').value, 10);

// view parameters
const rectSize = 20;
const gutterSize = 2;
const colors = {
  WHITE: 'rgb(255, 255, 255)',
  RED: 'rgb(255, 100, 100)',
  GREEN: 'rgb(100, 255, 100)',
  BLUE: 'rgb(100, 100, 255)',
  LIGHT: 'rgba(250, 201, 137, 50)',
};

document.querySelector('#sleep-time-form').addEventListener('submit', function(e) {
  e.preventDefault();
  const val = parseInt(document.querySelector('#sleep-time-input').value, 10);
  sleepTime = val;
});

function setup() {
	frameRate(20);
	const canvasWidth = 400;
	const canvasHeight = 400;
	const canvas = createCanvas(canvasWidth, canvasHeight);
  canvas.parent('sketch');
  noLoop();
  nQueens();
}

function draw() {
  const { queens, current, queenInQuestion, clashedQueen } = state;
  
	background('#ccc');
	stroke(0);
	for (let i = 0; i < numRows; i++) {
		for (let j = 0; j < numCols; j++) {
      const cellToRender = { row: i, col: j };
			const x = (width / 4) + (rectSize + gutterSize) * cellToRender.col;
			const y = (height / 4) + (rectSize + gutterSize) * cellToRender.row;
      const cellHasQueen = queens
        .map((row, col) => ({ row, col }))
        .some(queen => _.isEqual(cellToRender, queen));
      
      fill(colors.WHITE);
      if (clashedQueen && liesBetween(cellToRender, current, clashedQueen)) {
        fill(colors.LIGHT);
      }
      if (_.isEqual(cellToRender, queenInQuestion)) {
        fill(colors.BLUE);
      }
      if (_.isEqual(cellToRender, clashedQueen)) {
        fill(colors.RED);
      }
      if (_.isEqual(cellToRender, current)) {
        fill(colors.GREEN);
      }
      
      rectMode(CENTER);
			rect(x, y, rectSize, rectSize);
      
      if (cellHasQueen) {
        textAlign(CENTER, CENTER);
        text(' 👑', x, y);
      }
		}
	}
}

async function nQueens() {
  /**
   * Keep all state read and writes, and all world param reads, within this function
   */
  
  let next = {
    col: 0,
    row: 0
  };

  // Through cols of a grid:
  //   - can go forwards and backwards (hence while loop)
  while (0 <= next.col && next.col < numCols) {

    // Through cells (rows) of a col:
    //   - must start from the cell after a placed queen (hence generator)
    //   - can go forwards only (hence for loop)
    //   - don't have to go till the end (hence break)
    let foundLocation = false;
    for (const cell of generateColCells(next, numRows - next.row)) {
      state.setCurrent(cell);
      state.setClashedQueen(null);
      state.setQueenInQuestion(null);
      await sleep(sleepTime);

      let isSafe = true;
      for (const [col, row] of state.queens.entries()) {
        const queen = { row, col };
        state.setQueenInQuestion(queen);
        await sleep(sleepTime);
        if (conflict(queen, state.current)) {
          state.setClashedQueen(queen);
          await sleep(sleepTime);
          isSafe = false;
          break;
        }
      }

      if (isSafe) {
        foundLocation = true;
        break;
      }
    }
    
    if (foundLocation) {
      // broke out of col loop early
      next = {
        col: state.current.col + 1,
        row: 0
      };
      state.setQueens([...state.queens, state.current.row]);
    } else {
      // reached end of col loop
      const [ lastQueenRow ] = state.queens.slice(-1);
      const lastQueenCol = state.queens.length - 1;
      
      // two queens might pop consecutively. Hence, backtrack to col of most recently popped queen, not just previous col
      next = {
        col: lastQueenCol,
        row: lastQueenRow + 1
      };
      state.setQueens(state.queens.slice(0, -1));
    }
    await sleep(sleepTime);
  }
  
  state.setCurrent(null);
  state.setQueenInQuestion(null);
}

function conflict(queen, current) {
  return (
    queen.row === current.row || 
    queen.col === current.col || 
    abs(current.row - queen.row) === abs(current.col - queen.col)
  );
}

function generateColCells(startCell, size) {
  const cells = new Array(size)
    .fill()
    .map((_, i) => {
      return {
        row: startCell.row + i,
        col: startCell.col
      };
    });
  
  return cells;
}

function sleep(ms) {
  return new Promise(resolve => setTimeout(resolve, ms));
}

function liesBetween(cellX, cellA, cellB) {
  /**
   * Returns whether cellX lies between cellA and cellB
   */
  const threshold = 0.1;
  const combinedDist = cellDist(cellA, cellX) + cellDist(cellX, cellB);
  const endPointsDist = cellDist(cellA, cellB);
  
  return combinedDist - endPointsDist < threshold;
}

function cellDist(cellA, cellB) {
  return sqrt(sq(cellA.row - cellB.row) + sq(cellA.col - cellB.col));
};
              
            
!
999px

Console