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

capra 曰く、

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

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

改行しなければ

[Apeman (36617)]

1行ではなかろうか

Re:改行しなければ

[baby_face (5007)]

pythonのコードを1行で書くというのも、面白いパズルになるような。。

Re:

[Anonymous Coward]

exec "if True:\n print 1"

Re:

[Anonymous Coward]

ソースを見ましたが、少なくともこのソースを一行にするとエラーになります。

習作

[acc (36768)]

エイトクイーン [wikipedia.org]と一緒に、学部のころにアルゴリズムの初歩の授業で習いました。
問題をアルゴリズムミックに解いていくという考え方の習作として、問題領域も広すぎずちょうどいいですよね。

Re:

[Anonymous Coward]

何方か「10飛車」問題を解いて下さいな。

Re:習作

[greentea (17971)]

>何方か「10飛車」問題を解いて下さいな。
これでいいの？

飛＿＿＿＿＿＿＿＿
＿飛＿＿＿＿＿＿＿
＿＿飛＿＿＿＿＿＿
＿＿＿飛＿＿＿＿＿
＿＿＿＿飛＿＿＿＿
＿＿＿＿＿飛＿＿＿
＿＿＿＿＿＿＿飛＿
＿＿＿＿＿＿飛歩飛 ＜ちょ、おまwwww
＿＿＿＿＿＿＿飛＿

--
1を聞いて0を知れ!

Re:

[Anonymous Coward]

そんだけの飛車をどこで調達するんだよ。

Re:

[Anonymous Coward]

コマのセットを6つ買えばいい。それか3つセット買ってきて予備の何も書かれていないコマに飛と書けばいい。

Re:習作

[Anonymous Coward]

1.まず駒を5組用意する←ここが肝なんじゃない？

Re:

[Anonymous Coward]

・手駒として持っておく
・上に積む

まだか

[Elbereth (17793)]

Perlで一行で書いてみたよ! という投稿マダァー!?

書いたぜ！

[Anonymous Coward]

while(1){}

「ナイト・ツアー」って

[NOBAX (21937)]

クリスマスのイルミネーションとかライトアップを
見学する順路を解いたのかと空目した。

Re:「ナイト・ツアー」って

[Choro-Chan (31768)]

私は「ナイトライダー」と空目した・・・

K.I.T.T.ならすぐ答えを返してくれそうだ。

Re:

[Anonymous Coward]

それは「巡回セールスマン」だな。これはこれで面白いよ。

Re:

[Anonymous Coward]

セールスマンじゃ、ナイト＝夜ってオチにはならんのです。

一行とは

[ninestars (5792)]

python で行末コードをLFで普通に記述、それをWindows上で実行。

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

本家のPerlのChessモジュールを使ったやつが動かない

[t-nissie (8647)]

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

Re:本家のPerlのChessモジュールを使ったやつが動かない

[kr (10950)]

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キーで終了、セミコロン(;)で別解表示(シンメトリ等は考慮しない)です。

Re:本家のPerlのChessモジュールを使ったやつが動かない

[t-nissie (8647)]

おお、いつもありがとうございます。

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

Re:

[Anonymous Coward]

$knight => "a1" の後ろの;が余計なんじゃ？動かしてないけど

Haskell版

[kr (10950)]

本家にすでに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

桂馬で全マス踏むゲームがあった

[Anonymous Coward]

なんて名前だっけ。

ナイトムーブ？

[Rodin (28411)]

ファミコンで「ナイトムーブ」というゲームがありました。

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

連続で穴を開けたり、移動スピードを上げて踏むと高得点になります。
しかしナイトは立ち止まれず、どんどんスピードアップし、面ごとに開始位置も
変わるため、ハイスコア獲得が難しい仕掛けになっていました。

--
匠気だけでは商機なく、正気なだけでは勝機なし。

Re:

[Anonymous Coward]

参考 http://en.wikipedia.org/wiki/Knight_Move [wikipedia.org]

Re:桂馬で全マス踏むゲームがあった

[Ryo.F (3896)]

ただの桂馬一枚じゃ、全マスを踏むのことができないのは自明。
ナイト・ツアー問題は、ナイト巡回問題とも言いますね。

Re:

[Anonymous Coward]

＞ただの桂馬一枚じゃ、全マスを踏むのことができない

途中で成ればおｋ。ってそういう話じゃないね。

Re:

[Anonymous Coward]

> 途中で成ればおｋ。

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

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

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

ここでふと、成った桂馬は斜め前にも移動できる事実に気づきました。
やはり何の面白みも無い簡単すぎる問題でしたねこれは。
皆様も試さない方が良いですよ。

その名は （ Re:桂馬で全マス踏むゲームがあった）

[Anonymous Coward]

成金問題。

成金になれば問題が解決するという、プラグマティックな解決策を教授するためのゲーム。

python なのに one-liner

[Anonymous Coward]

> 11行で書いてみた

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

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

(いい加減に "バイト数" とか何かもっと別の指標が欲しいところ)

Re:python なのに one-liner

[T.Sawamoto (4142)]

とりあえず、「ずるっこ」をしてなさそうな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")

Re:python なのに one-liner

[yasiyasi (5450)]

とりあえず，リリースされたばかりのPython 3.0 [python.org]でも動きましたので，ご報告。

誰か，「Python3.0リリース」でタレコミお願いします。参考サイト：

• Python 3.0 リリース！ [coreblog.org]
  
• もっと知りたいPython3000 [gihyo.jp]
  

Re:python なのに one-liner

[T.Sawamoto (4142)]

おお、ついにリリースされましたか。早速試さねば……。

ついでに、先のコードを「ずるっこ」込みで最適化した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)

バイト数

[Anonymous Coward]

正社員以外のバイトの数

Re:

[Anonymous Coward]

昔BASICであった『一画面プログラム』を思い出す。

大昔

[Anonymous Coward]

MC6800で書いた、そんなに長いものにはならないと思うんだけどなぁ。

7行テトリス

[Anonymous Coward]

反射的に7行テトリスを思い起こしたけど
これって海外での知名度はどれほどのものなんだろう?
http://2chparty.net/archives/tetris/1059892659.htm [2chparty.net]

Re:

[Anonymous Coward]

７行ネタならDeCSSからの流れのこっち [2ch.net]のほうがよさげ