Java數獨生成器（最簡單的解決方案）

Question

我在這裏看到的最後一個問題：Sudoku - Region testing我問過如何檢查3x3區域，有人能給我一個滿意的答案（儘管它涉及很多修補程序以使其工作，因爲他們沒有提到類table_t是什麼。）

我完成了項目，並能夠創建一個數獨生成器，但它感覺它是人爲的。我覺得我通過採取非常暴力的方式來產生難題，從而以某種方式過於複雜。

本質上，我的目標是創建一個9×9的網格與9×3×3區域。每行/列/區域只能使用數字1-9一次。

我解決這個問題的方法是使用一個二維數組隨機放置數字，一次3行。一旦3行完成，它將檢查3行，3個區域和每個垂直列到第3個位置。在它迭代完成之前，它會做同樣的事情直到數組被填滿爲止，但由於我正在用rand進行填充，並且多次檢查每個行/列/區域，所以感覺效率很低。

是否有一種「更簡單」的方式去做這個除了2d數組之外的任何類型的數據構造？是否有更簡單的方法來檢查每個3x3區域可能與檢查垂直或水平更好一致？從計算的角度來看，我看不出有太多的方法可以更有效地做到這一點，而不會顯着增加代碼的大小。

Answer 1

我前段時間建立了一個數獨遊戲，並使用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/

Answer 2

我認爲你可以使用一維數組，在幾乎相同的方式一維數組可以模擬一棵二叉樹。例如，要查看數字下面的值，請在索引中添加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); 
    } 

} 

Answer 3

試試這個代碼：

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(); 
    } 
} 
} 

Answer 4

import java.util.Random; 
import java.util.Scanner; 

public class sudoku { 

    /** 
    * @antony 
    */ 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     int p = 1; 
     Random r = new Random(); 
     int i1=r.nextInt(8); 
     int firstval = i1; 
     while (p == 1) { 
      int x = firstval, v = 1; 
      int a[][] = new int[9][9]; 
      int b[][] = new int[9][9]; 
      for (int i = 0; i < 9; i++) { 
       for (int j = 0; j < 9; j++) { 
        if ((x + j + v) <= 9) 
         a[i][j] = j + x + v; 
        else 
         a[i][j] = j + x + v - 9; 
        if (a[i][j] == 10) 
         a[i][j] = 1; 
        // System.out.print(a[i][j]+" "); 
       } 
       x += 3; 
       if (x >= 9) 
        x = x - 9; 
       // System.out.println(); 
       if (i == 2) { 
        v = 2; 
        x = firstval; 
       } 
       if (i == 5) { 
        v = 3; 
        x = firstval; 
       } 

      } 
      int eorh; 
      Scanner in = new Scanner(System.in); 
      System.out 
        .println("hey lets play a game of sudoku:take down the question and replace the 0's with your digits and complete the game by re entering your answer"); 
      System.out.println("enter your option 1.hard 2.easy"); 
      eorh = in.nextInt(); 
      switch (eorh) { 
      case 1: 
       b[0][0] = a[0][0]; 
       b[8][8] = a[8][8]; 
       b[0][3] = a[0][3]; 
       b[0][4] = a[0][4]; 
       b[1][2] = a[1][2]; 
       b[1][3] = a[1][3]; 
       b[1][6] = a[1][6]; 
       b[1][7] = a[1][7]; 
       b[2][0] = a[2][0]; 
       b[2][4] = a[2][4]; 
       b[2][8] = a[2][8]; 
       b[3][2] = a[3][2]; 
       b[3][8] = a[3][8]; 
       b[4][2] = a[4][2]; 
       b[4][3] = a[4][3]; 
       b[4][5] = a[4][5]; 
       b[4][6] = a[4][6]; 
       b[5][0] = a[5][0]; 
       b[5][6] = a[5][6]; 
       b[6][0] = a[6][0]; 
       b[6][4] = a[6][4]; 
       b[6][8] = a[6][8]; 
       b[7][1] = a[7][1]; 
       b[7][2] = a[7][2]; 
       b[7][5] = a[7][5]; 
       b[7][6] = a[7][6]; 
       b[8][4] = a[8][4]; 
       b[8][5] = a[8][5]; 
       b[0][0] = a[0][0]; 
       b[8][8] = a[8][8]; 

       break; 
      case 2: 
       b[0][3] = a[0][3]; 
       b[0][4] = a[0][4]; 
       b[1][2] = a[1][2]; 
       b[1][3] = a[1][3]; 
       b[1][6] = a[1][6]; 
       b[1][7] = a[1][7]; 
       b[1][8] = a[1][8]; 
       b[2][0] = a[2][0]; 
       b[2][4] = a[2][4]; 
       b[2][8] = a[2][8]; 
       b[3][2] = a[3][2]; 
       b[3][5] = a[3][5]; 
       b[3][8] = a[3][8]; 
       b[4][0] = a[4][0]; 
       b[4][2] = a[4][2]; 
       b[4][3] = a[4][3]; 
       b[4][4] = a[4][4]; 
       b[4][5] = a[4][5]; 
       b[4][6] = a[4][6]; 
       b[5][0] = a[5][0]; 
       b[5][1] = a[5][1]; 
       b[5][4] = a[5][4]; 
       b[5][6] = a[5][6]; 
       b[6][0] = a[6][0]; 
       b[6][4] = a[6][4]; 
       b[6][6] = a[6][6]; 
       b[6][8] = a[6][8]; 
       b[7][0] = a[7][0]; 
       b[7][1] = a[7][1]; 
       b[7][2] = a[7][2]; 
       b[7][5] = a[7][5]; 
       b[7][6] = a[7][6]; 
       b[8][2] = a[8][2]; 
       b[8][4] = a[8][4]; 
       b[8][5] = a[8][5]; 
       break; 
      default: 
       System.out.println("entered option is incorrect"); 
       break; 
      } 

      for (int y = 0; y < 9; y++) { 
       for (int z = 0; z < 9; z++) { 
        System.out.print(b[y][z] + " "); 
       } 
       System.out.println(""); 
      } 
      System.out.println("enter your answer"); 
      int c[][] = new int[9][9]; 
      for (int y = 0; y < 9; y++) { 
       for (int z = 0; z < 9; z++) { 
        c[y][z] = in.nextInt(); 
       } 
      } 
      for (int y = 0; y < 9; y++) { 
       for (int z = 0; z < 9; z++) 
        System.out.print(c[y][z] + " "); 
       System.out.println(); 
      } 
      int q = 0; 
      for (int y = 0; y < 9; y++) { 
       for (int z = 0; z < 9; z++) 
        if (a[y][z] == c[y][z]) 
         continue; 
        else { 
         q++; 
         break; 
        } 
      } 
      if (q == 0) 
       System.out 
         .println("the answer you have entered is correct well done"); 
      else 
       System.out.println("oh wrong answer better luck next time"); 
      System.out 
        .println("do you want to play a different game of sudoku(1/0)"); 
      p = in.nextInt(); 
      firstval=r.nextInt(8); 
      /*if (firstval > 8) 
       firstval -= 9;*/ 
     } 

    } 
}