Aritalab:Lecture/Programming/Java/Sudoku

数独を解いてみる

数独の全解探索を行うプログラムです。 スペース区切りで与えられた9x9の枡（ブランクは0で表現する）を読み込み、空いているポジションに入りうる数字を全て試しています。通常の9x9数独だと、一瞬で解けます。 数独を Algorithm X (Dancing Links) で解こうという話がウェブ上で見られますが、解くだけなら以下のコードで十分です。 少し理論的な背景は、こちらのページを参照してください。

数独を解くプログラム Sudoku.java

import java.io.BufferedReader;
import java.io.FileReader;

public class Sudoku
  {
    int[][] sudoku = new int[9][9];
    
    void checkRow(int row, boolean[] list)
      {
        for (int i = 0; i < 9; i++)
          if (sudoku[row][i] != 0)
            list[sudoku[row][i] - 1] = true;
      }

    void checkColumn(int col, boolean[] list)
      {
        for (int i = 0; i < 9; i++)
          if (sudoku[i][col] != 0)
            list[sudoku[i][col] - 1] = true;
      }

    void checkBlock(int row, int col, boolean[] list)
      {
        for (int i = 0; i < 3; i++)
          for (int j = 0; j < 3; j++)
            {
              int r = i + (row / 3) * 3;
              int c = j + (col / 3) * 3;
              if (sudoku[r][c] != 0)
                list[sudoku[r][c] - 1] = true;
            }
      }

    public void solveSudoku()
      {// for文を使ってまだ埋まっていないマス目があるかチェック
        for (int i = 0; i < 9; i++)
          for (int j = 0; j < 9; j++)
            if (sudoku[i][j] == 0)
              {
                // 埋まっていない部分を見つけたので
                // ポジション(i,j)に入る候補を探す
                boolean[] list = new boolean[9];
                checkRow(i, list);
                checkColumn(j, list);
                checkBlock(i, j, list);
                for (int k = 0; k < 9; k++)
                  if (!list[k])
                    {
                      sudoku[i][j] = k + 1;
                      solveSudoku();
                    }
                sudoku[i][j] = 0;//全解探索を行うため現在位置を0に戻す。
                // この時点ではsolveSudoku()を再帰的に呼び出しており、既にi,j以降の
                // マス目は試した後になっている。
                return;
              }
        printSudoku();//全ての升目が埋まっていたらプリントアウト。
      }

    void printSudoku()
      {
        for (int i = 0; i < 9; i++)
          {
            for (int j = 0; j < 9; j++)
              System.out.print(sudoku[i][j] + " ");
            System.out.println();
          }
        System.out.println();
      }

    /*
     * 数独読み込みルーチン
     */
    public void readSudoku(String file)
      {
        try
          {
            BufferedReader br = new BufferedReader(
                new FileReader(file));
            String line;
            int row = 0;
            while (((line = br.readLine()) != null)
                && row < 9)
              {
                if (line.startsWith(";")) //コメント行読み飛ばし
                  continue;
                String[] numbers = line.split(" ");
                for (int i = 0; i < 9; i++)
                  {
                    sudoku[row][i] = Integer
                        .parseInt(numbers[i]);
                  }
                row++;
              }
          }
        catch (Exception e)
          {
            e.printStackTrace();
          }
      }

    static public void main(String[] args)
      {
        Sudoku su = new Sudoku();
        su.readSudoku("sudokuSample.txt");
        su.solveSudoku();
      }
  }

問題サンプルファイル sudokuSample.txt

;　セミコロンで始まる行はコメントとみなされます。
; スペース区切りで、空の枡目は0を入れます。
1 0 3 0 8 0 0 6 0
8 0 0 7 0 6 0 0 9
0 5 7 0 1 0 8 0 4
2 0 0 6 7 0 0 9 0
0 0 4 0 0 0 6 0 0
0 1 0 0 4 9 0 0 7
0 6 0 0 9 0 2 0 1
3 0 1 2 0 7 0 4 0
0 2 9 0 0 0 5 0 0