Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Here is an example of a case that backtracking is required where there is only one solution:

      11110
      -----
   11|....0
    2|....0
    0|00000
    0|00000
    0|00000

The sequential constraint solver fails here even though the deduction required is trivial. The first row can only be 10010 or else the 2 in the second row isn't possible.

A more difficult problem is the following:

      11 1 
      11211
      -----
    1|..0..
    2|..0..
   11|.010.
    4|.111.
    0|00000

There are two choices at this point. One option is:

      11 1 
      11211
      -----
    1|..0..
    2|..0..
   11|.010.
    4|01111
    0|00000
And we immediately run into a problem with the 3rd row, 1st col which needs to be both 1 and 0.

The other solves the problem immediately as all remaining squares are immediately specified by a single constraint.

      11 1 
      11211
      -----
    1|00010
    2|11000
   11|00101
    4|11110
    0|00000

Compared to most sudoku solves, I think this is pretty straightforward (you only need to look ahead one move to one other square). I think this would be fair game to give as a problem.

Of all the games with a unique solution that the sequential solver can't do that I looked at, almost all fell somewhere in the range of difficulty between these two. I didn't find any that require more than one move lookahead.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: