問題7

5×5のマス目に6個の○を次の条件を満たすように書きます。

条件：各行・各列に少なくとも1個は○を書く。同じマスには2個以上の○を書くことはできない。

このとき、6個の○を書く方法は全部で何通りありますか。

これを何も考えずCに直訳したのが以下。

#include <stdlib.h>
#include <stdio.h>

#define printit(a,b,c,d,e,f) printf("%02d,%02d,%02d,%02d,%02d,%02d\n",\
				    a,b,c,d,e,f)

int main(void){
    char rows[5], cols[5];
    int a, b, c, d, e, f, i, p = 0, t = 0;
    for (i = 0; i < 5; i++) rows[i] = cols[i] = 0; /* init */
    for (a = 0; a < 25; a++){
	rows[a % 5]++; cols[a / 5]++;
	for (b = 0; b < 25; b++){
	    if (a == b) continue;
	    rows[b % 5]++; cols[b / 5]++;
	    for (c = 0; c < 25; c++){
		if (a == c) continue;
		if (b == c) continue;
		rows[c % 5]++; cols[c / 5]++;
		for (d = 0; d < 25; d++){
		    if (a == d) continue;
		    if (b == d) continue;
		    if (c == d) continue;
		    rows[d % 5]++; cols[d / 5]++;
		    for (e = 0; e < 25; e++){
			if (a == e) continue;
			if (b == e) continue;
			if (c == e) continue;
			if (d == e) continue;
			rows[e % 5]++; cols[e / 5]++;
			for (f = 0; f < 25; f++){
			    if (a == f) continue;
			    if (b == f) continue;
			    if (c == f) continue;
			    if (d == f) continue;
			    if (e == f) continue;
			    rows[f % 5]++; cols[f / 5]++;
			    t++;
			    if(    rows[0] && cols[0]
				&& rows[1] && cols[1]
				&& rows[2] && cols[2]
				&& rows[3] && cols[3]
				&& rows[4] && cols[4]
				) {
				printit(a,b,c,d,e,f);
				p++;
			    }
			    rows[f % 5]--; cols[f / 5]--;
			}
			rows[e % 5]--; cols[e / 5]--;
		    }
		    rows[d % 5]--; cols[d / 5]--;
		}
		rows[c % 5]--; cols[c / 5]--;
	    }
	    rows[b % 5]--; cols[b / 5]--;
	}
	rows[a % 5]--; cols[a / 5]--;
    }
    fprintf(stderr, "%d / %d\n", p, t);
    return 0;
}

こんな力押しコードに20分も罹って、大丈夫か?

しかもこれ、例えば(00,06,12,18,24,01)と(01,06,12,18,24,00)を別カウントしているので、○をそれぞれ別ものとして扱った場合は正しいのだろうけど、問題を見る限りこういう場合は同一視しなければならなさそう。とすると、3,024,000を6! = 720 で割った 4,200が正解ということかな?

この場合の全組み合わせは、上のstdoutをさらに以下のperl scriptに食わせれば出る。

#!/usr/bin/env perl
use 5.010;
use strict;
use warnings;

my %dupe;
while(<>){
    chomp;
    $dupe{ join ",", sort split /,/, $_ }++
};
say for sort keys %dupe;

こんだけ力押ししても、Core i7なiMacでは実行はこんなもん。

% gcc -W -Wall -O6 5x5x6.c
% /usr/bin/time -l ./a.out >! 5x5x6.out
3024000 / 127512000
        3.68 real         3.15 user         0.14 sys
         0  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
         0  page reclaims
         0  page faults
         0  swaps
      1007  block input operations
         1  block output operations
         0  messages sent
         0  messages received
         0  signals received
      1025  voluntary context switches
         0  involuntary context switches
% wc 5x5x6.out
 3024000 3024000 54432000 5x5x6.out
% perl 5x5x6-pp.pl 5x5x6.out |wc
    4200    4200   75600

エレガントな問題解決
Paul Zeitz /
山口文彦・松崎公紀・
三橋泉・松永多苗子 伊知地宏訳
[原著:The Art and Craft of Problem Solving]

• 6重ループってなにこれきもい
• continueの使い方とかコピペ濫用にもほどがある。
• それでも一応問題の見積もりはしている。チェックすべき組み合わせは ₂₅P₆ = 127,512,000。この時点でCで書くことを決定。
• キモいループが正しくまわっているかどうかを、一応ループカウントしてチェック。確かに127512000と出ている。
• アンチョコは一切見ていない。「エレガントな問題解決」に似たような問題が出ていたような気はするのだけど…

なんて書いておくと、MacBook Airくれるのかしらん…

Dan the Brute Forcer