Aritalab:Lecture/Programming/Java/Sudoku

From Metabolomics.JP
< Aritalab:Lecture | Programming | Java(Difference between revisions)
Jump to: navigation, search
 
(6 intermediate revisions by one user not shown)
Line 2: Line 2:
 
数独の全解探索を行うプログラムです。
 
数独の全解探索を行うプログラムです。
 
スペース区切りで与えられた9x9の枡(ブランクは0で表現する)を読み込み、空いているポジションに入りうる数字を全て試しています。通常の9x9数独だと、一瞬で解けます。
 
スペース区切りで与えられた9x9の枡(ブランクは0で表現する)を読み込み、空いているポジションに入りうる数字を全て試しています。通常の9x9数独だと、一瞬で解けます。
 +
数独を [[Aritalab:Lecture/Programming/Java/AlgorithmX|Algorithm X]] (Dancing Links) で解こうという話がウェブ上で見られますが、解くだけなら以下のコードで十分です。
 +
少し理論的な背景は、[[Aritalab:Lecture/Algorithm/Sudoku|こちらのページ]]を参照してください。
 +
 +
;数独を解くプログラム Sudoku.java
 
<pre>
 
<pre>
 
import java.io.BufferedReader;
 
import java.io.BufferedReader;
Line 87: Line 91:
 
                 && row < 9)
 
                 && row < 9)
 
               {
 
               {
                 if (line.startsWith(";"))
+
                 if (line.startsWith(";")) //コメント行読み飛ばし
 
                   continue;
 
                   continue;
 
                 String[] numbers = line.split(" ");
 
                 String[] numbers = line.split(" ");
 
                 for (int i = 0; i < 9; i&#43;&#43;)
 
                 for (int i = 0; i < 9; i&#43;&#43;)
 
                   {
 
                   {
                     if (numbers[i].trim().equals(""))
+
                     sudoku[row][i] = Integer
                      sudoku[row][i] = 0;
+
                        .parseInt(numbers[i]);
                    else
+
                      sudoku[row][i] = Integer
+
                          .parseInt(numbers[i]);
+
 
                   }
 
                   }
 
                 row&#43;&#43;;
 
                 row&#43;&#43;;
Line 116: Line 117:
 
</pre>
 
</pre>
  
問題サンプル
+
;問題サンプルファイル sudokuSample.txt
 
<pre>
 
<pre>
 +
; セミコロンで始まる行はコメントとみなされます。
 +
; スペース区切りで、空の枡目は0を入れます。
 
1 0 3 0 8 0 0 6 0
 
1 0 3 0 8 0 0 6 0
 
8 0 0 7 0 6 0 0 9
 
8 0 0 7 0 6 0 0 9

Latest revision as of 14:52, 22 August 2017

[edit] 数独を解いてみる

数独の全解探索を行うプログラムです。 スペース区切りで与えられた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
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox