数独

問題を与えられたら、それを解くプログラムを作ってみました。
すべての問題はムリですが、中級レベルぐらいの問題なら解けます。

import java.util.ArrayList;

/**
 * 数独を解く.
 */
public class Sudoku {
    static class マス {
        boolean 候補 = new boolean[9];
        int 数字;   // 1..9,未決定は0
        マス(int num) {
            this.数字 = num;
            if (num == 0) {
                for (int i=0; i<候補.length; i++) {
                    候補[i] = true;
                }
            }
        }
        int get候補数() {
            if (数字 != 0) return 0;
            int count = 0;
            for (int i=0; i<候補.length; i++) {
                if (候補[i]) count++;
            }
            return count;
        }
        void 候補から外す(int num) {
            if (数字 == 0) 候補[num-1] = false;
        }
        /** 数字を決定する */
        void set数字(int x) {
            数字 = x;
            for (int i=0; i<候補.length; i++) {
                候補[i] = false;
            }
        }
        boolean もし候補が１つなら確定させる() {
            if (数字 != 0) return false;
            int num = -1;
            for (int i=0; i<候補.length; i++) {
                if (! 候補[i]) {
                    if (num == -1)
                        num = i+1;
                    else
                        return false;
                }
            }
            set数字(num);
            return true;
        }
        public String toString() {
            String s = ""+数字+"[";
            for (int i=0; i<9; i++) {
                s += 候補[i] ? (""+(i+1)) : "-";
            }
            return s + "]";
        }
    }
    
    
    static class 盤面 {
        final int START = new int { 0, 3, 6 };
        マス cells = new マス[9][9];
        盤面(int init) {
            for (int y=0; y<9; y++) {
                for (int x=0; x<9; x++) {
                    cells[y][x] = new マス(init[y][x]);
                }
            }
        }
        /** 
         * ９つのマスを返す。
         * patternが'x'のときには横１列の９つのセルを返す。
         * patternが'y'のときには縦１列の９つのセルを返す。
         * patternが'3'のときには、３ｘ３の９つのセルを返す。
         * @param pattern   'x','y','3'
         * @param pos       0..8
         * @return
         */
        マス getマス(char pattern, int pos) {
            マス result = new マス[9];
            switch (pattern) {
            case 'x':
                return cells[pos];
            case 'y':
                for (int x=0; x<9; x++) {
                    result[x] = cells[x][pos];
                }
                return result;
            case '3':
                for (int dy=0; dy<3; dy++) {
                    for (int dx=0; dx<3; dx++) {
                        result[dy*3+dx] = cells[START[pos/3]+dy][START[pos%3]+dx];
                    }
                }
                return result;
            }
            return null;
        }
        boolean is全部解けた() {
            for (int y=0; y<9; y++) {
                for (int x=0; x<9; x++) {
                    if (cells[y][x].数字 == 0) return false;
                }
            }
            return true;
        }
        int get未決定のマスの数() {
            int count = 0;
            for (int y=0; y<9; y++) {
                for (int x=0; x<9; x++) {
                    if (cells[y][x].数字 == 0) count++;
                }
            }
            return count;
        }
        void print() {
            for (int y=0; y<9; y++) {
                for (int x=0; x<9; x++) {
                    if (cells[y][x].数字 == 0) {
                        System.out.print(" -");
                    } else {
                        System.out.print(" "+cells[y][x].数字);
                    }
                }
                System.out.println();
            }
        }
        void dump() {
            for (int y=0; y<9; y++) {
                for (int x=0; x<9; x++) {
                    System.out.print(cells[y][x]);
                }
                System.out.println();
            }
            System.out.println("未決定のマスの数="+get未決定のマスの数());
        }
        void 候補を絞る(int xpos, int ypos, int num) {
            // 横の列にはnumはない
            for (int pos=0; pos<9; pos++) {
                if (pos != xpos) cells[ypos][pos].候補から外す(num);
                if (pos != ypos) cells[pos][xpos].候補から外す(num);
            }
            int ystart = ypos / 3 * 3;
            int xstart = xpos / 3 * 3;
            for (int dy=0; dy<3; dy++) {
                for (int dx=0; dx<3; dx++) {
                    cells[ystart+dy][xstart+dx].候補から外す(num);
                }
            }
        }
        void 候補を絞る() {
            // 数字が確定しているとき、その列、行、３ｘ３の中にその数字はない。
            for (int y=0; y<9; y++) {
                for (int x=0; x<9; x++) {
                    if (cells[y][x].数字 != 0) {
                        候補を絞る(x, y, cells[y][x].数字);
                    }
                }
            }
            // 数字が未確定で、候補が１つのとき、数字を確定させる。
            for (int y=0; y<9; y++) {
                for (int x=0; x<9; x++) {
                    cells[y][x].もし候補が１つなら確定させる();
                }
            }
            // 数字が未確定で、その列、行、３ｘ３の他のセルにその候補がなければ、それがその数字になる。
            for (int pos=0; pos<9; pos++) {
                候補が他になければ確定させる(getマス('x', pos));
                候補が他になければ確定させる(getマス('y', pos));
                候補が他になければ確定させる(getマス('3', pos));
            }
            for (int pos=0; pos<9; pos++) {
                共通部分にのみ候補があればそれ以外に候補はない(getマス('x', pos), getマス('3', pos/3));
                共通部分にのみ候補があればそれ以外に候補はない(getマス('x', pos), getマス('3', pos/3+3));
                共通部分にのみ候補があればそれ以外に候補はない(getマス('x', pos), getマス('3', pos/3+6));
                共通部分にのみ候補があればそれ以外に候補はない(getマス('y', pos), getマス('3', pos%3));
                共通部分にのみ候補があればそれ以外に候補はない(getマス('y', pos), getマス('3', pos%3+3));
                共通部分にのみ候補があればそれ以外に候補はない(getマス('y', pos), getマス('3', pos%3+6));
            }
        }

        /**
         * 1[---------]
         * 2[---------]
         * 3[---------]
         * ?[---4-6789]
         * ?[---456789] ←５の候補はこのセルしかない。５に確定する。
         * ?[---4-6789]
         * ?[---4-6789]
         * ?[---4-6789]
         * ?[---4-6789]
         */
        void 候補が他になければ確定させる(マス cells) {
            // １〜９の数字に対して確定しているかどうかと、候補の数を数える。
            boolean determinated = new boolean[9];
            int 候補数 = new int[9];
            for (int i=0; i<9; i++) {
                if (cells[i].数字 != 0) {
                    determinated[cells[i].数字-1] = true;
                } else {
                    for (int b=0; b<9; b++) {
                        if (cells[i].候補[b]) 候補数[b]++;
                    }
                }
            }
            // １〜９の数字に対して候補の数が１個なら、その数字に確定する。
            for (int n=0; n<9; n++) {
                if (determinated[n]) continue;
                if (候補数[n] == 1) {
                    // その候補を持つセルを確定させる
                    for (int i=0; i<9; i++) {
                        if (cells[i].数字 == 0 && cells[i].候補[n]) {
                            cells[i].set数字(n+1);
                            break;
                        }
                    }
                }
            }
        }
        /**
         * A A A  A A A  C C C
         * ? ? ?  ? ? ?  B B B
         * ? ? ?  ? ? ?  B B B
         * 
         * ? ? ?  ? ? ?  ? ? ?
         * ? ? ?  ? ? ?  ? ? ?
         * ? ? ?  ? ? ?  ? ? ?
         * 
         * ? ? ?  ? ? ?  ? ? ?
         * ? ? ?  ? ? ?  ? ? ?
         * ? ? ?  ? ? ?  ? ? ?
         * もし、ある候補がCの中にのみあってBの中になければ、Aの中にもない。
         * 同様に、ある候補がCの中にのみあってAの中になければ、Bの中にもない。
         * さらに具体的に。左がAのセル、右がBのセル、上３つがCの共通のセル。
         * [123456789]左と同一セル
         * [123456789]左と同一セル
         * [123456789]左と同一セル
         * [-23456789][123456789] ←Ｂ側のセルから1の候補が外れる
         * [-23456789][123456789] ←Ｂ側のセルから1の候補が外れる
         * [-23456789][123456789] ←Ｂ側のセルから1の候補が外れる
         * [-23456789][123456789] ←Ｂ側のセルから1の候補が外れる
         * [-23456789][123456789] ←Ｂ側のセルから1の候補が外れる
         * [-23456789][123456789] ←Ｂ側のセルから1の候補が外れる
         * 一方から見て、共有するセル内にしかない候補があれば、
         * それはもう一方の共有していないセルにはない。
         * 上記の例では、候補１は共有セルにしかない。Ａのみのセルには
         * 存在しない。従って、１は必ず共有セルにあることになり、
         * Ｂのみのセルには１の候補は外すことができる。
         */
        void 共通部分にのみ候補があればそれ以外に候補はない(マス cellsA, マス cellsB) {
            // 共通部分と残りの部分に分ける
            ArrayList Aだけ = toList(cellsA);
            ArrayList Bだけ = toList(cellsB);
            ArrayList 共通 = new ArrayList();
            for (int i=8; i>=0; i--) {
                Object test = Aだけ.get(i);
                if (Bだけ.contains(test)) {
                    Aだけ.remove(test);
                    Bだけ.remove(test);
                    共通.add(test);
                }
            }
            assert 共通.size() == 3;
            assert Aだけ.size() == 6;
            assert Bだけ.size() == 6;
            for (int n=1; n<=9; n++) {
                if (is確定したか(共通, n)) continue;
                if (is確定したか(Aだけ, n)) continue;
                if (is確定したか(Bだけ, n)) continue;
                if (has候補(共通, n)) {
                    if (! has候補(Aだけ, n) && has候補(Bだけ, n)) {
                        for (int i=0; i<9; i++) System.out.print(cellsA[i]);
                        System.out.println();
                        for (int i=0; i<9; i++) System.out.print(cellsB[i]);
                        System.out.println();
                        System.out.println("候補から外す(Bだけ, x)"+n);
                        候補から外す(Bだけ, n);
                    } 
                    else if (! has候補(Bだけ, n) && has候補(Aだけ, n)) {
                        System.out.println("候補から外す(Aだけ, x)"+n);
                        候補から外す(Aだけ, n);
                    }
                }
            }
        }
        private boolean is確定したか(ArrayList cells, int n) {
            for (int i=0; i cells) {
        ArrayList result = new ArrayList();
        for (int i=0; i args) {
        // http://www.kojima-cci.or.jp/~fuji/numplace/problems/0010.html
        int 問題0010 = new int {
            {0,4,0, 6,0,0, 0,0,9},
            {5,0,0, 7,0,0, 0,2,0},
            {0,0,0, 8,0,0, 1,0,0},

            {4,6,8, 0,0,7, 0,0,0},
            {0,0,0, 0,3,0, 0,0,0},
            {0,0,0, 2,0,0, 5,7,6},
            
            {0,0,1, 0,0,8, 0,0,0},
            {0,3,0, 0,0,5, 0,0,4},
            {7,0,0, 0,0,1, 0,5,0}
        };
        // http://www.kojima-cci.or.jp/~fuji/numplace/problems/0004.html
        int 問題0004 = new int {
            {6,8,0, 0,0,0, 0,0,0},
            {5,0,0, 7,1,0, 0,3,0},
            {0,0,0, 4,0,0, 0,0,2},

            {0,0,0, 0,0,9, 1,0,0},
            {0,0,4, 0,0,0, 6,0,0},
            {0,0,9, 8,0,0, 0,0,0},
            
            {2,0,0, 0,0,3, 0,0,0},
            {0,1,0, 0,2,6, 0,0,5},
            {0,0,0, 0,0,0, 0,4,9}
        };
        // http://www.kojima-cci.or.jp/~fuji/numplace/problems/0024.html
        int 問題0024 = new int {
            {0,0,0, 0,0,7, 2,0,0},
            {0,6,1, 0,2,0, 0,8,0},
            {2,0,0, 9,0,0, 0,3,0},
            
            {7,0,0, 0,0,0, 4,0,0},
            {0,9,0, 0,0,0, 0,6,0},
            {0,0,4, 0,0,0, 0,0,9},
            
            {0,2,0, 0,0,3, 0,0,4},
            {0,3,0, 0,6,0, 1,7,0},
            {0,0,9, 7,0,0, 0,0,0},
        };
        // ひな形
        int 問題0000 = new int {
            {0,0,0, 0,0,0, 0,0,0},
            {0,0,0, 0,0,0, 0,0,0},
            {0,0,0, 0,0,0, 0,0,0},
            
            {0,0,0, 0,0,0, 0,0,0},
            {0,0,0, 0,0,0, 0,0,0},
            {0,0,0, 0,0,0, 0,0,0},
            
            {0,0,0, 0,0,0, 0,0,0},
            {0,0,0, 0,0,0, 0,0,0},
            {0,0,0, 0,0,0, 0,0,0},
        };
        if (new Sudoku().解く(new 盤面(問題0024)))
            System.out.println("楽勝だぜ！");
        else
            System.out.println("むりポ");
    }
}

アルゴリズムは簡単。
最初はすべてのセルに１〜９の候補がありますが、問題の初期状態と、縦・横・３ｘ３のセルを見ながら候補を絞り込んでいきます。
絞り込む方法をいくつか用意し、それを順番に数回繰り返しているだけです。
途中で全部解ければ終わり。
比較的簡単な方法しか実装していないけれど、結構賢いですよ。
それに速いです。