Thursday 12 April 2018

combinatorics - How to determine the size of the complete game tree for basic [M]?

You can read the rules of the game here, or actually play it free on the mobile mbrane app, but it's not required to address the question.



Essentially: players take turns placing integers onto an empty Sudoku until no more integers may be legally placed.



Part of the complete gametree involves ~6.67x10²¹ complete Sudoku, reduced for rotation but not substitution because the integers have magnitude.



(Full disclosure: this part of the tree is almost entirely meaningless as strategic placement of the integers, influenced by the topology, seems to always result in incompletable Sudoku, which leads to the real problem.)




Here is an image to illustrate how the dead sectors occur, for those interested. (x's mark the dead sectors):



Typical basic [M] game displaying dead sectors



At some point I plan to figure out how to derive total number of broken Sudoku--dead sectors can be created with as few as 9 placements--but for now I just want to make sure I understand how the exponential expansion of placement sequence interacts mathematically with the factorial structure of Sudoku, and the proper notation.




  • What is the size of the basic [M] gametree, assuming only completable Sudoku?




Alternately:




  • How to derive the complete gametree size of basic [M] on a 2x2(2x2) gameboard?



The second example on 2x2(2x2) can actually be checked!



Sorry if this is a really basic question, but I only have basic maths, so be kind! (I'm working up to a question on how to determine the complexity class of the basic game:)

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...