Friday, March 13, 2009

Complexity of Ken Ken Game

I came across this puzzle named Ken Ken. It is Sudoku-type puzzle with arithmetic constraints. Here is a complexity question :
  • Is solving n x n Ken Ken puzzle NP-complete ?
NP-completeness results are known for similar games like Sudoku. Here is a paper on mathematics of Septoku. Here is David Eppstein's list of games with complexity results.

No comments: