0

これを間違って投稿した場合は申し訳ありません。しかし、私はこれを投稿する必要があるStackoverflowチャネルを知らなかったので、これが最適だと思いました。

ケンケンパズルを解いています。それは数独に非常に似ており、合計と演算子を持ついくつかのケージがあり、一意の番号を使用して充填ボックスを解決する必要があります。

パズルを解くために、ケージの合計値、使用するオペレーター、関連する広告ボックスなど、各ケージの値を取得できる入力があります。

バックトラッキングを使用して問題を解決するための私のアプローチによると：

  1. 入力を解析して、各ケージのクラスデータ構造を作成しています。

  2. 後で、ケージごとにクラスオブジェクトの配列を作成しています。

  3. その後、このパズルを解くためにバックトラッキングを使用してアルゴリズムを適用します。

コーディングを始める前に、ここの人々と話し合いたいと思っていました。彼らがプログラミングアプローチが正しいと思っているのか、それでもアプローチを変更する必要があるのか​​、あるいは彼らが私に解決策を提案したいのか。

4

1 に答える 1

1

バックトラックは、おそらくこの問題を解決するための最良の方法の1つだと思います。正直なところ、現時点ではこれ以上のことはわかりません。

アルゴリズムで何をするつもりなのか正確にはわかりません。ただし、バックトラック自体だけに頼るべきではないことをお勧めします。ケンケンが何であるかを知るためにウィキペディアの記事を読んだだけです。しかし、最初からバックトラックを改善することは可能であるように思われます。

バックトラックには、通常、スタックを使用します。したがって、おそらく、どのケージにどの番号を入れたかを示すオブジェクトのスタックがあります。これで、このスタックオブジェクトのそれぞれに、アルゴリズムが多数の可能性からこの番号を選択したかどうか、または他に選択肢がなかったためにアルゴリズムがこの場所でこの番号を選択することを余儀なくされたかどうかを示すプロパティを与えることができます。したがって、そのようなスタックの代わりに：

(2,2) 5
(1,1) 4
(0,0) 1

スタックは次のようになります。

(2,2) 5 CHOSEN
(1,1) 4 IMPLIED
(0,0) 1 CHOSEN

そして、ここで他の値を選択することはできないため、最後の「IMPLIED」にのみ戻る必要があります。また、他のすべての選択が間違っていることが判明した場合、何かが暗示されます。これがKenKenでどこまで可能かはわかりません。この場所では実際には数値が暗黙的ではありませんが、最初の選択によって、後でアルゴリズムがIMPLIEDを使用するように強制できないことを確認する必要があります。

于 2012-09-21T06:45:56.083 に答える