チックタックつま先テーブルのすべての組み合わせをハッシュ

Question

チックタックつま先モデルが勝者を持っているかどうかを判断するためのアルゴリズムに取り組んでいます。しかし、ちょっとひねりがあります - 関数has_won？複数回呼び出されています。その結果、私が読んでいる本のアルゴリズム問題の著者（Coding Interview）は、2^9の可能なテーブルのそれぞれを生成し、それらをテーブルにハッシングすることを示唆しています。

各順列に対して一意のキーを生成するために、各ボードを整数で表します（ボードは最初は文字配列です）。整数は次のように生成されます。（3^0）v0 +（3^1）v1 +（3^2）v2 + ... +（3^8）v8ここでvは空白なら0、それはXであり、Oならば2です。

私はこれに従っていません。彼女はなぜ彼女が何をしたのか理解しています。しかし、およそ20,000のボードに、同じ整数値のキー値をその表現と共有しない別のボードがないという保証はありますか？彼女は証拠を提示しなかったし、それがなぜ固有の番号なのか直感的に把握することはできない。

Answer 1

単純な例でどのように動作するか見てみましょう。ボードに2つのスペースしかないとします。私はそれが良いゲームではないことを知っていますが、数字コードがどのように機能するかを示すために、最初のステップとしてそれを使用しています。この場合、整数は、あなたの表記でV0とV1（0）Xを有する2つのスペースが空であるかどうかを教えて（1）又はO（2）を有する

(3^0)v0 + (3^1)v1 

あります。今例を列挙：左のスペースを埋めることだけで今すぐ右側のスペースを埋める3未満の数字を生成

_ _ (3^0) 0 + (3^1) 0 = 0 
X _ (3^0) 1 + (3^1) 0 = 1 
O _ (3^0) 2 + (3^1) 0 = 2 

ていることに注意してください。

_ X (3^0) 0 + (3^1) 1 = 3 
_ O (3^0) 0 + (3^1) 2 = 6 

右手スペースを埋めるには、3の倍数しか得られないことに注意してください。今は残りのことをやってください。

X X (3^0) 1 + (3^1) 1 = 4 
O X (3^0) 2 + (3^1) 1 = 5 
X O (3^0) 1 + (3^1) 2 = 7 
O O (3^0) 2 + (3^1) 2 = 8 

ここで、各構成が唯一の整数に対応することがわかります。さらに、整数除算によって整数から構成を取り出すことができます。最後の2番目のケースを取ります。7. 3で割って2を得、1の余りで2にします。2は右手の四角形の構成で、1は左の構成です。これは上記のすべての例で有効です。

3つ以上の正方形でこれを試しても、同じ結果が得られます。私がそれが本当であることを知っている理由と、あなたがあなたのポストで尋ねる証拠を得る方法は、基本3桁のシステムが各桁の状態をその桁の1つに保持することを認識することです。これはエンコーディングがどのように動作するのかということで、整数エンコーディングの各項が3の累乗を持つ理由です。これは、生成された整数が一意であることを示すのに十分です。

もう1つ考えられるのは、10個の状態のいずれかになりうる四角形を想像することです。その後、任意の通常のベース10数、例えば

234 

が1の状態と、各桁で一つだけの正方形を保ち、正方形の各設定は、あなたに1つだけ1台10数を与える9にこれらの0を呼び出します。あなたの投稿に記入した表記にこの番号を書きます。

(10^0) 4 + (10^1) 3 + (10^2) 2 = 234 

となり、v0 = 4、v1 = 3、v2 = 2となります。