数独の問題数を数え上げる in Java DouKaku?

数独の問題数を数え上げる

4×4のマスを2×2の4ブロックに区切り、いくつかのマスに1～4の数字を配置します。

以下、空白のマスすべてに数字を補い、縦、横、および各ブロックについて1～4の数字が
それぞれ一個ずつ含まれている状態にすることが可能で、かつその方法が一意であるもの、
つまり数独の問題として成立するもののみを考えます。

4 1 | 2           4 1 | 2 3
2   | 4 1         2 3 | 4 1
----+-----  --->  ----+----
  2 | 3 4         1 2 | 3 4
3 4 | 1           3 4 | 1 2

このようなものの総数を「初期配置の数字の個数ごとに」カウントしてください。

余力のある人は、極小な配置に限定してカウントしてみてください。
ただし、極小な配置とは、どの数字を取り除いても数独の問題として
不成立になる配置を指すものとします。


まどろっこしい言い回しになってしまいましたが、
一言で言えば「数独の問題数を数え上げよ」という問題になります。

参考：http://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC

post comment

Posted feedbacks - Java

288通りの最終盤面を取得し（Sudoku2x2#next()）、
各マスの数字の有無の全パターン（2^16-2通り）について
問題が解けるかどうか（SudokuSolver2x2#solve()）調べています。
要は総当たりです。

私の環境では、実行完了まで3分以上かかっています。

エレガントからはほど遠いコードですが
答えまで出る投稿が少ないので、参考までに。

$ time java Sudoku2x2
1 0
2 0
3 0
4 25728
5 284160
6 1041408
7 2141184
8 2961024
9 2958336
10 2204928
11 1239552
12 522624
13 161280
14 34560
15 4608

real    3m7.374s
user    3m6.433s
sys     0m0.334s

import java.util.*;

public class Sudoku2x2 implements Iterator<int[]>, SudokuCommon2x2 {

    private int count;
    private final int maxCount;
    private int[] nextValue;

    public static void main(String[] args) {
        countUpAll();
    }

    public static void countUpAll() {
        Sudoku2x2 sudoku = new Sudoku2x2();
        SudokuSolver2x2 solver = new SudokuSolver2x2();
        int[] counter = new int[16];
        int[] nums, nums2 = new int[16];
        
        while (sudoku.hasNext()) {
            nums = sudoku.next();
            
            for (int i = 1; i < 0xffff; ++i) {
                int n = 0;
                Arrays.fill(nums2, 0);
                for (int j = 0; j < 16; ++j) {
                    if(0<(i&(1<<j))) {
                        nums2[j] = nums[j];
                        ++n;
                    }
                }
                if(solver.solve(nums2)) ++counter[n];
            }
        }
        
        for (int i = 1; i <= 15; ++i) {
            System.out.println(i + " " + counter[i]);
        }
    }

    public Sudoku2x2() {
        count = 0;
        maxCount = (int) Math.pow(DIGITS_PATTERN.length, 4);
        nextValue = new int[16];
        generateNext();
    }

    public boolean hasNext() {
        return nextValue!=null;
    }

    public int[] next() {
        if(hasNext()) {
            int[] returnValue = new int[16];
            System.arraycopy(nextValue, 0, returnValue, 0, 16);
            generateNext();
            return returnValue;
        }
        throw new NoSuchElementException();
    }

    private void generateNext() {
        do {
            for (int c0 = count, i = 0; i < 4; ++i) {
                System.arraycopy(DIGITS_PATTERN[c0%24], 0, nextValue, i*4, 4);
                if(i==1) {
                    if(!containsAllNumbers(nextValue, BOX[0])) break;
                    if(!containsAllNumbers(nextValue, BOX[1])) break;
                }
                c0 = c0 / 24;
            }
            ++count;
        } while(
            (
            !containsAllNumbers(nextValue, BOX[2])
            || !containsAllNumbers(nextValue, BOX[3])
            || !containsAllNumbers(nextValue, COLUMN[0])
            || !containsAllNumbers(nextValue, COLUMN[1])
            || !containsAllNumbers(nextValue, COLUMN[2])
            || !containsAllNumbers(nextValue, COLUMN[3])
            ) && count < maxCount
        );
        if(maxCount <= count) nextValue = null;
    }
    
    private static boolean containsAllNumbers(int[] block, int[] index) {
        int test = 0;
        for(int i=0;i<index.length;++i) {
            test |= 1<<(block[index[i]]-1);
        }
        return test==15;
    }

    public void remove() { throw new UnsupportedOperationException(); }
}

class SudokuSolver2x2 implements SudokuCommon2x2 {
    SudokuCell[] grid;
    SudokuCell[][] allBlocks;
    int status;
    
    SudokuSolver2x2() {
        grid = new SudokuCell[16];
        for(int i=0;i<grid.length;++i) grid[i] = new SudokuCell();
        allBlocks = new SudokuCell[][] {
            getBlock(BOX[0]),
            getBlock(BOX[1]),
            getBlock(BOX[2]),
            getBlock(BOX[3]),
            getBlock(COLUMN[0]),
            getBlock(COLUMN[1]),
            getBlock(COLUMN[2]),
            getBlock(COLUMN[3]),
            getBlock(ROW[0]),
            getBlock(ROW[1]),
            getBlock(ROW[2]),
            getBlock(ROW[3])
        };
    }
        
    public boolean solve(int[] nums) {
        status = 0;
        for(int i=0;i<grid.length;++i) {
            grid[i].value = i<nums.length?nums[i]:0;
            grid[i].possibleList = 0<grid[i].value?0:15;
        }
        while(true) {
            solveInner();
            switch(status) {
                case -1: return false; // logical error
                case  1: return true;  // solved
            }
        }
    }
    
    protected void solveInner() {
        boolean modified = false, solved = true;
        int test = 0;
        for(int i=0;i<allBlocks.length;++i) {
            for(int j=0;j<allBlocks[i].length;++j) {
                modified |= allBlocks[i][j].updatePossibleList(allBlocks[i]);
                test |= 1<<(allBlocks[i][j].value-1);
            }
            solved &= (test==15);
        }
        if(!modified&&!solved) status = -1;
        if(solved) status = 1;
    }
    
    protected SudokuCell[] getBlock(int[] indexes) {
        SudokuCell[] returnValue = new SudokuCell[indexes.length];
        for(int i=0;i<indexes.length;++i)
            returnValue[i] = grid[indexes[i]];
        return returnValue;
    }

    protected class SudokuCell {
        int value;
        int possibleList;
        
        public boolean isPossible(int i) {
            return 0<i && (0<(possibleList & 1<<(i-1)));
        }

        private void setValue(int i) {
            value = i;
            possibleList = 0;
        }
        
        public boolean updatePossibleList(SudokuCell[] sp) {
            boolean updated = false;
            for(int i=0;i<sp.length;++i) {
                if(this==sp[i]) continue;
                if(isPossible(sp[i].value)) {
                    possibleList &= ~(1<<(sp[i].value-1));
                    updated = true;
                }
            }
            if(updated) check();
            return updated;
        }
        
        public void check() {
            if(value==0) {
                switch(possibleList) {
                    case 1: setValue(1); break;
                    case 2: setValue(2); break;
                    case 4: setValue(3); break;
                    case 8: setValue(4); break;
                }
            }
        }
    }
}

interface SudokuCommon2x2 {
    public static final int[][] COLUMN = {
        { 0, 4, 8, 12 }, { 1, 5, 9, 13 }, { 2, 6, 10, 14 }, { 3, 7, 11, 15 }
    };
    public static final int[][] ROW = {
        { 0, 1, 2, 3 }, { 4, 5, 6, 7 }, { 8, 9, 10, 11 }, { 12, 13, 14, 15 }
    };
    public static final int[][] BOX = {
        { 0, 1, 4, 5 }, { 2, 3, 6, 7 }, { 8, 9, 12, 13 }, { 10, 11, 14, 15 }
    };
    public static final int[][] DIGITS_PATTERN = {
        {1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4},
        {1, 3, 4, 2}, {1, 4, 2, 3}, {1, 4, 3, 2},
        {2, 1, 3, 4}, {2, 1, 4, 3}, {2, 3, 1, 4},
        {2, 3, 4, 1}, {2, 4, 1, 3}, {2, 4, 3, 1},
        {3, 1, 2, 4}, {3, 1, 4, 2}, {3, 2, 1, 4},
        {3, 2, 4, 1}, {3, 4, 1, 2}, {3, 4, 2, 1},
        {4, 1, 2, 3}, {4, 1, 3, 2}, {4, 2, 1, 3},
        {4, 2, 3, 1}, {4, 3, 1, 2}, {4, 3, 2, 1}
    };
}

DouKaku?

数独の問題数を数え上げる

Posted feedbacks - Java

Index

Feed

Other

Link

Pathtraq