数独解题小程序实现代码

高洛峰

发布时间：2017-03-24 13:56:42

3965人浏览过

来源于php中文网

原创

自己用java写了一个9x9数独解题的小程序，用的是穷举法，解一般的题目问题不大

代码如下：

package Test;
public class SensibleGame {
 /**
  * @param args
  */
 int[][] mainNumber;
 boolean[][] flagNumber;
 public SensibleGame(int[][] mainNumber)
 {
  this.mainNumber = mainNumber;
  flagNumber = new boolean[9][9];
  for(int i=0;i<9;i++)
  {
   for(int j=0;j<9;j++)
   {
    if(mainNumber[i][j] == 0)
    {
     flagNumber[i][j] = false;
    }
    else
    {
     flagNumber[i][j] = true;
    }
   }
  }
 }
 
 public boolean CheckRow(int i, int j)//检查(i,j)位置的行是否满足数独条件
 {
// 代码省略
   }
 
 public boolean CheckColumn(int i, int j)//检查(i,j)位置的列是否满足数独条件
 {
//代码省略
   }
 
 public boolean CheckRound(int i, int j)//检查(i,j)位置所在的3x3格是否满足数独条件
 {
//代码省略
   }
 
 public void run()//计算方法 穷举填数过程
 {
  int i = 0;
  int j = 0;
  boolean previousFlag = false;
  while(true)
  {
   if(i<0 || i>8 || j<0 || j>8)
   {
    System.out.print("下标越界！");
    return;
   }
   if(previousFlag == false)
   {
    if(flagNumber[i][j] == true)
    {
     previousFlag = false;
     if(i==8 && j==8)
     {
      System.out.print("计算结束\n");
      break;
     }
     else if(i>=0&&i<8&&j==8)
     {
      i = i + 1;
      j = 0;
      continue;
     }
     else
     {
      j = j + 1;
      continue;
     }
    }
    boolean flag = false;
    int k = 0;
    while(!flag && k<9)
    {
     mainNumber[i][j] = ++k;
     flag = CheckAll(i, j);
    }
    if(flag == true)
    {
     previousFlag = false;
     if(i==8&&j==8)
     {
      System.out.println("计算结束\n");
     }
     else if(i>=0&&i<8&&j==8)
     {
      i = i + 1;
      j = 0;
      continue;
     }
     else
     {
      j = j + 1;
      continue;
     }
    }
    else
    {
     previousFlag = true;
     mainNumber[i][j] = 0;
     if(i==0&&j==0)
     {
      System.out.println("计算失败\n");
     }
     else if(i>0&&i<9&&j==0)
     {
      i = i -1;
      j = 8;
      continue;
     }
     else
     {
      j = j - 1;
      continue;
     }
    }
   }
   else
   {
    if(flagNumber[i][j] == true)
    {
     previousFlag = true;
     if(i==0&&j==0)
     {
      System.out.println("计算失败\n");
      break;
     }
     else if(i>0&&i<9&&j==0)
     {
      i = i - 1;
      j = 8;
      continue;
     }
     else
     {
      j = j - 1;
      continue;
     }
    }
    boolean flag = false;
    while(!flag && mainNumber[i][j]<9 && mainNumber[i][j]>0)
    {
     mainNumber[i][j] = mainNumber[i][j] + 1;
     flag = CheckAll(i, j);
    }
    if(flag == true)
    {
     previousFlag = false;
     if(i==8&&j==8)
     {
      System.out.println("计算结束\n");
      break;
     }
     else if(i>=0&&i<8&&j==8)
     {
      i = i + 1;
      j = 0;
      continue;
     }
     else
     {
      j = j + 1;
      continue;
     }
    }
    else
    {
     previousFlag = true;
     mainNumber[i][j] = 0;
     if(i==0&&j==0)
     {
      System.out.println("计算失败\n");
      break;
     }
     else if(i>0&&i<9&&j==0)
     {
      i = i - 1;
      j = 8;
      continue;
     }
     else
     {
      j = j - 1;
      continue;
     }
    }
   }
  }
 }
 
 
 public void Print()//打印
 {
  int k =0;
  for(int i=0;i<9;i++)
  {
   for(int j=0;j<9;j++)
   {
    System.out.print(mainNumber[i][j]);
    if((++k)%9 == 0)
    {
     System.out.println("");
    }
   }
  }
 }
 
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int[][] mainNumber = {{0,9,0,0,1,0,0,2,0},
         {7,0,0,0,0,8,3,0,0},
         {0,0,0,0,0,0,4,0,0},
         {8,3,0,0,0,0,0,1,0},
         {0,0,6,0,0,0,0,0,5},
         {0,4,0,7,0,0,0,0,0},
         {0,0,0,0,0,7,8,9,0},
         {0,2,1,0,0,0,0,0,0},
         {3,0,0,0,5,0,0,0,6},
        };
  SensibleGame sensibleGame = new SensibleGame(mainNumber);
  sensibleGame.run();
  sensibleGame.Print();
 }
}

运行结果如下：