二次元配列を連番で繋げて埋めるロジック

[錦織]

二次元配列を連番で繋げて埋めたいのですが
ロジックが思い付かずこちらに記載させて頂きました。

１、二次元配列をすべて０で初期化する
２、特定の位置を１とする
３、２で決めた位置から左右上下に連番で数値を割り振る
４、３を繰り返し、すべてのマスを違う数字で埋める

みたいなことをしたいです。

例としましては以下のような形です。
※一筆でイメージ？です。

int array[4][4];

10,9,8,7
11,2,3,6
12,1,4,5
13,14,15,16

現在、近いロジックはできているのですが、
かなり無理やりにソースを書いており改修したいです。

現在のロジックでは、１～３を行い埋まらなくなったらリセットというのをWhile文で回しております。
盤面が小さければ特に問題ないのですが、大きくなればなるほどやばそうでして・・・。

[usao]

答えが無いときはどうするのでしょう？
例えば，
int array[3][3];
に対して，
>２、特定の位置を１とする
の段階で，スタート地点をarray[0][1]に指定されたときとか．

[錦織]

usao様

ご指摘ありがとうございます！
確かに・・・。定義を変えたら無限ループになってしまいました。

盤面サイズを最低4以上で考えていたので。
こちらありがとうございます。

現状、左右上下に移動できなくなった時の数字を見て
盤面のサイズ分だったら、whileを抜けるようにしております。

4以上ならその場合がなくなる気もするのですがどうなのでしょうか。

[たいちう]

真面目に考えると、かなり難しそうな問題なのですが、
盤面の大きさはどの程度までを想定しているのですか？
そして用途は何ですか？場合によってはベターな提案が得られるかも。


> 4以上ならその場合がなくなる気もするのですがどうなのでしょうか。

奇数×奇数なら起こりえるのです。
サイズと出発点が与えられたら、瞬時に判定できるのですが。

[錦織]

たいちう様

ありがとうございます。
なるほど・・・Whileで回避できていたのですが可能性があるのですね。
少し違うのですが、下記のようなゲームを作ろうとしております。

http://www.4gamer.net/games/173/G017371/20120704097/

自分の周囲にひとふでで書けるマスが何マスあるか？みたいなのを表示させたいです。

この問題を自動で作るのに連番で割り振り、
定義された範囲内のサイズで１番から分割していきたいと考えております。

[chop.chop]

つまり、この問題は

与えられたグラフにハミルトン路が存在するのかどうか（準ハミルトングラフかどうか）、つまり全ての頂点を一回のみ訪れるパスがあるかという問題に帰結できますね

wikiによると、ＮＰ完全らしいので多項式時間での解決は難しそうです……
こちらのサイトが分かりやすいのではないでしょうか
http://www.prefield.com/algorithm/graph ... _path.html

個人的には二次元配列よりは線形双方向リストを上下にもつなげてやったやつの方が作りやすいような気もしますね

[たいちう]

リンク先の説明でもどんなゲームか判りませんでした。

> 自分の周囲にひとふでで書けるマスが何マスあるか？みたいなのを表示させたいです。

この部分をもっと厳密に説明することはできますか？
私には伝わらないし、プログラムを作る以上、絶対必要です。

それと最大サイズについてですが、リンク先に表示されている6×6ですか？
この程度ならwhileを使った原始的な方法でも、あまり問題にならないのではないかと。