パスワードを忘れた? アカウント作成
41897 story

「ナイト・ツアー」の解をPython 60行でコーディング 39

ストーリー by hylom
Python Golf 部門より

capra 曰く、

チェスを使ったパズル、「ナイト・ツアー」というゲームをご存知だろうか?ナイトをボード上のマスを移動させ、全てのマスを1回ずつ通過させるというパズルである。

本家/.のttsiod氏は、このパズルの解をPythonで60行のコードで書いたそうだ。「100×100マスのボードでも1秒足らずで解を出せる」とのことだが、本家では「処理は速くないが11行で書いてみた」といったコメントや、「残念だが、次バージョンでは動かないだろう」といったツッコミなどが多く寄せられている模様。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • 改行しなければ (スコア:2, おもしろおかしい)

    by Apeman (36617) on 2008年12月03日 22時17分 (#1466936)
    1行ではなかろうか
  • by acc (36768) on 2008年12月03日 17時30分 (#1466741)
    エイトクイーン [wikipedia.org]と一緒に、学部のころにアルゴリズムの初歩の授業で習いました。
    問題をアルゴリズムミックに解いていくという考え方の習作として、問題領域も広すぎずちょうどいいですよね。
    • by Anonymous Coward
      何方か「10飛車」問題を解いて下さいな。
      • Re:習作 (スコア:3, おもしろおかしい)

        by greentea (17971) on 2008年12月03日 18時58分 (#1466817) 日記
        >何方か「10飛車」問題を解いて下さいな。
        これでいいの?

        飛________
        _飛_______
        __飛______
        ___飛_____
        ____飛____
        _____飛___
        _______飛_
        ______飛歩飛 <ちょ、おまwwww
        _______飛_
        --
        1を聞いて0を知れ!
        親コメント
        • by Anonymous Coward
          そんだけの飛車をどこで調達するんだよ。
          • by Anonymous Coward
            コマのセットを6つ買えばいい。それか3つセット買ってきて予備の何も書かれていないコマに飛と書けばいい。
      • Re:習作 (スコア:1, すばらしい洞察)

        by Anonymous Coward on 2008年12月04日 6時50分 (#1467098)
        1.まず駒を5組用意する←ここが肝なんじゃない?
        親コメント
      • by Anonymous Coward
        ・手駒として持っておく
        ・上に積む
  • by Elbereth (17793) on 2008年12月04日 5時47分 (#1467094)
    Perlで一行で書いてみたよ! という投稿マダァー!?
  • クリスマスのイルミネーションとかライトアップを
    見学する順路を解いたのかと空目した。
  • by ninestars (5792) on 2008年12月04日 9時47分 (#1467141) 日記
    python で行末コードをLFで普通に記述、それをWindows上で実行。

    「いや、このOSではCRLFが改行だから」

  • Perl6じゃないとダメなのかしら

    $ cat tour.pl
    #!/usr/bin/perl
    use Chess;
     
    $knight = Chess::Piece::Knight->new();
    $board = Chess::Board->new(100, 100, setup => {
                    $knight => "a1";
    });
     
    $knight->tour()->show();
    $ perl --version
     
    This is perl, v5.8.8 built for darwin-thread-multi-2level
     
    $ ./tour.pl
    syntax error at ./tour.pl line 7, near "}"
    Execution of ./tour.pl aborted due to compilation errors.
    prologのやつは動かし方がわかりません

    $ gprolog
    GNU Prolog 1.3.0
    By Daniel Diaz
    Copyright (C) 1999-2007 Daniel Diaz
    | ?- [knighttour].
      :
    yes
    | ?- このあとどうするのでしょう???
    --
    love && peace && free_software
    t-nissie
    • Prolog版は、'<'〜'>'が消えてしまっている気がします。 また、gprologではnot/1を(\+)/1に置き換えると動くようです。

      wrapper(Size, [X, Y], Path) :-
              X =< Size, X >= 1,
              Y =< Size, Y >= 1,
              Depth is Size * Size - 1,
              worker(Size, [X, Y], Depth, [], ReversedPath),
              reverse(ReversedPath, Path),
              write(Path), nl.
      worker(_, State, 0, CurrentPath, [State|CurrentPath]).
      worker(Size, State, Depth, CurrentPath, FinalPath) :-
              DepthM1 is Depth - 1,
              move_generator(Size, State, NewState),
              \+(checker(NewState, CurrentPath)),
              worker(Size, NewState, DepthM1, [State|CurrentPath], FinalPath).
      checker(State, [State|_]).
      checker(State, [_|StateList]) :-
              checker(State, StateList).
      move_generator(Size, [X, Y], [NewX, NewY]) :-
              move(MoveX, MoveY),
              NewX is X + MoveX, NewX =< Size, NewX >= 1,
              NewY is Y + MoveY, NewY =< Size, NewY >= 1.
      move(1, 2).
      move(2, 1).
      move(2, -1).
      move(1, -2).
      move(-1, -2).
      move(-2, -1).
      move(-2, 1).
      move(-1, 2).
      例えば5x5の盤で初期位置[1, 1]から始める場合、

      ?- wrapper(5, [1,1], _).
      で解が表示されます。Returnキーで終了、セミコロン(;)で別解表示(シンメトリ等は考慮しない)です。
      親コメント
      • おお、いつもありがとうございます。

        3x3と4x4には解がないけど5x5にはたくさん解があることがすぐに出せますね。

        | ?- wrapper(3,[1,1],_).
         
        no
        | ?- wrapper(4,[1,1],_).
         
        (25 ms) no
        | ?- wrapper(5,[1,1],_).
        [[1,1],[2,3],[3,5],[5,4],[4,2],[2,1],[3,3],[1,4],[2,2],[4,1],[5,3],[4,5],[2,4],[1,2],[3,1],[5,2],[4,4],[2,5],[1,3],[3,2],[5,1],[4,3],[5,5],[3,4],[1,5]]
         
        true ? a
        Prologは勉強しようと思ってもいつも「磯野家の家系」どまりなので、
        これを機会に、Knight's Tour Puzzleで「始点と終点が一致」の条件を
        つけたら解はどれくらい減るのか、をとりあえず目標にいじってみます。
        --
        love && peace && free_software
        t-nissie
        親コメント
    • by Anonymous Coward
      $knight => "a1" の後ろの;が余計なんじゃ?動かしてないけど
  • by kr (10950) on 2008年12月04日 17時41分 (#1467513) 日記
    本家にすでにHaskell版 [slashdot.org]が載ってますが、もっと短い版と、もっと速い版を書いてみました。

    まず2行版。さらにセミコロンを使ってよければ、何でも1行になるので、行数を競っても仕方ありませんけれども。

    import System
    main = getArgs >>= \args -> let d = read $ head args in mapM_ (tour d) [[(x, y)] | x <- [1 .. d], y <- [1 .. d]] where tour d v@((x, y):v') | d * d == length v = print v >> exitWith ExitSuccess | otherwise = mapM_ (tour d) [(x', y') : v | (x', y') <- [(x + 2, y + 1), (x + 2, y - 1), (x - 2, y + 1), (x - 2, y - 1), (x + 1, y + 2), (x + 1, y - 2), (x - 1, y + 2), (x - 1, y - 2) ], x' > 0, x' <= d, y' > 0, y' <= d, (x', y') `notElem` v' ]
    一応Haskell 98仕様準拠のはず。

    もう一つは、長さは気にせずネタ元のPython版とほぼ同様の動作をする高速版です。ghc 6.8.1以降が必要ですが、ghc 6.10.1で動くかどうかは未確認です。51行になりました。

    import Control.Monad
    import qualified Control.Exception as E
    import Data.Array.IO
    import Data.List
    import Data.Ord
    import System
    import System.IO
    import Text.Printf

    type Board = IOUArray (Int, Int) Int

    printBoard:: Board -> IO ()
    printBoard board = do
      rng@((xl, yl), (xu, yu)) <- getBounds board
      let scale = length $ show $ rangeSize rng
          hline = intercalate (replicate scale '-') $ replicate (xu - xl + 2) "+"
      putStrLn hline
      forM_ [y | y <- [yl .. yu]] $ \y ->
          do forM_ [ x | x <- [xl .. xu]] $ \x ->
                 readArray board (x, y) >>= printf "|%*d" scale
             putStrLn $ "|\n" ++ hline

    tour:: Board -> Int -> (Int, Int) -> IO ()
    tour board counter (x, y) = do
      writeArray board (x, y) counter
      bounds <- getBounds board
      if counter == rangeSize bounds
        then printBoard board >> exitWith ExitSuccess
        else do
          let js = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]
              neighbours:: (Int, Int) -> IO [(Int, Int)]
              neighbours (x, y) =
                  filterM (\p -> readArray board p >>= (return . (0==)))
                              [p | p <- [(x + dx, y + dy) | (dx, dy) <- js],
                               bounds `inRange` p]
          cs <- neighbours (x, y)
          cs' <- mapM (\p -> do { ns <- neighbours p; return (length ns, p) }) cs
          forM_ (sortBy (comparing fst) cs') $ \(_, p)->tour board (counter + 1) p
      writeArray board (x, y) 0

    main:: IO ()
    main = do
      args <- getArgs
      let d = if null args then 8 else read (head args)
      E.catchJust E.errorCalls (E.evaluate d >> return ()) $ \_ -> do
             prog <- getProgName
             hPutStrLn stderr $ "Usage: " ++ prog ++ " [ squareSize ]"
             exitWith $ ExitFailure 2
      board <- (newArray ((1, 1), (d, d)) 0):: IO Board
      forM_ [(x, y) | x <- [1 .. d], y <- [1 .. d]] $ tour board 1
      putStrLn "No solution found"
    手元のFreeBSD 7.1-PRERELEASE, Core 2 Duo E6600 2.4GHz, 2GB RAM, ghc 6.8.3の環境で試してみると、 100x100の盤面でも1秒足らずで計算できました。

    % time ./knight 100 > /dev/null
    0.650u 0.015s 0:00.66 100.0%    677+1840k 0+0io 0pf+0w
  • by Anonymous Coward on 2008年12月03日 4時47分 (#1466321)
    なんて名前だっけ。
    • ナイトムーブ? (スコア:3, 参考になる)

      by Rodin (28411) on 2008年12月03日 18時05分 (#1466777)
      ファミコンで「ナイトムーブ」というゲームがありました。

      ディスク片面・書換専用で、テトリスの作者が開発したそうです。
      ナイトを盤面(縦4x横8)でジャンプ移動させ、同じマスを3回踏むと穴が
      開き、穴に落ちないよう全マスを3回ずつ踏むと面クリアです。

      連続で穴を開けたり、移動スピードを上げて踏むと高得点になります。
      しかしナイトは立ち止まれず、どんどんスピードアップし、面ごとに開始位置も
      変わるため、ハイスコア獲得が難しい仕掛けになっていました。
      --
      匠気だけでは商機なく、正気なだけでは勝機なし。
      親コメント
    • ただの桂馬一枚じゃ、全マスを踏むのことができないのは自明。
      ナイト・ツアー問題は、ナイト巡回問題とも言いますね。
      親コメント
      • by Anonymous Coward
        >ただの桂馬一枚じゃ、全マスを踏むのことができない

        途中で成ればおk。ってそういう話じゃないね。
        • by Anonymous Coward
          > 途中で成ればおk。

          成ったら上下左右に移動できるから簡単じゃないかと思いましたが、
          念のためにちょっとやってみました。

          将棋に準拠した桂馬の初期位置(8-九)を仮定すると、
          その隣の角(9-九)が終点になることが確定します。
          桂馬が成ったポイントから、終点となる角まで、
          成るまでに通った足跡を避けながら全てのマスを通っていく...

          いや、これってどうやっても無理なんじゃないか?

          ここでふと、成った桂馬は斜め前にも移動できる事実に気づきました。
          やはり何の面白みも無い簡単すぎる問題でしたねこれは。
          皆様も試さない方が良いですよ。
    • by Anonymous Coward on 2008年12月03日 16時55分 (#1466707)
      成金問題。

      成金になれば問題が解決するという、プラグマティックな解決策を教授するためのゲーム。
      親コメント
  • by Anonymous Coward on 2008年12月03日 17時22分 (#1466730)
    > 11行で書いてみた

    すぐに「いやもっと短く」「俺は4行だぜ」とかのコメントが付いて、、、

    元ネタの60行の人のはちゃんとした python コードっぽい雰囲気なんですが
    この辺の4行とかの世界は 4行とはいっても "素直な4行" とは程遠いです。
    それはそれで技を駆使しているわけですが…

    (いい加減に "バイト数" とか何かもっと別の指標が欲しいところ)
    • by T.Sawamoto (4142) on 2008年12月03日 18時00分 (#1466771)
      とりあえず、「ずるっこ」をしてなさそうな17行バージョン(^^;)
      Usageが表示されない以外はほぼオリジナルと同じです。

      from sys import argv,exit
      def Fill(s,b,x,y,c):
        b[y][x]=c
        if c==s**2:
          a=len(str(c))
          print(s*('+'+a*'-')+'+')
          for l in b:
            print(''.join(['|%*d'%(a,n)for n in l])+'|\n+'+s*(a*'-'+'+'))
          exit(0)
        for u,v in ((-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)):
            x2,y2=x+u,y+v
            if 0<=x2<s and 0<=y2<s and b[y2][x2]==0:
              Fill(s,b,x2,y2,c+1)
        b[y][x]=0
      s = 8 if len(argv)!=2 else int(argv[1])
      Fill(s,[[0]*s for i in range(s)],0,0,1)
      print("No solution found")
      親コメント
      • by yasiyasi (5450) on 2008年12月04日 14時46分 (#1467383)
        とりあえず,リリースされたばかりのPython 3.0 [python.org]でも動きましたので,ご報告。

        誰か,「Python3.0リリース」でタレコミお願いします。参考サイト:
        親コメント
        • by T.Sawamoto (4142) on 2008年12月04日 15時01分 (#1467392)
          おお、ついにリリースされましたか。早速試さねば……。

          ついでに、先のコードを「ずるっこ」込みで最適化した9行バージョンをば。
          (発見できなかったときにメッセージを表示しない、数字桁数が5桁固定という違いあり)
          各行は某七行プログラミングスレの流儀に従い、1行は79桁以内に収めてあります。
          あと2行が減らせない(^^;)

          from sys import argv,exit;s=8 if len(argv)!=2 else int(argv[1])
          def F(s,p,q,r,b,x,y,c):
            b[y*s+x]=c;o=(p,p+q+r)
            if c==s*s:
              print(r+''.join([o[n%s//(s-1)]%b[n] for n in range(c)]));exit(0)
            for u,v in ((-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)):
              0<=x+u<s and 0<=y+v<s and b[(y+v)*s+x+u]<1 and F(s,p,q,r,b,x+u,y+v,c+1)
            b[y*s+x]=0
          F(s,'|%5d','|\n',s*('+'+5*'-')+'+\n',[0]*s*s,0,0,1)
          親コメント
    • by Anonymous Coward
      正社員以外のバイトの数
    • by Anonymous Coward
      昔BASICであった『一画面プログラム』を思い出す。
  • by Anonymous Coward on 2008年12月03日 17時25分 (#1466733)
    MC6800で書いた、そんなに長いものにはならないと思うんだけどなぁ。
  • by Anonymous Coward on 2008年12月03日 17時29分 (#1466738)
    反射的に7行テトリスを思い起こしたけど
    これって海外での知名度はどれほどのものなんだろう?
    http://2chparty.net/archives/tetris/1059892659.htm [2chparty.net]
    • by Anonymous Coward
      7行ネタならDeCSSからの流れのこっち [2ch.net]のほうがよさげ
typodupeerror

「毎々お世話になっております。仕様書を頂きたく。」「拝承」 -- ある会社の日常

読み込み中...