質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.47%

  • JavaScript

    17034questions

    JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

すべてのマスを訪れる回り方を求める

解決済

回答 4

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 333

okamot

score 1

 前提・実現したいこと

(Javascript)将棋のコマとして「銅」というコマを新しく考える.このコマは斜め左上,下,右のいずれかに一マス移動することができる.今,大きさn x n の将棋盤の適当な位置から銅がスタートして,この将棋盤のすべてのマスをちょうど一回だけ訪れる回り方を求めることにする.銅はスタートした位置に戻ってくる必要はない.
このような条件を満たすときマスの番号を順に入れた配列の配列を返すような関数 bronze(n) を定義せよ.
マスの番号は0からn^2 - 1とし,左上から順に横方向にスキャンしながら番号付けし,右下で終わるようにせよ.

function bronze(n)
{

    var LEFTUP = 0
    var RIGHT = 1
    var DOWN = 2

    function make_masu(n)
    {
        var state = []
        var i
        for(i = 0;i < n * n;i++) state[i] = 0

        return state
    }

    function move(state,now,move)
    {
        var now_x = now % n
        var now_y = Math.floor(now / n)

        if (move == DOWN && now_y > n - 1){
            state[now + n] = 1
            now = now + n
        } else if (move == LEFTUP && 0 < now_y && 0 < now_x){
            state[now - n - 1] = 1
            now = now - n - 1
        } else if (move == RIGHT && now_x < n - 1){
            state[now + 1] = 1
            now = now + 1
        }
        return state
    }
    function next_move(state,now)
    {

    }
    function search(start)
    {

    }
}


マスの状態をstateで与えてstateが1の場所は一度訪れたことがある場所という感じで考えているのですが,探索の仕方のアイデアが思いつかないです。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • mts10806

    2018/06/20 18:27

    学校の課題か何かでしょうか。課題代行や宿題代行のサイトではないので、質問の表現には気をつけていただけたらと。 https://teratail.com/help/question-tips#questionTips1-1 >作業依頼のような投稿をして、課題や仕事を無償でやってもらえる場ではありません。

    キャンセル

  • 退会済みユーザー

    2018/06/20 20:10

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

  • okamot

    2018/06/20 20:43

    すみませんでした。課題として出された問題でした、ありがたいことに回答を頂いたので自分でもう一度考えてみたいと思います。

    キャンセル

回答 4

checkベストアンサー

+5

探索の仕方(アルゴリズム)を考えるところから課題でしょうから、アルゴリズムの見つけ方について考えてみましょう。

端的な回答

  1. 1x1の場合、2x2の場合、3x3の場合について自分で総当たりで答えを作ってみる。
  2. その際に自分が考えたことをプログラムに落とし込み、総当たりでたどり着いた答えと同じ答えをを返すプログラム作ってみる。(簡単な1x1の場合から順にプログラムの処理を足していく)
  3. そのプログラムが確実に総当たり出来ているか確認する

と、答えにたどり着けます。


以下、考え方的なもの

まず、この問題が何を求めているかを正確に定義するところから始めないと何を考えればいいかわからなくなります。

課題の定義
私の理解としてはこの課題は
「NxNのマス目があり、一定のルールでのみ動ける銅がある場合に、Nを定義した場合に一筆書き出来るルートを返す関数を作成せよ」
です。

解が複数あった場合や、解が無い場合の挙動は定義されていないので好きに考えて良いという事でしょう。
「解が無いケースは想定しない」、「複数ある場合は最初に見つかったものだけを返す」とすれば簡単そうです。

また、計算量について指定は無いのでいくら時間がかかっても答えが出ればOKと考えて良いハズです。

スタート地点を「訪れた」と判定するかは曖昧ですが恐らく訪問扱いにするんだと思います。
(このあたりは問題の日本語の不備を指摘して条件をこちらで定義してから回答しましょう。出題者の性格や能力に問題があれば減点されるかもしれませんが、不正確な前提でプログラムを作るという悪癖をつけるよりはマシです)

  • 授業中に前提条件の説明などがあった場合はそれを加味してください。

ゴールの定義
とりあえず簡単そうなところをゴールとしましょう。
探索で簡単なのは総当たりです。
(Nの範囲が指定されていないので、総当たり以外の方法だとアルゴリズムが論理的に正しいである証明を添付する必要が発生するでしょう。)

これによってゴールは

  1. 定められた範囲について、定められた動き方をする駒について全パターンの移動を試行する
  2. 終了条件を満たした場合は正解として移動ルートを返却する。

の両方を満たすプログラムの作成ということになりました。

ゴールの分解
ゴールについて思いつく限り条件を詳細化していきます。

  1. 定められた範囲について、定められた動き方をする駒について全パターンの移動を施行する
    →「全パターン」を構成する要素とは?
    →「全」とは?どれだけ試行したら全パターンと言える?

  2. 試行中に終了条件を満たした場合は正解として移動ルートを返却する
    →何を持って終了条件とするのか?

ゴールの分解は割と難しいというか、アルゴリズムそのものになるので、先に具体例から考えてみましょう。

具体例を考えてみる

どうすれば総当たり出来るかについて、具体例を考えてみて具体例から汎用的なアルゴリズムを考えてみましょう。
いきなり9x9で考えると訳が分からなくなると思います。
まずは最小の1x1で考えてみましょう。

1x1だと何も考えなくても
スタート地点のみを訪れるルートが正解で、「全パターン」は1パターンだけだとわかります。
この場合、どこにも移動しなくても修了条件を満たしていることもわかります論点がわかります。

ではここで、
1x1の場合に正解として返すべき値はなんでしょうか?
なぜ全パターンが一つだけだと判断できたでしょうか?
1x1の場合の「終了条件」は何でしょうか?

この三つをプログラムに落とし込んでみて下さい。
作ったプログラムにbronze(1)とした場合に正しい正解を返してくれればOKです。

2x2の場合は脳内だけだと難しそうですが、ノートにでも書いて解いてみましょう。(左上への移動を╔と書きます)

  • 左上スタート→解無し
    初手→だと左下に行けず、初手↓だと右上に行けない

  • 右上スタート→ ↓╔↓ 
    初手は↓以外には移動できず、2手目は╔にしか移動できず3手目は→が訪問済みなので行けないので↓のみ

  • 左下スタート→ →╔→
    初手は→にしか移動できない、2手目は╔にしか移動できない。3手目は↓は訪問済みなので行けない

  • 右下スタート→解無し
    初手は╔にしか行けず、2手目は↓に行っても→に行ってもその後は移動できない

1x1で書いたプログラムは正しい2x2の条件を与えた場合に正しい答えを返してくれているでしょうか?
返してくれない場合は何か条件が足りないので、自分がノートに書いたときに何を持って判断したかを思い出して、プログラムに反映します。

という感じで3x3,4x4,,,と条件を設定して、答えが正しいかどうかを判定していきましょう。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/20 20:40

    回答ありがとうございます。とても分かりやすく頭の中を整理できた気がします。条件の見直しを今からしていきたいと思います。

    キャンセル

  • 2018/06/20 20:44

    はい。頑張ってください。
    具体的にしたいことがソースコードに落とし込めない場合や、
    ソースコードに落とし込んでみたが期待通りに動作しない場合は改めてその部分に絞って質問をすると良い回答が得られると思います。

    キャンセル

+3

 総当たり

総当たりでもいいと思いますが、

  1. 二次元座標マップ(二次元配列)として変数 map を作り、全要素値を false にする。要素値は通過フラグである(通過済 = true, 未通過 =false)。
  2. 現在の座標として、変数 x, y を作る
  3. 初期座標をランダムに決定し、変数 x, y を初期化。変数 map の該当座標値を true にする
  4. 移動先として「左上」「下」「右」をランダムに決定する
  5. 移動座標の map 値が true なら 4. へ戻る。座標が false なら true に変更し、変数 x, y を初期化
  6. 5. で3回 4. へ戻る動作が発生したら終了

 三手先をシミュレーション

三手先をシミュレーションすると、直前の二手によって、移動先の「左上」「下」「右」の中で移動できない選択肢がある事に気が付きます。

  • なぜ移動できないのか
  • どういう条件になると移動できないのか

上記を論理的に考え、アルゴリズムに落とし込むだけでも最適化は可能だと思います。

2手前の移動方向と1手前の移動方向が異なる時,この2つに使われていない移動方向に移動することが出来ないですね(すでに訪問済みであるため)。

そうですね。

  • 直前のニ手を変数で持っておく
  • 移動可能な方向を変数で持っておく ['left-up', 'right', 'down']

このようにすれば、変数値を変更する事で移動可能な方向を制御出来ます。

 座標による詰み

例えば、上から3行目の左端から右端まで、右方向に移動し続けたとします。
次に「左上」に移動すれば、3行目より下に行けなくなり、「下」に移動すれば、3行目より上に行けなくなります。
つまり、同一行で全ての列が通過済の状況になると、上下のどちらかの全座標が通過済でない限りは詰みます。
各行の通過済の列数を記録しておけば、このような事態は防げます。
列に関しても、同様ですね。

Re: okamot さん

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/21 07:43

    ちなみに、人力で解けました(lZを左右反転)。

    キャンセル

  • 2018/06/21 08:19

    回答ありがとうございます。2手前の移動方向と1手前の移動方向が異なる時,この2つに使われていない移動方向に移動することが出来ないですね(すでに訪問済みであるため)。

    キャンセル

+2

有向グラフのハミルトン路問題と思われます。すいません。力任せ探索でしか私は解けませんでした。組合せ爆発になるのでn=7以上は時間がかかって解けていません。

bronze = (n) ->
  masuToPoint = (m) ->
    [m %% n, m // n]

  pointToMasu = ([x, y]) ->
    return -1 unless 0 <= x < n
    return -1 unless 0 <= y < n
    x + y * n

  masuMax = n**2 - 1
  masuList = [0..masuMax]
  masuNextList = for i in masuList
    [x, y] = masuToPoint(i)
    [
      pointToMasu([x - 1, y - 1])
      pointToMasu([x + 1, y])
      pointToMasu([x, y + 1])
    ].filter (m) -> 0 <= m <= masuMax

  hamiltonianPath = (current, passed) ->
    passed.delete(current)
    return true if passed.size == 0
    masuNextList[current]
      .filter (next) -> passed.has(next)
      .some (next) -> hamiltonianPath(next, new Set(passed))

  (i for i in masuList when hamiltonianPath(i, new Set(masuList)))

for i in [1..6]
  beginTime = new Date
  result = bronze(i)
  endTime = new Date
  diffMsec = endTime.getTime() - beginTime.getTime()
  console.log "#{i} (#{diffMsec} msec): #{bronze(i)}"

JavaScriptのコードが欲しい場合はTry CoffeeScriptで自分で変換してください。

計算量はO(n^2*3^(n^2))ぐらい?大きすぎる…。

さらに最適化を目指すためのアイデア

  1. 0からn^2-1への対角線で鏡像になっているので、求めるのは半分だけで良い。(残り半分は自動的に決まる)
    効果は、たかが半分、されど半分。
  2. メモ化。
    JavaScriptのMapはNaNを除き===での比較になるため、ArrayやSetのオブジェクトは中身が同じでも異なると判断されてしまいます。。一度一意の文字列に変換するという方法で実装してみましたが、逆に遅くなってしまいました。
  3. 最後まで探索しなくても、打ち切りのパターンがあるはず。
    どういう条件で打ち切りできるのか、よくわかりませんでした。残りを区切る壁みたいのが出来たら、打ち切れるんだけど、どうやって検出するんだろう。
  4. ハミルトン閉路ではない。
    もし、ハミルトン閉路であれば、全てが可能という回答になります。しかし、そうではなさそうです。
  5. スタック数がO(n^2)。
    再帰させない方法はわかりませんでした。あるのかな?
  6. 探索順。
    単純に順番を変えてもほとんど変わりませんでした。よくわかりません。
  7. パターンを見いだす。
    奇数と偶数でそれぞれパターンはありそうですが、よくわかりません。
  8. 2x2で埋める。
    2x2の場合は右上と左下にあるときだけ埋められる。つまり、このパターンでうめていければ?
  9. なんかのアルゴリズム。
    たぶんありそうだけど、不勉強なので、わかりません。

私にはお姉さんを救うことは出来ないようです。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/21 08:02

    回答ありがとうございます。ハミルトン路というのは初めて聞いたので調べてみたのですがこの問題はたしかに同じような問題ですね。自分はすべてのマスを訪れる通りが1つもない開始位置で探索を打ち切ろうと思ってたんですけど難しそうです。

    キャンセル

+2

すでに tanat さんが、2 × 2 のとき(以後、これを[2,2] と書きます)に解が限定されることは示されていますから、これを拡張します。
[2,2]の解があるときのパターンから、拡張して、
・基点が左下である場合は [2,n] は解ける([2,2]の後に左上、→と続けられる)
・基点が右上である場合は [m,2] は解ける([2,2]の後に左上、↓と続けられる)
ことは分かります。

さらに、
・基点が左下である場合は、[3w+1,n] は解けない (ただし、wは0以上の整数)
これは[2,n]を書き切った後、右上にいるので、そこから→↓(×n)で[3,n] が解けることが分かります。そこからさらに→へ移動するとまた [2,n] のパターンになるので、横が 3w+1 でないときに解けることになります。
・基点が右上である場合は、[m,3h+1] は解けない(ただし、hは0以上の整数)
であることも分かります。
※[m,2]を書き切ると左下にいるので、そこから↓→(×n)で[m,3]が書け、そこからさらに下で[m,2]のパターンが再現される

って、これで解けるパターンが限定されたので、あとはそれに当てはまっていれば手順通りに埋めていくだけですね。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/21 17:29 編集

    もう少し他に解けるパターンがありました。
    起点が左下である場合、[m,3h] は解ける
     [2,3h] を書ききった後(右上にいる)に、→、→×(m-2)↓↓(┌↓)×(m-2)で[m-2,3]を埋めていくパターンが作れます。ただしこのパターンの終端は右下ではないので、そこからさらにつなげることは出来ません。

    キャンセル

関連した質問

同じタグがついた質問を見る

  • JavaScript

    17034questions

    JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。