algorithm - 8 ボール ゲームでビリヤードを効率的にラックアップする方法は?

Question

8ボールゲームのビリヤードボールのラッキングは複数のルールの下で行うことができるので、私が参照するラッキングは次のとおりです。

つまり、8 ボールが中央にあり、側面に沿ってストライプとベタが交互に配置されている必要があります。残りの 2 つのボール (ストライプとソリッド) は関係ありません。

ゲームを終えたばかりだと仮定して、ボールを集めてラックに置き、新しいゲームを開始するためにそれらを配置します。現在、それらはランダムな順序になっています。どのように進めますか？

_{免責事項：ペイントアートが続きます}

簡単なアプローチは、上 -> 下、左 -> 右の順に開始することです。

たとえば、1が正しい位置にあると仮定します。5ではなく、 と交換し2、次に(または ) と交換4しますが、を中央またはinの位置に移動したため、これはすでに非効率的です。つまり、最後にある必要がある場所ではありません。 .38484

コーナーでどのタイプのボールを作りたいかという決定もあります。事前にどうやって決めるの？すでに配置されているボールの数を考慮する必要がありますか? 私の例では、コーナーに灰色のものが必要な場合は、既に 3 つ配置されています (ボール 1、10、14)。角に白いものが必要な場合は、2 つだけ配置します (2,11)。これは重要ですか？

これを形式化するために、2私たちができる3つの操作：

• 2 つの隣接するボールを交換する
• 隣接していない 2 つのボールを交換する
• 回転ラック

両手を使用できるので、最初の操作を並列化できると仮定しましょう (同時に 2 つのボールを交換する) が、一度に交換できるのは隣接していないボール 2 つだけです。

(説明されている時間単位で) 時間を最小化するこのタスクに最適なアプローチはどれですか? これには貪欲が最適でしょうか？（私がそれらをラックに入れるとき、私はそれを行う方法だと思います）

編集：既存の（または以前の回答）に従って-コーナーにソリッドよりもストライプが多いということは、ストライドがコーナーを好むことを意味すると考えるかもしれません-それが真実ではないと言っているわけではありませんが、その仮定を行う場合はそれを証明してください.

Answer 1

ノート！この回答は、ローテーション要件の前に書かれました。あなた自身の注意で進んでください:)

これが私の最初の問題です。

最初に行うことは、外側のパリティを計算することです。「コーナーのストライプ」に適合する場合は +1、「コーナーのソリッド」に適合する場合は -1、8 ボールの場合は +0 です。これにより、+12 から -12 の範囲が得られ、より近い極限を目指します。(+0の場合、+12またはランダムに選択)

たとえば、これは +1 +1 +1 -1 -1 +1 -1 -1 -1 +1 +0 -1 であり、したがって -1 コーナーの傾いたソリッドです。

x o x x o
 x o x o
  8 x o
   o x
    o

次に行うことは、8 ボールを中央に移動することです。1 つのボールだけを所定の位置に移動する 1 つの隣接するスワップ (または、コーナーにある場合は隣接していない 1 つのボール) ではなく、2 つのボールを所定の位置に移動する 2 つの隣接するスワップを実行できる場合は、そうしてください。

x o x x o
 x 8 x o
  o x o
   o x
    o

8 のボールを移動した後、ボールを共有する 2 つの隣接するスワップのすべての組み合わせは、非隣接のスワップによって同じように生成される可能性があるため、一度に考慮する必要がある複雑さははるかに少なくなります。

残りのすべての動きをこの優先度で並べます。

-外側の隣接する 2 つのボールの交換は「4 の価値」です (最後のボールの場合は 2)。

- 隣接する 2 つのボール (1 つは外側) の交換は「2 の価値」です (最後のボールの場合は 1)。

-外側の 2 つのボールの交換は「2 の価値がある」

- 外側にある 2 つのボールの交換は「1 の価値がある」

そして、それらを上から下に実行します。

そこで、上の o を左に移動し (4)、右側の o を (2) に、左下の o を (2) に移動してから、上部の x を中央の o と入れ替えます (2)。 . 2-2-1 シリーズで 5 回のスワップを行うことになったので、3 回の移動です。

o x o x o
 x 8 x x
  o o o
   x x
    o

(特に、コーナーのストライプを狙っていれば、これは同じくらい速く解決されたでしょう。)

x x o o x
 o 8 o x
  o x o
   x o
    x

4ターンを要求するのは無理だと思いますが、まだ証明できていません。

別の実例:

これには +1 のパリティがあるため、コーナーのストライプを目指します。

8 o o o x
 o o o x
  o x x
   x x
    x

8 ボールをセンター x と交換 (1-)

x o o o x
 o o o x
  o 8 x
   x x
    x

外側の隣接する 2 つを入れ替え、4 ポイント (1-1)

x o o o x
 o o o x
  x 8 x
   o x
    x

隣接するエッジを中央にスワップ、2 ポイント (1-2-)

x o o o x
 o o x o
  x 8 x
   o x
    x

端から端まで交換、2 ポイント (1-2-1-)

x o x o x
 o o x o
  x 8 x
   o o
    x

3手。

編集:これは、最初の投稿の例では非常にうまく機能し、2つの動きで解決します:

これには +1 のパリティがあるため、コーナーのストライプを目指します。

x x o o x
 o o x o
  o o 8
   x x
    x

エッジの x で 8 をスワップし、次に中央で o でスワップする (2 つのエッジを解決する) (2-)

x x o o x
 o o x o
  o 8 x
   x o
    x

上下左右の隣接する o と x を入れ替える (4 つのエッジを解く) (2-2-)

x o x o x
 o o x o
  x 8 x
   o o
    x

2手。

Answer 2

あなたは2つの8つのボール、詐欺師を持っています。

与えられた例では、ソリューションは2つの動きを取ります：

2-5、3-8
3-4、11-12

最適な解決策は、動的計画法（DP）の問題を構成することによって最もよく見つかります。問題は固定費と不確実性のない多段階であるため、問題を最適に解決するDPマトリックスが存在します。

マトリックスを作成するには：対称性を考慮して、8ボールは9つの位置のいずれかになります。ソリッドは、約（14選択7）/ 2=1716のさまざまな方法で配置できます。つまり、ラック構成の総数は約1716 * 9=15,444です。したがって、15,444の異なる可能な状態があります。これらの状態のいずれかから他の状態に移行するためのコストを計算します。これにより、15,444 * 15,444セル、つまり約25億セルのマトリックスが作成されます。すべての最終状態のセルを識別します。マトリックスを解くために、開始状態から終了状態に到達するまで（または、現在の最小コストよりも大きいコスト合計に到達するまで）、幅優先探索を進めます。これを行うことにより、すべての最小コストのパスを確実に見つけることができます。

上記の解決策はやや単純であり、さまざまな方法で最適化して、より小さな行列を生成できることに注意してください。たとえば、回転対称を使用してセルの数を減らし、中心の低い位置の1つに8ボールがあることを除いて、正しいパスに1のコスト（ラックを回転させるため）を追加できます。

Pseudocode:

Create DP Matrix:

(1) determine number of possible arrangements, A, of balls
(2) for each arrangement, make a list of possible unique moves  
---- the possible moves are:  
------- rotating right  
------- rotating left  
------- exchanging any pair of balls  
------- exchanging any two pairs of adjacent balls  
(3) for each move in A store a pointer to the resulting arrangement  
(4) for each arrangment make an attribute indicating whether it is an end state  

Solve Problem  
(5) goto arrangement for starting position S  
(6) set best-cost-so-far (BCSF) variable to infinity
(6) breadth search from S, accumulating current cost CC as +1 for each transition
(7) if you reach an end state CC < BCSF, then set BCSF = CC and make solution list contain only the current path
(8) if you reach an end state CC = BCSF, then add path to solution list
(9) if CC > BCSF abandon branch and try next branch

The result will be a list of all possible solutions and the minimum cost BCSF.

Answer 3

15!/(7!7!1!)=51480可能なポジションがあります。これらのうち、4 つは最終的なものです。ボール 8 と 9 は交換でき、ストライプ/ソリッドは反転できます。これらの位置は距離 0 にあるとします。

これらの 4 つの位置のそれぞれについて、すべての可能な移動 (1 つのスワップまたは 2 つの隣接するスワップ) を生成します。前に見られなかったこれらの動きによって生成された各位置について、どの動きがそれを生成するために使用されたかを覚えておいて、これらの位置に距離 1 を与えます。次に、距離 1 のすべての位置に対して同じことを行い、新しい位置に距離 2 を与えます。新しいポジションがなくなるまでこれを行います。

これは、@DPenner が指摘したように、回転は常に隣接する動きに置き換えることができるという事実を利用しています。

スワップはそれ自体が逆であるため、ポジション A から B に移動する動きは、ポジション B を A に戻す動きでもあります。

したがって、最終的にはすべてのポジションのリストが作成され、最終ポジションではない各ポジションに対して、確実に最終ポジションに近づける移動が行われます。

少なくとも 4 手がかかるポジションは 232 あることがわかります。(編集: 私の隣接テーブルには以前にエラーが含まれていました。) 例:

      6-9,14-15     2-12       2-5,4-7       1-2
    x           x           x           x           o
   x x         x x         8 x         o x         x x
  x o x   =>  x o o   =>  x o o   =>  o 8 o   =>  o 8 o
 o o o x     o o x x     o o x x     x o x x     x o x x
o 8 o o x   o 8 o x o   o x o x o   o x o x o   o x o x o

4 手以上かかる初期位置はありません。

編集: 最初に 8 ボールを交換する戦略は最適ではありません。例えば：

         5-11     12-13,14-15    4-7,6-10
    x            x            x            x
   o o          o o          o o          o o
  o x o   =>   o 8 o   =>   o 8 o   =>   x 8 x
 x o x x      x o x x      x o x x      o o x o
8 x o x o    x x o x o    x o x o x    x o x o x

しかし、もっとうまくやることができます:

         3-11       1-2,3-5
    x            x            o
   o o          o 8          x x
  o x o   =>   o x o   =>   o 8 o
 x o x x      x o x x      x o x x
8 x o x o    o x o x o    o x o x o

問題は、コーナーの x の種類が間違っているため、手が失われることです。

むしろ戦略は、位置がずれているが、同じ種類であるか、すでに位置にあるために隣接するボールと交換できないボールを探すことです。コーナーは、隣接するスワップ オプションが最も少ないため、優先する必要があります。位置に適した種類のボールと交換する必要があります。最初のボールの最終位置にあるボールの種類が間違っている場合、間違った場所にある隣接するボールを選択する必要があります。そうすれば、その後の隣接するスワップで、それらのボールが正しい最終的な場所に配置されます。

上記の (カウンター) 例では、8 のボールが最終的な位置に到達するまで長いスワップが必要です。ただし、#5 の x は種類が間違っているため、代わりに、2 行目の 2 番目の隣接する o と交換します。

前の 4 つの移動の例は、次のように解決されます。

        11-2         12-5        13-3       9-10
    x           x           x           x           x
   x x         o x         o x         o o         o o
  x o x   =>  x o x   =>  x 8 x   =>  x 8 x   =>  x 8 x
 o o o x     o o o x     o o o x     o o o x     o o x o
o 8 o o x   x 8 o o x   x o o o x   x o x o x   x o x o x

最初のステップでは、左下隅にある o を選択します。最初の x は位置 2 にあります。次に #12 で 8 を選び、これを #5 に持ち帰ることができます。一番下の行の真ん中のoが次です。#3 の次の間違って配置された x と交換します。最後に、#9 と #10 を交換して、最終的なラックを取得します。以前とは道が違いますが、それでも4手でたどり着きました。

編集: もう 1 つのポイント: 隣接するスワップを実行するときは、両方のボールが最終的な位置にないものを優先する必要があります。その理由は、これは少なくとも全部で 2 つの移動が必要であることを意味するため、できるだけ早く最初の移動を行うのが最善です。

たとえば、問題のラックは、(2-4),(5,6) と (3-6),(12-13) の 2 つの手で解決できます。8 のボールが最初に最終位置に移動されましたが、交換された白いボールはまだ最終位置にありません。2 つの境界の交換 (2-4)、(12-13) が最初に行われた場合、最後のラックに到達するにはまだ 2 回の移動が必要であり、合計で次善の 3 回の移動が必要になります。

Answer 4

敬礼、最初に、これは非常に楽しくて興味深い問題だったと言わなければなりません。ラッキングの際には考えたこともありませんでしたが、合計 15 個のボールでは、いくつかの追加の動きは重要ではありません。

ラッキングの説明と画像から、次のルールが得られます。

1. コーナーは常に同じタイプ
2. 各辺の中央は常にコーナーと同じタイプです
3. コーナーに接触する 2 つのボールの各セットは、常に同じタイプ (およびコーナーと反対のタイプ) です。
4. 三角形の内側には常に 8 ボール、ストライプ、およびソリッドがあります (そして 8 ボールが上にあります)。
5. 側面では、互いに近くにあるボールは常に交互のタイプになります

で @DPenner が述べたようにLemma 1、ローテーションは、コストが同じであればスワップで置き換えることができるため、必要ありません。あなたがルービックのファンで、それらを使用することを選択した場合、必要なのは 1 つだけです。

4 回未満のスワップでは解決できません。(常に)

あなたの例の画像はこれを証明するのに最適です.どちらの方法でも、6つのカラーボールをその位置から取り除く必要があり、8ボール=>それは3½スワップであり、スワップには2つのボールが必要なため、4つのスワップに丸めます.
どうしてこれなの？
すべてのルールを満たしているわけではないため:

• [5,1,4] [2,6] [11,13] [10,12]お互いに近くにいることはできません (ブレーク 5)
• 8ball中央の三角形ではなく、側面にあります (ブレーク 4)
• [5,4] [6,12] [13,9]すべて同じタイプではありません（ブレイク3）、さらに[1,5,4]セットの場合はコーナーとは反対側（ブレイク3）ではありません。
• [2]コーナーと[11]同じタイプではありません (ブレーク 2)

アルゴリズム

第 1 ステップ: 8 ボールを固定する 8 ボール
を所定の位置に交換します。とにかくそこにある必要があります。
これが回転する唯一のチャンスです (8 ボールが三角形の内側から始まるが、位置が正しくない場合)

Count赤い位置にある同じタイプのボールが最も多い。
最多カウントのボールが残り、残りのスポットは交換する必要があります。

IF count is 3 {
    #inside triangle will choose 
    IF inside triangle has 2 of a kind, that type stays (in the red spots)
    ELSE pick random
}

スワップを開始します。

• コーナーを行う（交換が必要なボールを選び、コーナーで反対のボールを見つける）
• ミドルを行う（交換が必要なボールを選び、サイドの真ん中で反対のボールを見つける）
• コーナーとミドルが完了した場合、最後のスワップは内側の三角形にあります

あなたの例のデモ：

swap 8 with 3  #move1
count[stripe]=3 [6,13,9]  
count[solid]=3 [5,4,12]
highest count=3, checking inside, inside is correct, random pick: stripes stay
Pick 5, corners() correct, swap with middles(2)  #move2
Pick 4, corners() correct, swap with middles(11)  #move3
Pick 12, corners() correct, swap with middles(3)  #move4
Done.

ランダム ピックでソリッドを選択する場合:

Pick 6, swap with corners(10)  #move2
Pick 13, swap with corners(1)  #move3
Pick 9, swap with corners(14)  #move4
Done.

デモ 2:

3 を 7 に変更、「白いボール 8 番」をボール 15 番に置き換え

swap 8 with 3  #move1
count[stripe]=3 [6,13,9]  
count[solid]=3 [5,4,12]
highest count=3, checking inside, inside has 2 of a kind(stripes) => stripes stay
Pick 5, corners() correct, swap with middles(2)  #move2
Pick 4, corners() correct, swap with middles(11)  #move3
Pick 12, corners() correct, swap with middles(15)  #move4
Done.

Have fun!

PS:灰色の位置にあるアルゴリズム バリエーション #2も気に入るかもしれませんcountsが、実際のシナリオでは赤い点を使用する方が簡単であることがわかりました。