3
$\begingroup$

Weird question, I know, but this is in relation to an extension of Sudoku into a set of sequential, partisan games which always results in incompletable Sudoku. (i.e. the requirements of strategic play lead to choices that create "dead cells" in which no integer may be placed without violating the orthogonal constraints. Typical games on 9x9 seems to result in Sudoku with about a dozen dead cells.)

If this has been looked at, I'd appreciate any links (with the understanding that it probably hasn't, but that it never hurts to ask.)

Part of the impetus for the question is that we're trying to get a handle on the size of the gametrees. Enumeration of Sudoku doesn't really help because it doesn't take into account sequence or the number of incompletable grids of a given order.

You can read the concise rules for the "multiplayer partisan Sudoku" here.


Here are some screenshots to illustrate how "broken" Sudoku can be formed:

enter image description here
In this example, 5 placements result in an incompletable Sudoku--all the positions that can take an 8 are highlighted, but an 8 may no longer be legally placed in the center Region. 5 placements is the minimum I've be able to utilize to produce this effect on a 9x9, and there are a number of different 5 integer combinations that can produce it.

"Dead cells" in a typical game would look more like this:

A typical, basic M game with "dead" cells -- positions for 4's highlighted A typical, basic M game with "dead" cells -- positions for 5's highlighted
In this example you will note that neither a 5 nor a 4 can be legally placed in the bottom-center Region. For a fuller example of how partisan, strategic placement works in conjunction with Sudoku, see "Power of M"

$\endgroup$
3
$\begingroup$

There has been a bit of work on this problem, I think this 2012 result is the most well known. It basically says that if there are less than 17 filled entries, then a Sudoku cannot be uniquely completed (there will be more than one way to complete it).

http://www.ucd.ie/news/2012/01JAN12/100111-There-is-no-16-clue-or-less-Sudoku-mathematician-proves.html

$\endgroup$
  • $\begingroup$ Thank you! This is enormously helpful. "A brute force exhaustive search would not have been feasible" confirms my suspicions about the tractability complexity space. $\endgroup$ – DukeZhou Jul 5 '17 at 2:21
  • $\begingroup$ This has helped me make connection to wrong choices in Sudoku puzzle solving, which I hadn't previously because I'm approaching the construct from the opposite direction. $\endgroup$ – DukeZhou Jul 5 '17 at 2:31
  • 1
    $\begingroup$ Thanks for this news item. I knew that Gary McGuire was working on this seriously. But the last time I chatted with him about it was in 2008 or thereabouts. $\endgroup$ – Jyrki Lahtonen Jul 5 '17 at 4:52

protected by Community Jul 5 '17 at 2:45

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.