Comment by seanalltogether | Hacker News Reader

Comment by seanalltogether | Hacker News Reader

Parent Full thread

seanalltogether

Oddly enough, I found the 10x10 easier to solve then the 6x6 and the 8x8. After a couple play-throughs I think I know why. When trying to determine your next move, there's 3 options.

1. Look for a chance to play a block that wouldn't cause a chain of 3 colors together.

2. Look so see if the row or column has enough of a certain color in it.

3. Look to see if the row or column is a duplicate of another.

1 and 2 are easier to spot, but 3 is actually quite difficult and takes a lot of time to determine. On the 10x10, option 3 is almost never the determining case, probably because there are so many more possible configurations for a row or column, vs on a 6x6.

Those three heuristics seem to work for the puzzles on the site, due to a limitation of the site's puzzle generator. However, there exist puzzles of this type which cannot be solved using only those three heuristics.

Take this one, for instance:

  - O - - - -
  X - - O X -
  - - - - - -
  O - X - O -
  - - - - - O
  X - O - X -

This puzzle has the unique solution shown below, but none of your three heuristics will make any progress on it.

  O O X X O X
  X X O O X O
  X O O X O X
  O X X O O X
  O X X O X O
  X O O X X O

One of the ways you can solve this is to note that the square in the upper-left corner must be O. This is because if it were X, then there would be three adjacent Os in the first column. This insight is due to calebcjh@gmail.com.

Except that your puzzle has multiple solutions, so I'm guessing that's why it breaks the heuristics. The same would be true of a sudoku puzzle with too few starting numbers.

  O O X X O X
  X X O O X O
  O O X O X X
  O X X O O X
  X X O X O O
  X O O X X O

Your solution is not valid. The 3rd column and the last column are duplicates.

Reply on news.ycombinator.com