3^9の仮定は間違っています。これには、たとえば、両方のプレーヤーが各ターンにXまたはOを配置するため、不可能なXのみを持つボードが含まれます。
私の最初の考えは、（9 * 8 * 7 * 6 * 5 * 4 * 3 * 2）*2つの可能性があるということでした。最初のプレーヤーには9つの選択肢があり、2番目のプレーヤーには8つの選択肢があり、最初のプレーヤーには7つの選択肢があります。
現在、3 ^ 9は19863と9です！は362880であるため、これは明らかに優れたソリューションではありません。多くの「異なるシナリオ」は、実際にはまったく同じように見えます。それでも、19863ボードのセットアップの多くが無効であるという基本的な考えは残っています。
おそらく単純な数式で置き換えることができるこのコードは、これが移動したい位置の数であることを示しています。
<script>
a = permuteString( "X........" ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XO......." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOX......" ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXO....." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXOX...." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXOXO..." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXOXOX.." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
//Subset of the Array.prototype.slice() functionality for a string
function spliceString( s , i )
{
var a = s.split("");
a.splice( i , 1 );
return a.join("");
}
//Permute the possibilities, throw away equivalencies
function permuteString( s )
{
//Holds result
var result = {};
//Sanity
if( s.length < 2 ) return [];
//The atomic case, if AB is given return { AB : true , BA : true }
if( s.length == 2 )
{
result[s] = true;
result[s.charAt(1)+s.charAt(0)] = true;
return result;
}
//Enumerate
for( var head = 0 ; head < s.length ; head++ )
{
var o = permuteString( spliceString( s , head ) );
for ( key in o )
result[ s.charAt( head ) + key ] = true;
}
return result;
}
</script>
これにより、次の数値が得られます。1番目の動き：9 2番目の動き：72 3番目の動き：252 4番目の動き：756 5番目の動き：1260 6番目の動き：1680 7番目の動き：1260
したがって、合計5289の動きで、これはすでに終了したゲームや対称性をチェックすることさえありません。
これらの数値を使用すると、配列内の動きを検索できます。可能なすべてのゲームをループすることで、この配列を自分で生成できます。
T。