朝日新聞2005年11月18日パズル横丁解答

プログラムの実行結果は以下の通り。

----------
　　　10１
５１　　５
１　10　　
５　１　５
　10　１　

1 件, 12.921 秒

図にすると以下のようになる。

プログラムのソースは以下の通り。

#include "puzutl.h"

set result;
int numResult = 0;

void pp( int a, int b, int c) {
  if( a) ps( "10");
  if( b) ps( "５");
  if( c) ps( "１");
  if( !(a||b||c)) ps( "　");
}
void find(int a0,int a1,int a2,int a3,int a4,int a5,int a6,int a7,int a8,int a9,int a10,int a11,int a12,int a13,int a14,int a15,int a16,int a17,int a18,int a19,int a20,int a21,int a22,int a23,int a24,
          int b0,int b1,int b2,int b3,int b4,int b5,int b6,int b7,int b8,int b9,int b10,int b11,int b12,int b13,int b14,int b15,int b16,int b17,int b18,int b19,int b20,int b21,int b22,int b23,int b24,
          int c0,int c1,int c2,int c3,int c4,int c5,int c6,int c7,int c8,int c9,int c10,int c11,int c12,int c13,int c14,int c15,int c16,int c17,int c18,int c19,int c20,int c21,int c22,int c23,int c24)
{
  char buf[1024];
  sprintf( buf, "%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d/%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d/%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d",
           a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,a17,a18,a19,a20,a21,a22,a23,a24,
           b0,b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14,b15,b16,b17,b18,b19,b20,b21,b22,b23,b24,
           c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,c21,c22,c23,c24);
  if( result.find(buf) != result.end()) return; // 同じ解を表示しないようにする
  result.insert(buf);
  numResult++;
  ps( "----------\n");
  pp(a0,b0,c0);
  pp(a1,b1,c1);
  pp(a2,b2,c2);
  pp(a3,b3,c3);
  pp(a4,b4,c4);ps("\n");
  pp(a5,b5,c5);
  pp(a6,b6,c6);
  pp(a7,b7,c7);
  pp(a8,b8,c8);
  pp(a9,b9,c9);ps("\n");
  pp(a10,b10,c10);
  pp(a11,b11,c11);
  pp(a12,b12,c12);
  pp(a13,b13,c13);
  pp(a14,b14,c14);ps("\n");
  pp(a15,b15,c15);
  pp(a16,b16,c16);
  pp(a17,b17,c17);
  pp(a18,b18,c18);
  pp(a19,b19,c19);ps("\n");
  pp(a20,b20,c20);
  pp(a21,b21,c21);
  pp(a22,b22,c22);
  pp(a23,b23,c23);
  pp(a24,b24,c24);ps("\n");
}

YesNo samepos( int a, int b, int c) {
  int cnt = 0;
  if(a) cnt++;
  if(b) cnt++;
  if(c) cnt++;
  if( cnt >= 2) return YES; else return NO;
}
int main( int argc, cstring argv[])
{
  int a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,a17,a18,a19,a20,a21,a22,a23,a24;
  int b0,b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14,b15,b16,b17,b18,b19,b20,b21,b22,b23,b24;
  int c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,c21,c22,c23,c24;
  int acnt, bcnt, ccnt;
  int w;
  ProcTime pt;
  for( int a=0; a< 256; a++) {
    a0=a1=a2=a3=a4=a5=a6=a7=a8=a9=a10=a11=a12=a13=a14=a15=a16=a17=a18=a19=a20=a21=a22=a23=a24=0;
    acnt=1; a21=10;
    if(a&1) { a2=10; acnt++;}
    if(a&2) { a3=10; acnt++;}
    if(a&4) { a12=10; acnt++;}
    if(a&8) { a13=10; acnt++;}
    if(a&16) { a14=10; acnt++;}
    if(a&32) { a17=10; acnt++;}
    if(a&64) { a18=10; acnt++;}
    if(a&128) { a19=10; acnt++;}
    if(a2+a3>11) continue;
    if(a12+a13+a14>11) continue;
    if(a17+a18+a19>11) continue;
    if(a2+a12+a17>11) continue;
    if(a3+a13+a18>11) continue;
    if(a14+a19>11) continue;
    for( int b=0; b< 16384; b++) {
      b0=b1=b2=b3=b4=b5=b6=b7=b8=b9=b10=b11=b12=b13=b14=b15=b16=b17=b18=b19=b20=b21=b22=b23=b24=0;
      bcnt=1; b5=5;
      if(b&1) { b0=5; bcnt++;}
      if(b&2) { b2=5; bcnt++;}
      if(b&4) { b3=5; bcnt++;}
      if(b&8) { b7=5; bcnt++;}
      if(b&16) { b8=5; bcnt++;}
      if(b&32) { b9=5; bcnt++;}
      if(b&64) { b10=5; bcnt++;}
      if(b&128) { b12=5; bcnt++;}
      if(b&256) { b13=5; bcnt++;}
      if(b&512) { b14=5; bcnt++;}
      if(b&1024) { b15=5; bcnt++;}
      if(b&2048) { b17=5; bcnt++;}
      if(b&4096) { b18=5; bcnt++;}
      if(b&8192) { b19=5; bcnt++;}
      // 横
      if(a0+a1+a2+a3+a4+b0+b1+b2+b3+b4!=10) continue;
      if(a5+a6+a7+a8+a9+b5+b6+b7+b8+b9!=10) continue;
      if(a10+a11+a12+a13+a14+b10+b11+b12+b13+b14!=10) continue;
      if(a15+a16+a17+a18+a19+b15+b16+b17+b18+b19!=10) continue;
      if(a20+a21+a22+a23+a24+b20+b21+b22+b23+b24!=10) continue;
      // 縦
      if(a0+a5+a10+a15+a20+b0+b5+b10+b15+b20!=10) continue;
      if(a1+a6+a11+a16+a21+b1+b6+b11+b16+b21!=10) continue;
      if(a2+a7+a12+a17+a22+b2+b7+b12+b17+b22!=10) continue;
      if(a3+a8+a13+a18+a23+b3+b8+b13+b18+b23!=10) continue;
      if(a4+a9+a14+a19+a24+b4+b9+b14+b19+b24!=10) continue;
      // 斜め
      if(a0+a6+a12+a18+a24+b0+b6+b12+b18+b24!=10) continue;
      if(a4+a8+a12+a16+a20+b4+b8+b12+b16+b20!=10) continue;
      if( 12-(acnt+bcnt) < 5) continue; // 各行又は列に最低一つの1が無ければならないので
      for( int c=0; c< 33554432; c++) {
        c0=c1=c2=c3=c4=c5=c6=c7=c8=c9=c10=c11=c12=c13=c14=c15=c16=c17=c18=c19=c20=c21=c22=c23=c24=0;
        ccnt=1; c4=1;
        if(c&1) { c0=1; ccnt++;}
        if(c&2) { c1=1; ccnt++;}
        if(c&4) { c2=1; ccnt++;}
        if(c&8) { c3=1; ccnt++;}
        if(c&64) { c6=1; ccnt++;}
        if(c&128) { c7=1; ccnt++;}
        if(c&256) { c8=1; ccnt++;}
        if(c&512) { c9=1; ccnt++;}
        if(c&1024) { c10=1; ccnt++;}
        if(c&2048) { c11=1; ccnt++;}
        if(c&4096) { c12=1; ccnt++;}
        if(c&8192) { c13=1; ccnt++;}
        if(c&16384) { c14=1; ccnt++;}
        if(c&32768) { c15=1; ccnt++;}
        if(c&65536) { c16=1; ccnt++;}
        if(c&131072) { c17=1; ccnt++;}
        if(c&262144) { c18=1; ccnt++;}
        if(c&524288) { c19=1; ccnt++;}
        if(c&1048576) { c20=1; ccnt++;}
        if(c&4194304) { c22=1; ccnt++;}
        if(c&8388608) { c23=1; ccnt++;}
        if(c&16777216) { c24=1; ccnt++;}
        if( acnt+bcnt+ccnt == 12) {
          // 横
          if(a0+a1+a2+a3+a4+b0+b1+b2+b3+b4+c0+c1+c2+c3+c4!=11) continue;
          if(a5+a6+a7+a8+a9+b5+b6+b7+b8+b9+c5+c6+c7+c8+c9!=11) continue;
          if(a10+a11+a12+a13+a14+b10+b11+b12+b13+b14+c10+c11+c12+c13+c14!=11) continue;
          if(a15+a16+a17+a18+a19+b15+b16+b17+b18+b19+c15+c16+c17+c18+c19!=11) continue;
          if(a20+a21+a22+a23+a24+b20+b21+b22+b23+b24+c20+c21+c22+c23+c24!=11) continue;
          // 縦
          if(a0+a5+a10+a15+a20+b0+b5+b10+b15+b20+c0+c5+c10+c15+c20!=11) continue;
          if(a1+a6+a11+a16+a21+b1+b6+b11+b16+b21+c1+c6+c11+c16+c21!=11) continue;
          if(a2+a7+a12+a17+a22+b2+b7+b12+b17+b22+c2+c7+c12+c17+c22!=11) continue;
          if(a3+a8+a13+a18+a23+b3+b8+b13+b18+b23+c3+c8+c13+c18+c23!=11) continue;
          if(a4+a9+a14+a19+a24+b4+b9+b14+b19+b24+c4+c9+c14+c19+c24!=11) continue;
          // 斜め
          if(a0+a6+a12+a18+a24+b0+b6+b12+b18+b24+c0+c6+c12+c18+c24!=11) continue;
          if(a4+a8+a12+a16+a20+b4+b8+b12+b16+b20+c4+c8+c12+c16+c20!=11) continue;
          // 同じ場所にコインがあったらやり直し
          if(samepos(a0,b0,c0)||
             samepos(a1,b1,c1)||
             samepos(a2,b2,c2)||
             samepos(a3,b3,c3)||
             samepos(a4,b4,c4)||
             samepos(a5,b5,c5)||
             samepos(a6,b6,c6)||
             samepos(a7,b7,c7)||
             samepos(a8,b8,c8)||
             samepos(a9,b9,c9)||
             samepos(a10,b10,c10)||
             samepos(a11,b11,c11)||
             samepos(a12,b12,c12)||
             samepos(a13,b13,c13)||
             samepos(a14,b14,c14)||
             samepos(a15,b15,c15)||
             samepos(a16,b16,c16)||
             samepos(a17,b17,c17)||
             samepos(a18,b18,c18)||
             samepos(a19,b19,c19)||
             samepos(a20,b20,c20)||
             samepos(a21,b21,c21)||
             samepos(a22,b22,c22)||
             samepos(a23,b23,c23)||
             samepos(a24,b24,c24)) continue;
          find(a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,a17,a18,a19,a20,a21,a22,a23,a24,
               b0,b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14,b15,b16,b17,b18,b19,b20,b21,b22,b23,b24,
               c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19,c20,c21,c22,c23,c24);
        }
      }
    }
  }
  pt.end();
  ps( "\n%d 件, %g 秒\n", numResult, pt.sec());
  return 0;
}