二次元配列を特定の範囲内のサイズでランダムな形に分割する

[daruma]

二次元配列を特定の範囲内のサイズでランダムな形に分割したいのですが、よさそうなロジックが思いつきません。
こうしたら簡単にできそう！みたいなアドバイスを頂けないでしょうか。

例）３×３の二次元配列を２～４マスの範囲で分割する

1,2,3
1,2,3
2,2,3

例）４×４の二次元配列を２～４マスの範囲で分割する

1,1,1,2
3,3,1,2
4,3,3,2
4,4,5,5

みたいな感じです。
わかりにくくてすみません。

問題なのは範囲によって形が変わってしまう事、
全てのマスが埋めたいのですが埋まらないことが出てきてしまう事になります。

[usao]

オフトピック

最初は１マスずつばらばらの状態からくっつけていく感じでなんとかなりませんか．

例えば，3*3なら1マスな9個のグループから出発して…
隣接していて合併しても目標最大個数を超えないグループ対　をリストアップして
そのうちの　どれか　を選んで併合，
というのを繰り返していく感じ，というか．


>埋まらないことが出てきてしまう

これについては併合するグループを選ぶ際に，
・マスの個数が足りない　（目標最小個数に達していないやつを優先）
・隣接するマスが少ない　（最初は角や辺の場所から優先してくっつけていく．後回しにすると後で困りそうだから）
みたいな条件で優先順位を設けてどうにか回避できないかなぁ

[たいちう]

コード:

1マスの部屋で埋め尽くす;

for (;;) {
	if (全ての部屋が範囲内の大きさ) break;  // 完成
	if (許容範囲より大きい部屋がある) その部屋を1マスの部屋に分割;

	許容範囲より小さい部屋をランダムで1つ選ぶ;
	
	ターゲットの部屋の壁が壊せるか壊せないか調べる;
	// 壊せない壁とは、外周(A)、または、壊したら許容範囲外の部屋ができてしまう壁(B)

	if (壊せる壁がある)
		壊せる壁をランダムで1つ選んで壊す;
	else
		(B)をランダムで1つ選んで壊す;
}

証明はできないけど千日手のようなことにはならないと思います。
最初の配列が大きく、かつ、許容される範囲が狭い場合、
最終的に解決するとしても時間がかかってしまう恐れがあるので、
その場合は別の工夫が必要になるかもしれません。


> 問題なのは範囲によって形が変わってしまう事、
> 全てのマスが埋めたいのですが埋まらないことが出てきてしまう事になります。

範囲によって形が変わるのは当たり前なので、何が問題なのかわかりません。
私が何か見落としているようなら、ご指摘お願いします。

[usao]

>if (許容範囲より大きい部屋がある) その部屋を1マスの部屋に分割;

なるほど，余ったやつが出たら周辺を巻き込んで局所的にやりなおせばいいということですね．

…ちょっと，やってみました．
効率とかデータの管理方法だとか度外視して”やってみただけ”なのでひどいコードですが．（そのためかやたら長いw）

あまり試してないですが，簡単な問題は解けてる…のかな？

► スポイラーを表示

コード:

#include <iostream>
#include <vector>
#include <algorithm>

//２次元配列
const int W = 4;
const int H = 4;
unsigned int Map[H][W];

//作るべき部屋のサイズ範囲
const unsigned int MinRoomSize = 2;
const unsigned int MaxRoomSize = 4;

//作業用
const int MAP_SIZE = W*H;
unsigned int RoomSize[ MAP_SIZE ];  //RoomSize[部屋番号]で部屋のサイズ．ただしもはや存在しない部屋の値は0


//初期状態生成
void Initialize()
{
    unsigned int RoomNumber = 0;
    for( int y=0; y<H; y++ )
    {
        for( int x=0; x<W; x++ )
        {
            Map[y][x] = RoomNumber;
            ++RoomNumber;
        }
    }

    for( int i=0; i<MAP_SIZE; i++ )
    {   RoomSize[i] = 1;    }
}

//現状を出力
void PrintMap()
{
    for( int y=0; y<H; y++ )
    {
        printf( "%2u", Map[y][0] );
        for( int x=1; x<W; x++ )
        {   printf( ",%2u", Map[y][x] );    }
        printf( "\n" );
    }
    printf( "\n" );
}

//目標達成しているかどうか
bool Complete()
{
    for( unsigned int i=0; i<MAP_SIZE; i++ )
    {
        unsigned int s = RoomSize[i];
        if( s==0 )continue;
        if( s<MinRoomSize || MaxRoomSize<s )return false;
    }
    return true;
}

//サイズ最小な部屋の番号をひとつ返す
unsigned int GetSmallestRoom()
{
    unsigned int MinSize = std::numeric_limits<unsigned int>::max();
    for( unsigned int i=0; i<MAP_SIZE; i++ )
    {
        if( RoomSize[i]>0 && RoomSize[i]<MinSize )
        {   MinSize = RoomSize[i];  }
    }

    std::vector< unsigned int > Tmp;
    Tmp.reserve( MAP_SIZE );
    for( unsigned int i=0; i<MAP_SIZE; i++ )
    {
        if( RoomSize[i] == MinSize )
        {   Tmp.push_back( i ); }
    }

    std::random_shuffle( Tmp.begin(), Tmp.end() );
    return Tmp.front();
}

//２つの部屋を合併．
void IntegrateRoom( unsigned int RoomNum1, unsigned int RoomNum2 )
{
    //RoomNum1番側に取り込む
    RoomSize[ RoomNum1 ] += RoomSize[ RoomNum2 ];
    RoomSize[ RoomNum2 ] = 0;

    for( int y=0; y<H; y++ )
    {
        for( int x=0; x<W; x++ )
        {
            if( Map[y][x] == RoomNum2 )
            {   Map[y][x] = RoomNum1;   }
        }
    }
}

//RoomNum番の部屋に隣接する部屋を調査
void SearchNeighbor(
    unsigned int RoomNum,
    std::vector<unsigned int> &rDstSafeIntegratable,    //合併しても最大サイズを超えない部屋番号を格納
    std::vector<unsigned int> &rDstSizeOver //合併すると最大サイズを超える部屋番号を格納
    )
{
    const int dx[4] = { 0, -1, 1, 0 };
    const int dy[4] = { -1, 0, 0, 1 };

    rDstSafeIntegratable.clear();
    rDstSizeOver.clear();

    for( int y=0; y<H; y++ )
    {
        for( int x=0; x<W; x++ )
        {
            if( Map[y][x] != RoomNum )continue;

            for( int dir=0; dir<4; dir++ )
            {
                int xx = x + dx[dir];
                int yy = y + dy[dir];
                if( xx<0 || xx>=W || yy<0 || yy>=H )continue;
                unsigned int rn = Map[yy][xx];
                if( rn==RoomNum )continue;

                unsigned int IntegratedSize = RoomSize[RoomNum] + RoomSize[rn];
                if( IntegratedSize < MaxRoomSize )
                {   rDstSafeIntegratable.push_back( rn );   }
                else
                {   rDstSizeOver.push_back( rn );   }
            }
        }
    }

    std::sort( rDstSafeIntegratable.begin(), rDstSafeIntegratable.end() );
    rDstSafeIntegratable.erase( std::unique( rDstSafeIntegratable.begin(), rDstSafeIntegratable.end() ), rDstSafeIntegratable.end() );

    std::sort( rDstSizeOver.begin(), rDstSizeOver.end() );
    rDstSizeOver.erase( std::unique( rDstSizeOver.begin(), rDstSizeOver.end() ), rDstSizeOver.end() );
}

//サイズオーバーな部屋を探す
bool FindSizeOverRoom( unsigned int &rDstRoomNum )
{
    for( unsigned int i=0; i<MAP_SIZE; i++ )
    {
        if( RoomSize[i]>MaxRoomSize )
        {
            rDstRoomNum = i;
            return true;
        }
    }
    return false;
}

//RoomNum番の部屋をばらばらに解体する
void DestructRoom( unsigned int RoomNum )
{
    RoomSize[ RoomNum ] = 0;

    unsigned int NewRoomNum = 0;
    for( int y=0; y<H; y++ )
    {
        for( int x=0; x<W; x++ )
        {
            if( Map[y][x] != RoomNum )continue;

            while( RoomSize[NewRoomNum]>0 )
            {   ++NewRoomNum;   }

            Map[y][x] = NewRoomNum;
            RoomSize[NewRoomNum] = 1;
        }
    }
}

//main
int main()
{
    //乱数系列初期化
    //引数を変えれば結果が変わる
    std::srand( 10 );   //※std::random_shuffle()に影響するのはコレでいいのだろうか？

    //初期状態準備
    Initialize();
    printf( "初期状態\n" );
    PrintMap();

    //がんぱる
    std::vector< unsigned int > SafeIntegratableTgts;
    std::vector< unsigned int > SizeOverTgts;

    SafeIntegratableTgts.reserve( MAP_SIZE );
    SizeOverTgts.reserve( MAP_SIZE );

    unsigned int turn = 0;
    while( true )
    {
        ++turn;

        if( Complete() )
        {
            printf( "できた\n" );
            break;
        }
        if( turn > 100 )    //※どうしてもできないときの無限ループ防止
        {
            printf( "もうあきらめる\n" );
            break;
        }

        printf( "Turn %u\n", turn );

        unsigned int RoomNum1;
        if( FindSizeOverRoom( RoomNum1 ) )
        {
            printf( "Destruct Room%u(%u)\n", RoomNum1, RoomSize[RoomNum1] );
            DestructRoom( RoomNum1 );
        }
        else
        {
            RoomNum1 = GetSmallestRoom();
            SearchNeighbor( RoomNum1, SafeIntegratableTgts, SizeOverTgts );

            std::vector< unsigned int > &rTgts = ( !SafeIntegratableTgts.empty()  ?  SafeIntegratableTgts  :  SizeOverTgts );
            std::random_shuffle( rTgts.begin(), rTgts.end() );
            unsigned int RoomNum2 = rTgts.front();
        
            printf( "Room%u(%u) + Room%u(%u)\n", RoomNum1, RoomSize[RoomNum1], RoomNum2, RoomSize[RoomNum2] );
            if( SafeIntegratableTgts.empty() ){ printf( "(Size Over)\n" );  }

            IntegrateRoom( RoomNum1, RoomNum2 );
        }

        PrintMap();
    }

    //
    printf( "\n==Enter to quit==\n" );
    getchar();  //※Enter押すまで待つ用
    return 0;
}

[かずま]

サイズは、縦も横も 15までです。

コード:

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <ctime>

char t[][4] = {
    {2,1},       {2,16},       {3,1,2},      {3,16,32},
    {3,1,16},    {3,1,17},     {3,16,17},    {3,15,16},
    {4,1,2,3},   {4,16,32,48}, {4,1,16,17},
    {4,1,16,32}, {4,1,17,33},  {4,16,32,33}, {4,16,31,32},
    {4,1,2,16},  {4,1,2,16},   {4,16,17,18}, {4,14,15,16},
    {4,1,2,17},  {4,16,17,32}, {4,15,16,17}, {4,15,16,32},
    {4,1,17,18}, {4,15,16,31}, {4,1,15,16},  {4,16,17,33},
};
cont int N = sizeof(t) / sizeof(t[0]);

int b[16 * 16], row, col;

void print()
{
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++)
            std::cout << std::setw(4) << b[i*16 + j];
        std::endl(std::cout);
    }
}

int ok(int r, int c, int i)
{
    int n = t[i][0];
    for (int j = 1; j < n; j++)
        if (b[r*16 + c + t[i][j]]) return 0;
    return 1;
}

void set(int r, int c, int i, int k)
{
    b[r*16 + c] = k;
    int n = t[i][0];
    for (int j = 1; j < n; j++)
        b[r*16 + c + t[i][j]] = k; 
}

void step(int r, int c, int k)
{
    if (c == col) {
        c = 0;
        if (++r == row) { print(); exit(0); }
    }
    if (b[r*16 + c]) step(r, c+1, k);
    else {
        b[r*16 + c] = k;
        for (int i = 0; i < N; i++) {
            if (ok(r, c, i)) {
                set(r, c, i, k);
                step(r, c+1, k+1);
                set(r, c, i, 0);
            }
        }
        b[r*16 + c] = 0;
    }
}

int main()
{
    std::srand(std::time(0));
    std::random_shuffle(t, t+N);
    std::cout << "input row and col: ";
    std::cin >> row >> col;
    if (!std::cin || row >= 16 || col >= 16) return 1;
    for (int i = 0; i < row; i++) b[i*16 + col] = 999;
    for (int i = 0; i <= col; i++) b[row*16 + i] = 999;
    step(0, 0, 1);
}

実行結果

コード:

input row and col: 5 5
   1   2   3   3   3
   1   2   3   4   5
   6   2   2   4   5
   6   7   7   4   4
   7   7   8   8   8

[かずま]

サイズは、縦も横も 15までです。

訂正です。
15行目 cont --> const
52行目と 60行目は不要(38行目があるから)
67行目の random_shuffle() は 53行目の for文の前に移した方がよい

[かずま]

67行目の random_shuffle() は 53行目の for文の前に移した方がよい

すみません。訂正の訂正です。
random_shuffle() をそこに移動させてはいけないことが分かりました。

[たいちう]

かずまさん。全くわかりません。
お手数ですが簡単な説明をお願いできるでしょうか。
(説明を聞いてもわからなければごめんなさい。
私以外にもわからない人が多くいると思うので、
その場合はご容赦ください。)

私にとって新しい世界が開けるかもしれませんが、
もう少し考えて無理なら諦めます。

[かずま]

コード:

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <ctime>

char t[][4] = {
     {2,1},       {2,16},       {3,1,2},      {3,16,32},
     {3,1,16},    {3,1,17},     {3,16,17},    {3,15,16},
     {4,1,2,3},   {4,16,32,48}, {4,1,16,17},
     {4,1,16,32}, {4,1,17,33},  {4,16,32,33}, {4,16,31,32},
     {4,1,2,16},  {4,1,2,16},   {4,16,17,18}, {4,14,15,16},
     {4,1,2,17},  {4,16,17,32}, {4,15,16,17}, {4,15,16,32},
     {4,1,17,18}, {4,15,16,31}, {4,1,15,16},  {4,16,17,33},
};
const int N = sizeof(t) / sizeof(t[0]);

int b[16 * 16], row, col;

void print()
{
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++)
            std::cout << std::setw(4) << b[i*16 + j];
        std::endl(std::cout);
    }
    std::cout << "--------------------\n";
    std::cin.get();
}

int ok(int r, int c, int i)
{
    int n = t[i][0];
    for (int j = 1; j < n; j++)
        if (b[r*16 + c + t[i][j]]) return 0;
    return 1;
}

void set(int r, int c, int i, int k)
{
    b[r*16 + c] = k;
    int n = t[i][0];
    for (int j = 1; j < n; j++)
        b[r*16 + c + t[i][j]] = k; 
}

void step(int r, int c, int k)
{
    if (c == col) {
        c = 0;
        if (++r == row) { print(); return; }
    }
    if (b[r*16 + c])
        step(r, c+1, k);
    else
        for (int i = 0; i < N; i++) {
            if (ok(r, c, i)) {
                set(r, c, i, k);
                step(r, c+1, k+1);
                set(r, c, i, 0);
            }
        }
}

int main()
{
    std::srand(std::time(0));
    std::random_shuffle(t, t+N);
    std::cout << "input row and col: ";
    std::cin >> row >> col;
    if (!std::cin || row >= 16 || col >= 16) return 1;
    for (int i = 0; i < row; i++) b[i*16 + col] = 999;
    for (int i = 0; i <= col; i++) b[row*16 + i] = 999;
    step(0, 0, 1);
}

b は 16 x 16 の 2次元配列を 1次元配列に置き換えたものです。
row = 3, col = 4 なら

コード:

    0    0    0    0  999
    0    0    0    0  999
    0    0    0    0  999
  999  999  999  999  999

と初期化されます。

r行 c列のマスは、b[r*16 + c] で参照できます。
その右隣は +1、下は +16 です。

この領域 b を 2～4マスの部分領域で埋めたいわけです。

コード:

2マスは、次の 2通り。
+--+--+  +--+
| 0| 1|  | 0|
+--+--+  +--+
         |16|
         +--+

3マスは、次の 6通り。
+--+--+--+  +--+  +--+--+  +--+--+  +--+        +--+
| 0| 1| 2|  | 0|  | 0| 1|  | 0| 1|  | 0|        | 0|
+--+--+--+  +--+  +--+--+  +--+--+  +--+--+  +--+--+
            |16|  |16|        |17|  |16|17|  |15|16|
            +--+  +--+        +--+  +--+--+  +--+--+
            |32|
            +--+

4マスは、19通り。自分で書き出してみてください。

これが t[N][4] で、N = 27 のパターンがあります。
0 は不要なので、ここにマスのサイズを入れています。

あとは、b[0] から順番に、
b[r*16+c] が 0 でなければ、すでに埋まっているので次の b[r*16+c+1] に行く。
b[r*16+c] が 0 なら、そこに 27通りのパターンのうちの一つ t が置けるか
どうか ok()で 見て、置ければ set(r, c, i, k) で置き、右隣に (k+1)番目の
部分領域を置きに行きます。戻ってきたら、set(r, c, i, 0) で tを外します。

r = row, c = col になったら、全部埋まったので print() で表示します。
ここで exit() で終了する代わりに、return で戻ると全パターンを表示します。
cin.get() で止まるので、Enterキーを押して、次の解を表示します。

$ echo 3 3 | ./a.out >file で、Enterキーなしに全パターンをファイルに書き出せま
す。

[たいちう]

かずまさん。おかげさまで理解できました。
(読めるようになったけど、書ける日が来るだろうか。)

このデータの持ち方は私では思いつきませんね。
再帰で全ての解を得る方法も考えていましたが、
乱数を使うことで全ての解をもつ必要もなくなると。
最後に番兵(?)と{3,15,16}のような形の処理も勉強になりました。

丁寧な説明ありがとうございました。

[かずま]

バグがありました。

コード:

    for (int i = 0; i < row; i++) b[i*16 + col] = 999;

を

コード:

	for (int i = 0; i < row; i++) b[i*16 + col] = b[i*16 + 15] = 999;

に修正します。

[かずま]

さらにバグは続きます。

コード:

	 {4,1,2,16},  {4,1,2,16},   {4,16,17,18}, {4,14,15,16},

同じ形がありますね。これを次のように修正します。

コード:

	 {4,1,2,16},  {4,1,2,18},   {4,16,17,18}, {4,14,15,16},