list of heuristics used
-: implemented
*: not implemented (yet)

KEY

level 1: trivial, immediate: can spot this by looking at one
         cell and its immediate neighbourhood
level 2: easy, almost immediate: can spot this with doing a
         minimum of search through slightly more distant
         cells.
level 3: intermediate: need to consider a larger area,
         possibly the entire board. heuristics with runtime
         Theta(n^4) will NOT go here.
level 4: more powerful search needed, might need to search
         through the entire board multiple times, runtime
         can be exponential.
level 5: advanced stuff. runtime: 2^(runtime from level 4)

AKARI (NP-complete)

level 1 (trivial, immediate)

- if a wall already has its n lights, or it will have n lights
  after lighting up all adjacent free cells, fill in all
  free neighbours with empty and light, respectively.

level 2 (easy, almost immediate)

- if a light diagonally adjacent to a wall causes that wall
  to not being able to fulfill its number of required adjacent
  lights: that cell must be empty.
- if there is an unlit empty cell and only one unfilled cell
  which can reach it, that cell must be light.
- if an unfilled cell can't see any other unfilled cells,
  it must contain bulb.

level 3 (intermediate)

* if putting a bulb on a cell makes it impossible to light up
  some cell on the board, that cell must be empty.
  (level 5 contradiction also accomplishes this, only slower)
* check if there exist two walls each having two possible light sites,
  forcing all other cells in two lanes to be empty

level 4

* if there are multiple ways of placing bulb and all of them light up the same
  cells and none are next to numbers, then none of these cells can contain bulb
  (must be empty) or the unique solution rule is violated

level 5 (advanced)

- for a cell: assume that it has bulb, then fill in greedily.
  then, assume it's empty, fill in greedily. for each cell that
  were filled in similarly for both, then the cell should be
  filled in like this. in addition, if any of the assumptions
  cause a contradiction, the cell must be filled in the other
  way.

HASHIWOKAKERO (np-complete)

level 1

- if there is only one way to fill in the remaining edges near a node, do it.
- if a node has n available edges and its number is 2n-1 or higher, it must
  have at least one edge in each direction.

level 2

- if a 2 has only two ways and one of the ways is towards 1 or 2, then the
  other way must have an edge.
- if a 1 has only one way to a non-1, then there must be an edge towards it.
- if not putting an edge makes it impossible to fulfill the node, then the edge
  must be there.

level 3

- if a node has one edge left, and each move except one causes an illegal
  position (more specifically: disconnected subgraphs) then do the only legal
  move
* try all ways of distributing edges. apply the intersection (minimum) of all
  legal ways.

level 4

level 5

- try all ways of distributing edges around a node, then solve greedily. then
  take the min of all ways to put edges and apply it.

HEYAWAKE (NP-complete)

level 1 (trivial, immediate)

- if a numbered region has enough walls, then the rest of the
  cells must be empty.
- if a numbered region has number of walls + unfilled equal to
  its number, then the rest of the cells must be wall.
- mark unfilled cells next to a wall as empty
- identify combinations of rectangle shapes, numbers and whether
  they are near a wall (n*m-i, n*m rectangle with number i)
  - 2x2-2 in a corner
  - 2x2-2 
  - 3x2-3 with the 3 side at the edge
  - 3x3-5
  - 3x3-4, mark empty
  - nx2-n (n>2), mark n-2 empty in neighbouring regions
  - (n*2+1)x1

level 2 (almost immediate)

- if making a cell empty causes a strip of empty passing through
  >=2 borders, then the cell must be wall.
- if an empty cell is surrounded by three walls, the fourth must
  be empty.

level 3 (intermediate)

- try all combinations of filling in a numbered region. only
  check if for adjacent walls and surrounded 1x1 within the
  region. across all non-rejected combinations, take the
  intersection of these (ie, only fill in cells filled in
  the same way for all combinations). only attempt this
  heuristic if (regsize choose regnum) is below a certain
  number.
* check all pairs of regions to find:
  * neighbouring 3x3-4 and 3x3-4: fill in as #  |  #
                                              # | #
                                             #  |  #

level 4

- if placing a wall in a cell causes two regions to be
  disconnected, then the cell must be empty ("empty
  articulation point")

level 5

- for a cell: assume that it is blocked, then fill in greedily.
  then, assume it is blank, fill in greedily. for each cell that
  were filled in similarly for both, then the cell should be
  filled in like this. in addition, if any of the assumptions
  cause a contradiction, then the cell must be filled in the
  other way.
- try all combinations of filling in a numbered region. reject
  all combinations causing disconnection, strip crossing >=2
  borders and adjacent walls. fill in the intersection of
  all these combinations. NB, do not run this heuristic if
  regsize choose regnum is larger than some constant.

HITORI

level 1

- if a value occurs once in its row and column, it's never blocked
- if there are three adjacent equal values in a row/column, 1 and 3 must be
  blocked, while 2 must be empty
- all cells adjacent to a wall must be empty

level 2

- if a row/column has two or more of a number and one is filled in wih
  empty, the rest must be wall

level 3

level 4

- if placing a wall in a cell causes the empty area to be disconnected, then
  that cell must be empty

level 5
- assume that a cell is empty or wall, then fill in greedily (using heuristics
  up to level 3) and take intersection or hope for contradiction.
- same as above, but can use level 4 heuristics

KUROMASU

level 1
- all cells next to blocked must be empty

level 2
- if placing blocked tightly in all 4 directions results in the number being
  satisfied, then fill in blocked like this
- if placing empty as far as possible in all 4 directions results in the
  number being satisfied, then fill in empty like this
- if three sides of a number are done (streak of empty/other numbers, followed
  by blocked or wall) then the fourth side is given

level 3
- if placing empty or blocked causes illegal board (according to veribyboard),
  then the cell must be filled in the other way (by contradiction)

level 4
- try all ways of extending from a number in all directions. take intersection
  of all legal positions (according to verifyboard)

level 5
- try all ways of extending from a number in all directions, do greedy and
  take intersection or achieve contradiction

MASYU

level 1

- if a black dot is near or 1 away from the border, then an edge must point
  away from the border
- if a white dot is near the border, an edge parallel to the border must go
  through it
- if there are three whites in a row, draw three parallel lines through them
  (orthogonal to the white dots)
- if there are two black dots in a row, draw 2 edges out from them, extended
  in the direction of adjacency
- if an edge through a white is extended on one side and can only turn one
  way on the other side, then make this turn. this heuristic automatically
  handles two whites in a row
- if it is impossible to extende an edge of length 2 from a black dot, then
  there must be an edge of length 2 in the opposite direction
- if a loose end can only grow to one place, let it
- if a loose end is within a white, let it continue through in the same
  direction
- if an edge can go though a white dot in only one direction, then do it
- if there is an edge of length 1 going out of a black dot, extend it
- line through a white dot such that it must turn in the next cell,
  and white 2 away or black 3 away.
  white: 2-line must be orthogonal
  black: 2-line in opposite direction, from black
  TODO refomulate (level1beyondmustturn)
- two black dots of distance 2 away: if one has an edge pointing away,
  the other must also have it
- for the pattern *.oo, black must have edge away from oo

level 2

level 3

- if there are two possible moves from a loose end and one of them causes a
  closed loop which doesn't include all dots and edges, then the other
  move must be taken
- check if a move causes an odd number of loose ends in a region

level 4

- if there is an enclosing with 4 loose ends, two occurrences of two
  adjacent cells AB and CD, where both are adjacent to two spaces
  and there are no dots in the enclosing: then the connection should
  be AC BD or AD BC.

level 5

- try all ways of extending an edge and solve greedily and take
  intersection or hope for contradiction
- try both ways of making a straight line through o, solve greedily
  and take intersection
- try all ways of fulfilling black, solve greedily and take intersection

MINESWEEPER

level 1

- if the rest of the cells around a number can only be filled in one way,
  do it (the rest must be bomb or the rest must be empty)
- if there are 0 mines left, the rest of the cells must be empty (R0083 R0087).
  if there are n mines left and n unfilled cells, the rest must be mine (R0103)

level 2

- try all combinations of placing the mines around a number. reject those
  combinations that violate other numbers within a 5x5 area around the
  current number. then take intersection of all legal combinations. worst
  case is (8 choose 4)=70, so the boundedness of the total number of
  operations justifies level 2

level 3

level 4

level 5
- try all ways of placing mines around a number, then do greedy and
  apply intersection or reach contradiction

unformalized
- develop a heuristic for R0085, 2 mines left and 2 easy mines to be
  placed
- in general, my solver struggles on puzzles with mines left

verifyboard:
good levels for testing underestimate: R101
good levels for testing overestimate: R109

consider using this:
http://en.wikipedia.org/wiki/Board_puzzles_with_algebra_of_binary_variables

NURIKABE (NP-complete)

level 1 (trivial, immediate)

- surround cells containing 1 with walls.
- for 2x2 blocks containing 3 walls, set the 4th to be island.
- if a cell is adjacent to two numbers, it must be wall.
- if an unfilled cell is surrounded by wall, it must be wall.
- if there is an island of the same size as its number, all
  unfilled neighbouring cells must be wall.
* if an unfilled cell is surrounded by island, it must be
  island (not needed so far). (nb, apply only if there are blocked
  elsewhere)

level 2 (easy, almost immediate)

- if a cell is adjacent to two different islands (they both
  contain a number), it must be wall.
- if a wall region can only grow to one cell and not all walls
  have been placed, the one cell must be wall.
- if an island can only grow to one cell (and it's not done),
  then the cell must be island.
- if there is an enclosure containing a number and the
  enclosure is of the same size, all enclosed cells must be
  island.

level 3

- if an island is one less than its size and one cell is
  adjacent to all cells the island can grow to, that one
  cell must be wall.
- if a cell on the board cannot be reached by any island,
  it must be wall.
- if there is a cell where an island must pass in order to
  grow enough, it must be island ("island articulation point").
- if there is an island which, when grown maximally, reaches
  exactly its size, then let it do so.
- if there is an enclosed area with several blank cells,
  and exactly one must be blocked: if there is a blank cell
  such that making it black connects the existing blocked at least
  as strong as the other moves, then that cell must be blocked.
  also, for each blank in the enclosed area, every 2x2 area around it
  cannot have blanks outside the enclosing, as placing blocked in these
  squares will interfere with the connections. please note that it is
  impossible to have a tie here, as that indicates non-unique solutions.
  however, a tie can occur in level 5 because of a bad move, do don't
  cast a fatal error. NB, i'm not convinced of the correctness. currently
  i get no illegal states using this heuristic on my test suite.

level 4

- if there is a cell where a wall must pass in order to
  connect all walls, it must be wall ("wall articulation
  point").
- if an island can grow into a cell and cause another island
  to not be able to grow sufficiently, that cell must be wall.
- if there is a cell where a wall on it would cause another
  island to not be able to grow sufficiently, that cell must
  be island.
- find an enclosing with one numbered cell such that there
  cells adjacent to the border, and all cells next to the
  border are unfilled. also, if the numbered cell was a wall,
  it must not split the enclosing into multiple regions.
  find the boundary between unfilled/empty and walls.
  generate two sets: all id's of walls adjacent to the left
  boundary, and all id's of walls adjacent to the right
  boundary. if the intersection of the two id sets is empty,
  then all the border cells should be wall!
- match unnumbered islands! first off, give each number its
  unique id. from each island, do a bfs (which is allowed
  to pass through unnumbered islands). each time an
  unnumbered island is "hit", add the numbered island id
  to the unnumbered island's personal set of id's of
  numbered islands able to reach it (the island can be
  reached if size(numbered)+path+size(unnumbered)<=number.
  then, if there is an unfilled cell such that it borders
  to two islands with an empty intersection of island ids,
  then the cell must be wall.
  also, if it is legal to reach an unnumbered island in only
  one way via one cell, that cell must be empty.
* take intersection of all ways to put an island (including
  surrounding walls). if it is possible to find two disjoint
  growings of an island, then the intersection of island is
  empty (the intersection of walls might still be nonempty).
  the leaf of the backtracking should check if the final
  shape (including walls) doesn't violate basic rules (2x2
  wall, isolated enclosure with wall and unnumbered island,
  neighbouring islands closed with wrong number)
* if there is an unnumbered blank which can only be legally
  connected to one numbered tile: try all ways of connecting
  these and take the intersection. see above.
* if there is an unnumbered blank which can only be legally
  connected to one numbered tile: set the island id for this
  blank, and run the other island growth heuristic.
* for a group of (connected?) cells of size n>=2: assume in
  turn all 2^n combinations. do a non-deep check for illegal
  scenarios: 2x2 walls, disconnected walls, enclosed islands
  with wrong size, 0 or 2 numbers. if the subgroup of
  noncontradicting fillings has a cell filled in the same
  way across all fillings, then it must be filled in like
  that.

level 5

- for a cell: assume that it is blank, then fill in greedily.
  then, assume it's wall, fill in greedily. for each cell that
  were filled in similarly for both, then the cell should be
  filled in like this. in addition, if any of the assumptions
  cause a contradiction, the cell must be filled in the other
  way.
- for an island, try all ways to grow the island. for each way, assume that it
  is the correct way, then solve greedily. take the intersection of all legal
  resulting states. if a cell is filled in the same way for all these, then the
  cell must be filled in like that. NB, this heuristic is expected to be both
  rather powerful and extremely slow.
* each 2x2 cell must contain at least one blank. for a given 2x2 area
  containing no blank, assume in turn that each square is blank, and
  solve greedily. if all except one possibility leads to a contradiction, and
  there exist cells that are filled in the same way for each reached legal
  state, then that cell must be filled in like that. only run this heuristic
  on 2x2 areas containing no blanks and at most 2 blocked.
* if an unnumbered island can belong to n numbered islands:
  for each of the n islands, assume that the unnumbered island
  belongs to it, then solve greedily. if all but one leads
  to contradiction, then the unnumbered island belongs to the
  non-contradictory one. afterwards, run suitable unnumbered
  connection heuristic.
* for a group of (connected?) cells of size n>=2: assume in
  turn all 2^n combinations of filling in these cells. if a
  subset causes contradictions: check if the complementary
  subset of noncontradictory fillings have one cell filled
  in the same way. then, fill it in. also, if, for the non-
  contradictory subset, some cell gets filled in the same
  way for every combination, then it must be filled in like
  that.
* given an unnumbered island: identify all islands being
  able to reach it. take intersection of all ways for all
  islands to reach the island (might be too expensive).

level ? (unformalized heuristics)

* try to grow two or more islands simultaneously and take
  intersection?
* find a general area where only one island can grow in
  order to prevent 2x2 wall. use this in conjunction with
  intersection.
* try all ways to connect two walls. if only one way is
  legal, apply it.
* advanced reasoning on walls: check if a blank prevents a
  wall spanning tree (based on the number of allowed walls)
* given an isolated unnumbered island: identify all islands
  able to reach it. then check if there is an island such
  that all the other islands (when connecting to the
  isolated island) causes the island to not be able to grow
  to its desired size. then, the isolated island belongs to
  this island, and we can run intersection on the island
  and the isolated island. (?)

unsolved situations

check out these detailed walkthroughs:
056 http://fabpedigree.com/nurikabe/nuriks01.htm
060 http://fabpedigree.com/nurikabe/nuriks05.htm
063 064 http://fabpedigree.com/nurikabe/nuriks08.htm
066 http://fabpedigree.com/nurikabe/nuriks11.htm

PICROSS (NP-complete)

level 1

- if clue is 0, then all cells in row/column become empty
- if there is just one possible combination for a given row/column,
  apply it

level 2

level 3

level 4

- try all possibilities for a row/column and apply the intersection of
  all possibilities

level 5

- for each cell, assume filled/empty, solve greedily and take intersection
  and/or achieve contradiction
* try all legal combinations of filling in a row or column,
  then do greedy. then fill in the intersection of all these
  combinations.

SLITHERLINK (NP-complete)

see http://en.wikipedia.org/wiki/Slitherlink for a bucketload
of rules. make a general pattern searcher or something like
that.

level 1

- around 0, mark all edges as empty
- if a number has enough edges, the rest must be empty
- if a number has edges + unfilled == number, the rest must be
  edge
- a dot with 3 empty must have empty as its fourth neighbour
- a dot with two edges must have 2 empty
- a dot with 1 edge and 2 empty must have another edge
- 2 adjacent 3's: separate with edge, and x above/below middle
  edge
- 3 having one edge going into one of its 4 dots: fill in two
  edges around the 3 not adjacent to the incoming one
- 3 having one corner with 2 empty, the remaining around this
  corner should be edge
- diagonally adjacent 3's: "enclose" them
- adjacent 3 and 1 near border: put edge between 3 and border
- 2 in corner: two edges go away from 2 along border
- 1 having a corner with two outer edges empty: the other edges
  for this corner must be empty

level 2

* a diagonal 3 2 2 ... 2 3 must have the outside edges of 3
  filled with edge
- jordan curve theorem

level 3

level 4

- if placing an edge makes an illegal loop, it must be empty

level 5

- for one edge: assume edge, and assume empty. fill in
  greedily and do the usual stuff

YAJILIN

level 1

- if two arrows pointing the same way have one cell inbetween, then
  that cell must be blocked or it must have edges through it
- between two blocked separated by one gap there must be edge
- if an empty cell is adjacent to blocked (or an edge is already
  pointing into it) and there's only two ways to make an edge: it must be
  filled like that
- if an empty cell has only one legal edge, then it must be blocked
- if there are two adjacent empty cells with only two legal edges, then
  fill both cells with edges
- if an empty cell borders only blocked, arrows and empty cells with degree 2,
  then this cell must be blocked

level 2

- if there is just one way to fill in blocked in an interval between
  two arrows or one arrow and a wall, do it
- given an arrow which is fulfilled with blocked: if any cell only has
  two legal edges, the cell must be filled in this way

level 3

- if all possibilities of making an edge (except one) creates a loop
  which doesn't solve the level, then create the only edge that doesn't
* if there is only one way that prevents self-loop for a special case,
  then apply it.
  x -??    x|-??
  x| ?? => x| ?? (and all its rotations)
  x????    x????

level 4

- for each interval between two arrows, try all ways of placing
  blocked, check correctness with verifyboard and take the intersection
- find a loose end. try all ways of extending it. then, extend the edge
  further as long as it has only one possibility of expanding. if all
  combinations except one lead to an illegal position according to
  verifyboard, apply that one combination
* given an enclosing with only a few reachable spaces: try all ways of
  connecting all loose ends (and placing blocked, if necessary). if there
  are >=two ways of tying the same ends, then all of them are illegal due to
  the requirement of having a unique solution! check verifyboard and take the
  intersection of all legal ways. do not use the uniqueness criterium if one
  or more of the possibilities involve placing blocked in rows/columns with
  numbered arrows
* for each pair of (close) loose ends (within an enclosing), try all ways of
  connecting them, use verifyboard and apply the only correct possibility

level 5

- for each action in an empty cell (blocked and 6 ways of placing two edges),
  fill in greedily and take intersection
- for each interval between two arrows, try all ways of placing
  blocked, fill in greedily and take intersection
- for every way to extend a loose end by one edge, fill in greedily and take
  intersection

level ? (unformalized heuristics)
* deal with situations like this:
    stuff
  +--- ----+
  |        |
  +--  ----+
  closing the loop from above separates the loop from the rest of the
  stuff, avoid this somehow
* more specifically:
  xxx    xxx
  - - => --- (where x is blocked), since the other way of connecting the loose
  - -    --- ends isn't unique
  xxx    xxx
  (occurs in C096)
