March 28, 2009 2:00 am

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.