Workshop › 15 Puzzle › Step 18 of 27

Which boards can be solved?

What we are doing

Half of all arrangements of this puzzle can never be solved. A rule tells them apart: count the pairs of tiles in the wrong order, add the gap's row counted from the bottom; the board can be solved exactly when the sum is odd. solvable(list) checks it, so we can prove our shuffle keeps its promise.

```js
// A position can be solved when the number of pairs out of order, plus the gap's row counted from the bottom, is odd.
function solvable(list) {
  const numbers = list.filter((t) => t !== 0)
  let inversions = 0
  for (let a = 0; a < numbers.length; a++) {
    for (let b = a + 1; b < numbers.length; b++) if (numbers[a] > numbers[b]) inversions++
  }
  const gapRowFromBottom = N - rowOf(list.indexOf(0))
  return (inversions + gapRowFromBottom) % 2 === 1
}
```

What it means

numbers is the board without the gap.
Two loops compare every number with every number after it; a bigger one first is an inversion.
The gap's row from the bottom is N - row (1 for the bottom row).
% 2 === 1 asks whether the sum is odd.

Your turn

Above function reset(), write the comment and solvable, and leave an empty line. Press Run.

Skills: Loops

← Shuffle with real slides Is it solved? →

All steps