ナンバープレイスを解く

Wikipediaネタが何回か続いたので、ガラッと話を変えてパズルを解いてみようと思います。wikipediaに飽きたわけじゃないですからね^^; まだあのデータを使って色々と遊べるので、その話はまた今度で。

パズルのプログラムは結構好きで、ちょこちょこいろんな種類のパズルを解かせて遊んでました。でもパズルって遊びだけにしか使えないってわけでもなくて、人工知能の基礎的な勉強にもなると思います。例えば数独とかナンクロは、複数ある候補のうちから与えられた制約を満たすものを選択する、制約充足問題と考えられます。

また、ちょっと高度過ぎますが、クロスワードを自動で解く場合は質問文を理解し、それに合う回答を知識ベースや検索エンジンなどから収集してこなければなりません。実際クロスワードを解く方法は最近発表される論文でもたまに見かけたります。

というわけで、パズルを解くプログラムを書くのは面白いだけじゃなくて、きっと色々勉強にもなることも多いんじゃないかなぁと思います。

さて解くパズルですが、まずはメジャーどころでナンバープレイス(数独)を対象にします。作ったプログラムは下の通りです。たまにはPerl以外も、ということで昔を思い出してPythonで書いてみました。

#!/usr/bin/env python

import sys
#import psyco; psyco.full()

SIZE_BOARD = 9
SIZE_BLOCK = 3

sample_board = [
    [0,0,3,0,0,0,7,0,0],
    [0,2,0,4,0,6,0,8,0],
    [1,0,0,0,5,0,0,0,9],
    [0,4,0,0,0,0,0,1,0],
    [0,0,6,0,0,0,2,0,0],
    [0,1,0,0,0,0,0,3,0],
    [8,0,0,0,1,0,0,0,4],
    [0,6,0,9,0,2,0,5,0],
    [0,0,7,0,0,0,6,0,0]
]

def get_candidates(board):
    candidates = []
    # 候補集合の初期化
    for x in range(0, SIZE_BOARD):
        candidates.append([])
        for y in range(0, SIZE_BOARD):
            candidates[x].append([])
            candidates[x][y] = [1,2,3,4,5,6,7,8,9]
    
    for x in range(0, SIZE_BOARD):
        for y in range(0, SIZE_BOARD):
            if board[x][y] > 0:
                candidates[x][y] = []
                continue
            else:
                for i in range(0, SIZE_BOARD):
                    if board[x][i] in candidates[x][y]:
                        candidates[x][y].remove(board[x][i])
                    if board[i][y] in candidates[x][y]:
                        candidates[x][y].remove(board[i][y])
        area_x = int(x / SIZE_BLOCK)
        area_y = int(y / SIZE_BLOCK)
        for i in range(area_x * SIZE_BLOCK, (area_x + 1) * SIZE_BLOCK):
            for j in range(area_y * SIZE_BLOCK, (area_y + 1) * SIZE_BLOCK):
                if x == i or y == j: continue
                if board[i][j] in candidates[x][y]:
                    candidates[x][y].remove(board[i][j])
    return candidates

def is_solved(board):
    for x in range(0, SIZE_BOARD):
        for y in range(0, SIZE_BOARD):
            if board[x][y] == 0:
                return False
    return True

def solve(board):
    #print_board(board)

    if is_solved(board):
        print "solved!"
        print_board(board)
        sys.exit();

    candidates = get_candidates(board)
    num_cand = SIZE_BOARD + 1
    for x in range(0, SIZE_BOARD):
        for y in range(0, SIZE_BOARD):
            if len(candidates[x][y]) == 0: 
                continue
            elif len(candidates[x][y]) < num_cand:
                min_x = x
                min_y = y
                num_cand = len(candidates[x][y])
    if num_cand == SIZE_BOARD + 1:
        return

    for cand in candidates[min_x][min_y]:
        org = board[min_x][min_y]
        board[min_x][min_y] = cand
        solve(board)
        board[min_x][min_y] = org

def print_board(board):
    for row in sample_board:
        for i in row:
            if i == 0:
                print '.',
            else:
                print i,
        print
    print

def main():
    board = sample_board
    print_board(board)
    solve(board)

if __name__ == '__main__':
    main()

実行するとこんな感じ。psycoを使った状態で実行して3秒くらい？効率悪い書き方になっちゃってるかな。

% time python sudoku.py
. . 3 . . . 7 . .
. 2 . 4 . 6 . 8 .
1 . . . 5 . . . 9
. 4 . . . . . 1 .
. . 6 . . . 2 . .
. 1 . . . . . 3 .
8 . . . 1 . . . 4
. 6 . 9 . 2 . 5 .
. . 7 . . . 6 . .

solved!
6 5 3 8 2 4 7 9 1
5 2 1 4 7 6 9 8 3
1 3 2 7 5 8 4 6 9
2 4 8 5 9 7 3 1 6
9 8 6 3 4 1 2 7 5
4 1 5 2 6 9 8 3 7
8 7 9 6 1 3 5 2 4
7 6 4 9 3 2 1 5 8
3 9 7 1 8 5 6 4 2

3.644u 0.016s 0:03.66 99.7%     0+0k 0+0io 0pf+0w

ついでにC++でも作って見ましたよっと。無駄にクラスとか作ってみました。やっぱりC++はどういう書き方がいいのかよく分からないなぁ…。

#include <iostream>
#include <map>
#include <set>

using namespace std;

const int SIZE_BOARD = 9;
const int SIZE_BLOCK = 3;
const int SPACE = 0;

typedef map<int, set<int> > Candidates;
typedef set<int> Cand;
typedef set<int>::iterator CandIt;

class NumberPlace {
  private:
    int board[SIZE_BOARD][SIZE_BOARD];
  public:
    NumberPlace() { init(); }
    NumberPlace(int[SIZE_BOARD][SIZE_BOARD]);
    ~NumberPlace() {}
    void init();
    bool is_solved();
    void print();
    Candidates candidates();
    bool solve();
    int make_key(int x, int y) { return x * SIZE_BOARD * 10 + y; }
};

NumberPlace::NumberPlace(int board[SIZE_BOARD][SIZE_BOARD]) {
  for (int x = 0; x < SIZE_BOARD; x++) {
    for (int y = 0; y < SIZE_BOARD; y++) {
      this->board[x][y] = board[x][y];
    }
  }
}

void NumberPlace::init() {
  for (int x = 0; x < SIZE_BOARD; x++) {
    for (int y = 0; y < SIZE_BOARD; y++) {
      board[x][y] = SPACE;
    }
  }
}


bool NumberPlace::is_solved() {
  for (int x = 0; x < SIZE_BOARD; x++) {
    for (int y = 0; y < SIZE_BOARD; y++) {
      if (board[x][y] == SPACE) {
        return false;
      }
    }
  }
  return true;
}

void NumberPlace::print() {
  for (int x = 0; x < SIZE_BOARD; x++) {
    for (int y = 0; y < SIZE_BOARD; y++) {
      if (board[x][y] == SPACE) {
        cout << ".";
      } else {
        cout << board[x][y];
      }
      if (y != SIZE_BOARD-1) {
        cout << " ";
      }
    }
    cout << endl;
  }
  cout << endl;
}

Candidates NumberPlace::candidates() {
  Candidates candidates;
  for (int x = 0; x < SIZE_BOARD; x++) {
    for (int y = 0; y < SIZE_BOARD; y++) {
      Cand cand;
      for (int i = 1; i < SIZE_BOARD+1; i++) {
        cand.insert(i);
      }
      int key = make_key(x, y);
      candidates[key] = cand;
    }
  }
  for (int x = 0; x < SIZE_BOARD; x++) {
    for (int y = 0; y < SIZE_BOARD; y++) {
      int key = make_key(x, y);
      if (board[x][y] != SPACE) {
        candidates.erase(key);
        continue;
      } else {
        // 同じ行、列
        for (int i = 0; i < SIZE_BOARD; i++) {
          CandIt it;
          it = candidates[key].find(board[x][i]);
          if (it != candidates[key].end()) {
            candidates[key].erase(it);
          }
          it = candidates[key].find(board[i][y]);
          if (it != candidates[key].end()) {
            candidates[key].erase(it);
          }
        }
      }
      // 同じブロック
      int area_x = x / SIZE_BLOCK;
      int area_y = y / SIZE_BLOCK;
      int start_x = area_x * SIZE_BLOCK;
      int start_y = area_y * SIZE_BLOCK;
      for (int i = start_x; i < start_x + SIZE_BLOCK; i++) {
        for (int j = start_y; j < start_y + SIZE_BLOCK; j++) {
          if (x == i || y == j) continue;
          CandIt it;
          it = candidates[key].find(board[i][j]);
          if (it != candidates[key].end()) {
            candidates[key].erase(it);
          }
        }
      }
    }
  }
  return candidates;
}

bool NumberPlace::solve() {
  //print();

  if (is_solved()) {
    this->print();
    return true;
  }
  Candidates candidates = this->candidates();
  int min_x = -1;
  int min_y = -1;
  int num_cand = SIZE_BOARD + 1;
  for (int x = 0; x < SIZE_BOARD; x++) {
    for (int y = 0; y < SIZE_BOARD; y++) {
      int key = make_key(x, y);
      if (candidates.count(key) == 0) continue;
      int size = candidates[key].size();
      if (size != 0 && size < num_cand) {
        min_x = x;
        min_y = y;
        num_cand = candidates[key].size();
      }
    }
  }
  int key = make_key(min_x, min_y);
  Cand cand = candidates[key];
  CandIt it = cand.begin();
  while (it != cand.end()) {
    int org = board[min_x][min_y];
    board[min_x][min_y] = (int)*it;
    bool result = solve();
    if (result) {
      return true;
    }
    board[min_x][min_y] = org;
    it++;
  }
  return false;
}


int main(int argc, char **argv) {
  int board[SIZE_BOARD][SIZE_BOARD] = {
    {0,0,3,0,0,0,7,0,0},
    {0,2,0,4,0,6,0,8,0},
    {1,0,0,0,5,0,0,0,9},
    {0,4,0,0,0,0,0,1,0},
    {0,0,6,0,0,0,2,0,0},
    {0,1,0,0,0,0,0,3,0},
    {8,0,0,0,1,0,0,0,4},
    {0,6,0,9,0,2,0,5,0},
    {0,0,7,0,0,0,6,0,0}
  };
  NumberPlace numpla(board);
  numpla.print();
  numpla.solve();
  return 0;
}

毎回コードをブログにベタ張りしてるんだけど、さすがにちょと見づらいかな…。今はまだコードもそんなに長くないからいいけど、複数のファイルにわかれたりするとちょっと厳しいかも。どこかのレポジトリに置いて、リンク張るだけにした方がよさそうですね。

次はナンクロかイラストロジックを解いてみます。ナンクロは辞書を作らないといけないので、ちょっと手間がかかりますが、その分解けると面白いです。