Aritalab:Lecture/Programming/Java/Sudoku

Revision as of 13:06, 7 October 2010

数独を解いてみる

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[i][col] != 0)
            list[sudoku[i][col] - 1] = true;
      }

    void checkBlock(int row, int col, boolean[] list)
      {
        for (int i = 0; i < 3; i)
            {
              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)
            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;
                // この時点ではsolveSudoku()を再帰的に呼び出しており、既にi,j以降の
                // マス目は試した後になる。そのためスキャンを終了する。
                return;
              }
        printSudoku();
      }

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

    /*
     * 数独読み込みルーチン
     */
    public int[][] 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;
              }
          }
        catch (Exception e)
          {
            e.printStackTrace();
          }
        return sudoku;
      }

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

問題サンプル

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