6

ここで見た最後の質問: Sudoku - Region testing で、3x3 領域を確認する方法を尋ねたところ、誰かが満足のいく答えを得ることができました (ただし、希望どおりに機能させるには多くの調整が必要でした。クラス table_t が何であったかは言及しません。)

プロジェクトを終了し、数独ジェネレーターを作成することができましたが、それは不自然な気がします。そして、パズルを生成するために非常に強引なアプローチをとることで、どうにか物事を複雑にしすぎたように感じます.

基本的に私の目標は、9 ～ 3x3 の領域を持つ 9x9 グリッドを作成することです。各行 / 列 / 領域では、1 ～ 9 の数字を 1 回だけ使用する必要があります。

これを解決する方法は、2 次元配列を使用して、一度に 3 行ずつランダムに数字を配置することでした。3行が完了すると、3行、3つの領域、および3番目の位置までの各垂直列がチェックされます。配列がいっぱいになるまで反復すると同じことが行われますが、ランドでいっぱいになっていて、各行/列/領域を複数回チェックしていたため、非常に非効率的でした。

2次元配列以外の任意のタイプのデータ構造でこれを行うための「より簡単な」方法はありますか? 垂直または水平のいずれかをより適切にチェックすることと一致する可能性のある各 3x3 領域をチェックする簡単な方法はありますか? 計算の観点からは、コードのサイズを劇的に肥大化させずに、より効率的に計算を行う方法があまりにも多くありません。

4

4 に答える 4

9

少し前に数独ゲームを作成し、Donald Knuth によるダンシング リンク アルゴリズムを使用してパズルを生成しました。これらのサイトは、アルゴリズムの学習と実装に非常に役立つことがわかりました

http://en.wikipedia.org/wiki/Dancing_Links

http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/

http://garethrees.org/2007/06/10/zendoku-generation/

于 2011-08-06T00:46:29.807 に答える
0

このコードを試してください：

package com;
public class Suduku{
    public static void main(String[] args ){
        int k=0;
        int fillCount =1;
        int subGrid=1;
        int N=3;
        int[][] a=new int[N*N][N*N];
    for (int i=0;i<N*N;i++){
        if(k==N){
            k=1;
            subGrid++;
            fillCount=subGrid;
        }else{
            k++;
            if(i!=0)
            fillCount=fillCount+N;
        }
        for(int j=0;j<N*N;j++){
            if(fillCount==N*N){
                a[i][j]=fillCount;
                fillCount=1;
                System.out.print("  "+a[i][j]);
            }else{
                a[i][j]=fillCount++;
                System.out.print("  "+a[i][j]);
            }
        }
        System.out.println();
    }
}
}
于 2013-03-31T04:27:10.310 に答える
0

1D 配列がバイナリ ツリーをモデル化できるのとほぼ同じ方法で、1D 配列を使用できると思います。たとえば、数字の下の値を見るには、インデックスに 9 を追加します。

私はこれを作ったばかりですが、このようなものは機能しますか？ 

private boolean makePuzzle(int [] puzzle,  int i)
{
     for (int x = 0; x< 10 ; x++)
     {
           if (//x satisfies all three conditions for the current square i)
           {
                puzzle[i]=x;
                if (i==80) return true //terminal condition, x fits in the last square
                else
                    if makePuzzle(puzzle, i++);//find the next x
                         return true; 
           }// even though x fit in this square, an x couldn't be 
             // found for some future square, try again with a new x
     }
     return false; //no value for x fit in the current square
 } 

 public static void main(String[] args ) 
 {
  int[] puzzle = new int[80];
  makePuzzle(puzzle,0);
  // print out puzzle here
 }

編集：Javaで配列を使用してからしばらく経ちました。構文を台無しにして申し訳ありません。疑似コードと考えてください:)

これが私のコメントで以下に説明されているコードです。

public class Sudoku
{
    public int[] puzzle = new int[81];
    private void makePuzzle(int[] puzzle, int i)
    {
        for (int x = 1; x< 10 ; x++)
        {
            puzzle[i]=x;
            if(checkConstraints(puzzle))
            {
                if (i==80)//terminal condition
                {
                    System.out.println(this);//print out the completed puzzle
                        puzzle[i]=0;
                    return;
                }
                else
                    makePuzzle(puzzle,i+1);//find a number for the next square                          
            }
            puzzle[i]=0;//this try didn't work, delete the evidence 
        }       
    }
    private boolean checkConstraints(int[] puzzle)
    {
        int test;
     //test that rows have unique values    
      for (int column=0; column<9; column++)
        {
            for (int row=0; row<9; row++)
            {
                test=puzzle[row+column*9];
                for (int j=0;j<9;j++)
                {
                    if(test!=0&&  row!=j&&test==puzzle[j+column*9])
                        return false;
                }
            }
        }
        //test that columns have unique values
        for  (int column=0; column<9; column++) 
        {
             for(int row=0; row<9; row++)
            {
                test=puzzle[column+row*9];
                for (int j=0;j<9;j++)
                {
                    if(test!=0&&row!=j&&test==puzzle[column+j*9])
                        return false;
                }
            }
        }
        //implement region test here
        int[][] regions = new int[9][9];
        int[] regionIndex ={0,3,6,27,30,33,54,57,60};
        for (int region=0; region<9;region++) //for each region
        {

            int j =0;
            for (int k=regionIndex[region];k<regionIndex[region]+27; k=(k%3==2?k+7:k+1))
                {
                    regions[region][j]=puzzle[k];
                    j++;
                }
        }
        for (int i=0;i<9;i++)//region counter
        {
            for (int j=0;j<9;j++)
            {
                for (int k=0;k<9;k++)
                {
                    if (regions[i][j]!=0&&j!=k&&regions[i][j]==regions[i][k])
                    return false;
                }

            }
        }
    return true;

    }
    public String toString()
    {
        String string= "";
        for (int i=0; i <9;i++)
        {
            for  (int j = 0; j<9;j++)
            {
                string = string+puzzle[i*9+j];
            }
            string =string +"\n";
        }
        return string;
    }
    public static void main(String[] args)
    {
        Sudoku sudoku=new Sudoku();
        sudoku.makePuzzle(sudoku.puzzle, 0);
    }

}
于 2011-08-06T03:28:56.310 に答える