数独を解くアルゴリズム

質問

数独を解くプログラムを再帰呼び出しなしで作ろうとしています。丁度このウェブサイト（http://sudoku.klaas.nl/）のアプレットと同じアルゴリズムが作りたいんです。

まず一番左上はしから始め、現在のセルに入れることのできる解を全てリスト化して、その一つをそのセルに入れます。次のセルに移り同じことを続けていきます。これを、解のないセルに行きあたるまでつづけていき、行き詰まった場合は一つもどり、別の解を選択したのち、次のセルに進みます。

私の作った数独のプロゴラムには、undoメソッドがあるので、これを使って前のセルに戻ることができるようにしています。

色々ためして見ましたが、うまくいくいきません。どなたか簡単なやり方があったら教えてください。

回答No.2

HarukaV49

アルゴリズムは、人間が数独を解く方法で実装してみました。
確定したところを見つけては、絞り込んでいきます。
現段階では、ステップごとに数値が確定していく問題しか解けません。
( new FSudoku(0) を実行して確認してみてください)
上級問題のように、複数の可能性があって、仮定を置かないと解けない問題は、
対応できていません。( new FSudoku(1) を実行して確認してみてください)

個人的に興味があるので、仮定を置かないと解けないような問題も
解けるようなアルゴリズムに拡張してみようと思っています。

こんな方法でも興味があるようだったら言ってください。
（万能・高速・エレガントなアルゴリズムが見つかるかどうかは分かりませんが．．．）

投稿文字数制限の関係で、GUIでデータを編集できるようにはなっていませんし、
全くオブジェクト指向設計になっていません、すみません。
一見、長いソースコードに感じられますが、半分以上はデータの入出力と
GUIコントロールのコードです。本質部分は、非常にシンプルです。

import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.util.List;
import javax.swing.*;

public class FSudoku {
private int[][] data = new int[9][9]; // 解くべき数値データ、空白セルは0で埋める
private List<Integer>[][] list = new ArrayList[9][9]; // 数値候補リスト
private int step = 0; // 計算ステップ数

private JLabel[][] label = new JLabel[9][9];
private JLabel stepLabel;

public FSudoku( int index ) {
init( index );
}

private void init( int index ) {
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.add( getNorthPanel(), BorderLayout.NORTH );
f.add( getCenterPanel(), BorderLayout.CENTER );

inputData( index );
createList();
output();

f.setSize( 800, 400 );
f.setVisible( true );
}

// サンプルデータ作成
private void inputData( int index ) {
int[][] dataSample0 = {
{ 0,0,8, 0,0,1, 0,0,6 },
{ 0,0,9, 6,0,0, 0,3,0 },
{ 5,0,0, 0,0,7, 0,8,0 },

{ 0,9,0, 2,1,0, 0,5,0 },
{ 8,5,0, 0,7,0, 0,4,3 },
{ 0,2,0, 0,0,3, 0,7,0 },

{ 0,4,0, 7,0,0, 0,0,9 },
{ 0,6,0, 0,0,2, 4,0,0 },
{ 7,0,0, 1,0,0, 3,0,0 } };

int[][] dataSample1 = {
{ 0,3,0, 5,0,0, 8,1,0 },
{ 0,0,0, 7,6,0, 0,9,0 },
{ 4,0,0, 0,0,0, 0,0,0 },

{ 0,4,3, 9,0,5, 0,0,6 },
{ 0,1,0, 0,0,0, 0,7,0 },
{ 6,0,0, 8,0,1, 9,3,0 },

{ 0,0,0, 0,0,0, 0,0,9 },
{ 0,9,0, 0,8,6, 0,0,0 },
{ 0,6,1, 0,0,2, 0,8,0 } };

switch( index ) {
case 0:
this.data = dataSample0;
break;
case 1:
this.data = dataSample1;
break;
}
}

private void calcurate() {
createList();
int sstep=0;
int c=0;
while( true ) {
if( sstep >= step ) break; // 指定ステップ数で抜ける
c = getCount();
removeNumber();
if( c == getCount() ) break; // リスト数値総数が減らなくなったら終了か行き詰まり
sstep++;
}
output();
step = sstep;
stepLabel.setText( " " + step + " " );
}

private void createList() {
for(int i=0; i<9; i++)
for(int j=0; j<9; j++) {
list[i][j] = new ArrayList<Integer>();
if( data[i][j] == 0 )
for(int v=1; v<10; v++)
if( isNotExist(i, j, v) )
list[i][j].add( v );
}
}
// 数値vはii行，jj列，ボックス内に存在しない
private boolean isNotExist( int i, int j, int v ) {
return !isExistRow(j, v) && !isExistColumn(i, v) && !isExistBox(i, j, v);
}
// 数値vが行内に存在するか
private boolean isExistRow( int j, int v ) {
for(int i=0; i<9; i++)
if( v == data[i][j] ) return true;
return false;
}
// 数値vが列内に存在するか
private boolean isExistColumn( int i, int v ) {
for(int j=0; j<9; j++)
if( v == data[i][j] ) return true;
return false;
}
// 数値vがボックス内に存在するか
private boolean isExistBox( int ii, int jj, int v ) {
for(int i=ii/3*3; i<ii/3*3+3; i++)
for(int j=jj/3*3; j<jj/3*3+3; j++)
if( v == data[i][j] ) return true;
return false;
}

// 確定した数値をリストから削る
private void removeNumber() {
for(int i=0; i<9; i++)
for(int j=0; j<9; j++)
if( list[i][j].size() == 1 ) {
int v = list[i][j].get(0);
removeInRow(i, j, v);
removeInColumn(i, j, v);
removeInBox(i, j, v);
}
}
private void removeInRow( int ii, int jj, int v ) {
for(int i=0; i<9; i++)
if( i!=ii )
list[i][jj].remove( new Integer(v) );
}
private void removeInColumn( int ii, int jj, int v ) {
for(int j=0; j<9; j++)
if( j!=jj )
list[ii][j].remove( new Integer(v) );
}
private void removeInBox( int ii, int jj, int v ) {
for(int i=ii/3*3; i<ii/3*3+3; i++)
for(int j=jj/3*3; j<jj/3*3+3; j++)
if( i!=ii || j!=jj )
list[i][j].remove( new Integer(v) );
}
// リスト内の数値の総数
private int getCount() {
int c = 0;
for(int i=0; i<9; i++)
for(int j=0; j<9; j++)
c += list[i][j].size();
return c;
}

// GUI数値出力
private void output() {
for(int i=0; i<9; i++)
for(int j=0; j<9; j++)
if( data[i][j] != 0 )
label[i][j].setText( "<html><font size=\"+2\">" + String.valueOf( data[i][j] ) );
else
label[i][j].setText( toString( list[i][j] ) );
}
private String toString( List value ) {
String s = "{";
for(int i=0,n=value.size(); i<n; i++)
s += (i==0 ? "" : ",") + value.get(i);
s += "}";
return s;
}

// GUI生成
private JPanel getCenterPanel() {
JPanel panel = new JPanel();
panel.setLayout( new GridLayout(9,9) );
for(int i=0; i<9; i++)
for(int j=0; j<9; j++) {
label[i][j] = new JLabel();
label[i][j].setHorizontalAlignment( JLabel.CENTER );
JPanel p = new JPanel();
p.setLayout( new BorderLayout() );
p.setBackground( Color.WHITE );
p.setBorder( BorderFactory.createMatteBorder(i==0?3:0, j==0?3:0,
(i+1)%3==0?3:1, (j+1)%3==0?3:1, Color.LIGHT_GRAY) );
p.add( label[i][j] );
panel.add( p );
}
return panel;
}
// GUI生成
private JPanel getNorthPanel() {
JPanel p = new JPanel();

JButton b0 = new JButton("|<");
b0.addActionListener( new ActionListener(){
public void actionPerformed(ActionEvent e) {
step = 0;
calcurate();
}} );
JButton b1 = new JButton("<");
b1.addActionListener( new ActionListener(){
public void actionPerformed(ActionEvent e) {
step--;
calcurate();
}} );
stepLabel = new JLabel( " " + step + " " );
JButton b2 = new JButton(">");
b2.addActionListener( new ActionListener(){
public void actionPerformed(ActionEvent e) {
step++;
calcurate();
}} );
JButton b3 = new JButton(">|");
b3.addActionListener( new ActionListener(){
public void actionPerformed(ActionEvent e) {
step = 100;
calcurate();
}} );
p.add( b0 );
p.add( b1 );
p.add( stepLabel );
p.add( b2 );
p.add( b3 );
return p;
}
}

回答No.1

Foxtrot_OW

>同じアルゴリズムが作りたいんです
提示されたサイトに書かれているとおり、SourceForgeでソースコードが公開されているそうですよ？まったく同じアルゴリズムにするなら、そのソースコードを読むしかありません。
https://sourceforge.net/projects/judoku

>再帰呼び出しなしで
なぜでしょうか？

>undoメソッドがあるので、これを使って前のセルに戻る
前のセルに戻るのはどのようなものでしょうか？それとも、解答を探す手順を一手手前に戻るということでしょうか？
このようなundo/redoを実現するもっとも単純でどんな場合にも使える方法は、すべての手順の状態を保存しておくことです。そうすればどの段階にでも戻れますから。
また、n手目のm手前に戻りたければ、また最初から実行しなおして(n-m)手目で停止するという方法もあるかと思います。

>色々ためして見ましたが、
どのような手段を試したのでしょうか？

>うまくいくいきません
どううまくいかなかったのでしょうか？

参考URL：

http://www.hyuki.com/writing/techask.html#level