YSR研究所

○Webページを参考に試行錯誤

　とは言っても、何もないところから良いプログラムは生まれません。「先達はあらまほしきことなり」と誰かが言っていましたし、「車輪の再発明」という言葉もあります。で、色々ググっていると、面白いページを見つけました。

http://www2.tokai.or.jp/deepgreen/shortnotes/numberplace/algorithm.htm

　……なにこれヤバイ。マジヤバ。
　何がヤバイかって、その解法が洗練されていること。よくある「普通の解き方」(行・列・ブロックで入らない候補数字を消しておく、n国同盟等)のエッセンスをたった6つの要素にまとめてしまうというその発想が凄い。大雑把にまとめると、
　・Sbitサーチ(候補数字が1つだけのマスはその数字に確定)
　・Ubitサーチ(行・列・ボックス内である数字がある1つのマスにしか入らない場合、その数字はそこで確定)
　・InterSection(行・列・ボックスで交差する場合の処理)
　・Enclosure(n国同盟)
　・Exclosure(n国同盟)
　・Negation(背理法)
といったところです。で、実際に使ってみると、難問もビシバシ撃破できるところが素晴らしい(「世界一難しい数独」レベルだと、流石にNegationを2段積まないと無理だったけど)。ま、n国同盟をゴリゴリ計算で出せたらそりゃ強いでしょと。
　自分が実装したコードはちょっと見せられませんが(汚い実装だという意味で)、興味がある方は自力で組んでみてはいかがでしょうか？　Enclosureを多段forループ無しで作るのは難しいですよ(ボソッ

　ぶっちゃけバックトラックで組んだ方が手っ取り早かった件

↓自力で組んだEnclosure関数。modeが当該ページ上のnね。
/* Enclosure(number, mode) */
/* 場合分けせず、modeの値に応じて動的に処理する */
int Enclosure(int number[][NUM_MAX], int mode){
  int flg = 0, temp[NUM_MAX], *pos, i, j, k, sum, chk, tmp;
  pos = (int *)malloc(sizeof(int) * mode);
  for(k = 0; k < mode; k++)
    pos[k] = k;
  while(1){
    /* OR操作 */
    for(k = 0; k < NUM_MAX; k++)
      temp[k] = number[pos[0]][k];
    for(i = 0; i < NUM_MAX; i++){
      for(j = 1; j < mode; j++)
        temp[i] |= number[pos[j]][i];
    }
    /* 候補数字数を数える */
    sum = 0;
    for(k = 0; k < NUM_MAX; k++)
      sum += temp[k];
    /* 分岐 */
    if(sum < mode){
      /* 解なし */
      return -1;
    }else{
      if(sum == mode){
        /* 反映 */
        for(i = 0; i < NUM_MAX; i++){
          chk = 0;
          for(k = 0; k < mode; k++){
            if(pos[k] == i){
              chk = 1;
              break;
            }
          }
          if(chk == 0){
            for(k = 0; k < NUM_MAX; k++){
              if((temp[k] == 1) && (number[i][k] == 1)){
                number[i][k] = 0;
                if(flg == 0)
                  flg = 1;
              }
            }
          }
        }
      }
    }
    /* 次の組み合わせへと移動 */
    chk = 0;
    for(i = mode - 1; i > -1; i--){
      if(pos[i] == i - mode + NUM_MAX){
        if(i == 0){
          chk = 1;
          break;
        }
        continue;
      }
      tmp = pos[i] + 1;
      for(j = i; j < mode; j++){
        pos[j] = tmp;
        tmp++;
      }
      break;
    }
    if(chk == 1)
      break;
  }
  free(pos);
  return flg;
}

関連記事

• 「人類流の、さえたやりかた」 - 数学上の種々の変換についての概説 (2013/08/04)
• 応用情報技術者試験合格キターーーーー！！ (2013/06/24)
• 数独を解くプログラムを書いてみた。 (2013/04/18)
• 「知らないって幸せなこと」？ (2012/07/28)
• 1回目の投稿なので自己紹介でも。 (2012/06/10)