petertseng

# https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/signpost.html
# This should work on every single puzzle generated,
# because this solver uses the same reasoning as that used by the generator to check for solvability:
# check for cells with only a single possible successor or a single possible predecessor.
#
# There are other techniques that can be used:
# * Search with distance > 1, for example check which cell will eventually allow 24 to connect to 27.
# * Naked groups and hidden groups:
#   * If N preds have N succs as their only possible succs, discard all other possible preds from those succs
#   * If N succs have N preds as their only possible preds, discard all other possible succs from those preds

petertseng

# http://www.logicgamesonline.com/lightsout/daily.php

def popcount(x)
  b = 0
  while x > 0
    x &= x - 1
    b += 1
  end
  b
end