CSDN首页 空间 新闻 论坛 Blog 下载 读书 网摘 搜索 .NET Java 视频 接项目 求职 在线学习 买书 程序员 通知
山寨机中的战斗机! 程序优化工程师到底对IT界有没有贡献
CSDN社区
搜索 收藏 打印 关闭
CSDN社区 >  Java >  J2SE / 基础类

经典题目求算法

楼主iwillfling(牛哥哥)2006-03-14 21:19:59 在 Java / J2SE / 基础类 提问

?   -   ?   -   3   -   9   -   ?   -   ?   -   ?   -   ?   -   ?  
  ?   -   9   -   7   -   ?   -   ?   -   1   -   5   -   2   -   ?  
  ?   -   8   -   ?   -   ?   -   ?   -   7   -   ?   -   4   -   9    
  ?   -   4   -   5   -   ?   -   ?   -   ?   -   ?   -   ?   -   7  
  ?   -   ?   -   ?   -   8   -   ?   -   ?   -   ?   -   ?   -   ?  
  2   -   ?   -   ?   -   ?   -   ?   -   ?   -   9   -   ?   -   ?  
  7   -   1   -   ?   -   ?   -   ?   -   ?   -   ?   -   9   -   ?  
  ?   -   6   -   9   -   3   -   ?   -   ?   -   1   -   8   -   ?      
  ?   -   ?   -   ?   -   ?   -   ?   -   9   -   7   -   ?   -   ?  
  以上是9*9的数组,每一行,每一列都是1~9,9个数字,而且没有重复.  
  填出?处的数字.用java怎么实现? 问题点数:20、回复次数:28Top

1 楼goalshx(天天天蓝)回复于 2006-03-14 23:10:43 得分 0

不会    
  关注中~  
  期待牛人出现Top

2 楼gifted1982(玩游戏的Coder)回复于 2006-03-15 09:35:40 得分 0

还真挺难呀,不太会,等好的方法Top

3 楼TONYBLARED(奔放的犀牛)回复于 2006-03-15 12:28:22 得分 0

盼正确答案,盼就一个字。Top

4 楼seu_cose(专注于通信技术)回复于 2006-03-15 12:56:41 得分 0

文曲星上的   游戏?Top

5 楼jacbo(今天你坚持了没有)回复于 2006-03-15 13:07:51 得分 0

学习Top

6 楼superman421(38度的雪)回复于 2006-03-15 14:21:57 得分 0

markTop

7 楼qybao(阿宝)回复于 2006-03-17 09:30:28 得分 20

此题感觉比较有意思,所以写了个算法求解,但从算法上看,应该有多解,碍于算法的复杂度,我只做了一种求解  
  以下的算法是一种求解的算法,如果大家有好的算法,也希望能贴出来一起研究  
   
  import   java.util.*;  
   
  //?   -   ?   -   3   -   9   -   ?   -   ?   -   ?   -   ?   -   ?  
  //?   -   9   -   7   -   ?   -   ?   -   1   -   5   -   2   -   ?  
  //?   -   8   -   ?   -   ?   -   ?   -   7   -   ?   -   4   -   9  
  //?   -   4   -   5   -   ?   -   ?   -   ?   -   ?   -   ?   -   7  
  //?   -   ?   -   ?   -   8   -   ?   -   ?   -   ?   -   ?   -   ?  
  //2   -   ?   -   ?   -   ?   -   ?   -   ?   -   9   -   ?   -   ?  
  //7   -   1   -   ?   -   ?   -   ?   -   ?   -   ?   -   9   -   ?  
  //?   -   6   -   9   -   3   -   ?   -   ?   -   1   -   8   -   ?  
  //?   -   ?   -   ?   -   ?   -   ?   -   9   -   7   -   ?   -   ?  
   
  //求解结果  
  //1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  //3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  //5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  //6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  //9   -   7   -   2   -   8   -   1   -   6   -   4   -   5   -   3  
  //2   -   3   -   8   -   7   -   5   -   4   -   9   -   6   -   1  
  //7   -   1   -   6   -   5   -   2   -   3   -   8   -   9   -   4  
  //4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  //8   -   5   -   4   -   6   -   3   -   9   -   7   -   1   -   2  
   
  class   NineX   {  
  String   result[][]   =   {{"?","?","3","9","?","?","?","?","?"},    
    {"?","9","7","?","?","1","5","2","?"},    
    {"?","8","?","?","?","7","?","4","9"},    
    {"?","4","5","?","?","?","?","?","7"},  
    {"?","?","?","8","?","?","?","?","?"},  
    {"2","?","?","?","?","?","9","?","?"},  
    {"7","1","?","?","?","?","?","9","?"},  
    {"?","6","9","3","?","?","1","8","?"},  
    {"?","?","?","?","?","9","7","?","?"}};  
   
  ArrayList   alrow[]       =   new   ArrayList[9];       //每行可以取的数字  
  ArrayList   alcol[]       =   new   ArrayList[9];       //每列可以取的数字  
  ArrayList   alcel[][]   =   new   ArrayList[9][9];//每个?处可取的数字  
  ArrayList   alerr[]       =   new   ArrayList[9*9];   //无效的组合  
  ArrayList   alhis           =   new   ArrayList();         //回退信息保留  
     
  public   static   void   main(String[]   args)   {  
  NineX   nx   =   new   NineX();  
  nx.show();  
  }  
   
  public   NineX()   {  
  int   i,   j;  
  for   (i=0;   i<9;   i++)   {  
  alrow[i]   =   new   ArrayList();  
  alcol[i]   =   new   ArrayList();  
  for   (j=0;   j<9;   j++)   {  
  alcel[i][j]   =   new   ArrayList();  
  alerr[i*9+j]   =   new   ArrayList();  
  }  
  }  
   
  initialize();  
  }  
   
  public   void   show()   {  
  if   (combine())   {  
  print();  
  }  
  }  
   
  private   void   initialize()   {  
  int   i,   j,   k;  
  String   row,   col,   s;  
   
  //find   the   remain   numbers   in   each   row   or   col  
  String   num[]   =   {"1","2","3","4","5","6","7","8","9"};  
  for   (i=0;   i<9;   i++)   {  
  row   =   "";  
  col   =   "";  
  for   (j=0;   j<9;   j++)   {  
  if   (!result[i][j].equals("?"))   {  
  row   +=   result[i][j];  
  }  
  if   (!result[j][i].equals("?"))   {  
  col   +=   result[j][i];  
  }  
  }  
  for   (j=0;   j<9;   j++)   {  
  if   (row.indexOf(num[j])<0   &&   alrow[i].indexOf(num[j])<0)   {  
  alrow[i].add(num[j]);  
  }  
  if   (col.indexOf(num[j])<0   &&   alcol[i].indexOf(num[j])<0)   {    
  alcol[i].add(num[j]);  
  }  
  }  
  }  
   
  //peek   possible   number   in   each   row  
  // System.out.println("---------------rows---------------");  
  // for   (i=0;   i<alrow.length;   i++)   {  
  // System.out.println("rows["+i+"]="+alrow[i]);  
  // }  
   
  //peek   possible   number   in   each   col  
  // System.out.println("---------------cols---------------");  
  // for   (i=0;   i<alcol.length;   i++)   {  
  // System.out.println("cols["+i+"]="+alcol[i]);  
  // }  
   
  //find   the   same   number   in   each   row   or   col  
  for   (i=0;   i<9;   i++)   {  
  for   (j=0;   j<9;   j++)   {  
  if   (result[i][j].equals("?"))   {  
  for   (k=0;   k<alrow[i].size();   k++)   {  
  s   =   alrow[i].get(k).toString();  
  if   (alcol[j].contains(s)   &&   alcel[i][j].indexOf(s)<0)   {  
  alcel[i][j].add(s);  
  }  
  }  
  }  
  }  
  }  
   
  //peek   the   possible   numbers   in   each   cell  
  // System.out.println("---------------cells---------------");  
  // for   (i=0;   i<9;   i++)   {  
  // for   (j=0;   j<9;   j++)   {  
  // System.out.println("cells["+i+"]["+j+"]="+alcel[i][j]);  
  // }  
  // if   (i   <   8)   {  
  // System.out.println("-----------------------------------");  
  // }  
  // }  
  }  
   
  private   boolean   combine()   {  
   
  int   celidx   =   0;  
  int   row,   col;  
  int   i,   j,   k;  
  boolean   used,   found;  
  String   s,   buf="";  
  alhis.clear();  
   
  while   (celidx   <   9*9)   {  
  row   =   celidx   /   9;  
  col   =   celidx   %   9;  
   
  if   (result[row][col].equals("?"))   {  
  found   =   false;  
  for   (i=0;   i<alcel[row][col].size();   i++)   {  
  s   =   alcel[row][col].get(i).toString();  
  if   (alerr[celidx].contains(buf+s))   {  
  continue;  
  }  
   
  used   =   false;  
  //row   check  
  for   (j=0;   j<col;   j++)   {  
  if   (result[row][j].equals(s))   {  
  used   =   true;  
  break;  
  }  
  }  
  if   (used)   {  
  alerr[celidx].add(buf+s);  
  continue;  
  }  
   
  //col   check  
  for   (j=0;   j<row;   j++)   {  
  if   (result[j][col].equals(s))   {  
  used   =   true;  
  break;  
  }  
  }  
  if   (used)   {  
  alerr[celidx].add(buf+s);  
  continue;  
  }  
   
  //peak   combination  
  // System.out.println("----------possible   combination----------");  
  // System.out.println(buf+s);  
  // System.out.println("cell_index="+celidx);  
   
  //possible   number  
  result[row][col]   =   s;  
  buf   +=   s;  
  found   =   true;  
  alhis.add(String.valueOf(celidx));  
  break;  
  }  
   
  if   (!   found)   {  
  //peak   combination  
  // System.out.println("----------impossible   combination----------");  
  // System.out.println(buf);  
  // System.out.println("cell_index="+celidx);  
   
  //move   back   to   last   cell  
  if   (alhis.size()   >   0)   {  
  celidx   =   Integer.parseInt(alhis.get(alhis.size()-1).toString());  
  alhis.remove(alhis.size()-1);  
  }   else   {  
  celidx--;  
  }  
  if   (celidx   <   0)   {  
  System.out.println("----------impossible   result----------");  
  return   false;  
  }  
   
  //move   back   to   last   combination  
  if   (!   alerr[celidx].contains(buf))   {  
  alerr[celidx].add(buf);  
  }  
  if   (buf.length()   <=   1)   {  
  buf   =   "";  
  }   else   {  
  buf   =   buf.substring(0,   buf.length()-1);  
  }  
   
  //trun   back   to   the   original   value  
  result[celidx/9][celidx%9]   =   "?";  
  continue;  
  }  
   
  }    
   
  celidx++;  
   
  }  
   
  return   true;  
  }  
   
  private   void   print()   {  
  int   i,   j;  
  System.out.println("---------------result---------------");  
  for   (i=0;   i<9;   i++)   {  
  for   (j=0;   j<8;   j++)   {  
  System.out.print(result[i][j]+"   -   ");  
  }  
  System.out.println(result[i][j]);  
  }  
  }  
  }  
   
  Top

8 楼qybao(阿宝)回复于 2006-03-17 09:32:27 得分 0

以下是修改上面的算法,求多解,但没有测试,太耗时间  
  import   java.util.*;  
   
  //?   -   ?   -   3   -   9   -   ?   -   ?   -   ?   -   ?   -   ?  
  //?   -   9   -   7   -   ?   -   ?   -   1   -   5   -   2   -   ?  
  //?   -   8   -   ?   -   ?   -   ?   -   7   -   ?   -   4   -   9  
  //?   -   4   -   5   -   ?   -   ?   -   ?   -   ?   -   ?   -   7  
  //?   -   ?   -   ?   -   8   -   ?   -   ?   -   ?   -   ?   -   ?  
  //2   -   ?   -   ?   -   ?   -   ?   -   ?   -   9   -   ?   -   ?  
  //7   -   1   -   ?   -   ?   -   ?   -   ?   -   ?   -   9   -   ?  
  //?   -   6   -   9   -   3   -   ?   -   ?   -   1   -   8   -   ?  
  //?   -   ?   -   ?   -   ?   -   ?   -   9   -   7   -   ?   -   ?  
   
  //1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  //3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  //5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  //6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  //9   -   7   -   2   -   8   -   1   -   6   -   4   -   5   -   3  
  //2   -   3   -   8   -   7   -   5   -   4   -   9   -   6   -   1  
  //7   -   1   -   6   -   5   -   2   -   3   -   8   -   9   -   4  
  //4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  //8   -   5   -   4   -   6   -   3   -   9   -   7   -   1   -   2  
   
  class   NineX   {  
  String   result[][]   =   {{"?","?","3","9","?","?","?","?","?"},    
    {"?","9","7","?","?","1","5","2","?"},    
    {"?","8","?","?","?","7","?","4","9"},    
    {"?","4","5","?","?","?","?","?","7"},  
    {"?","?","?","8","?","?","?","?","?"},  
    {"2","?","?","?","?","?","9","?","?"},  
    {"7","1","?","?","?","?","?","9","?"},  
    {"?","6","9","3","?","?","1","8","?"},  
    {"?","?","?","?","?","9","7","?","?"}};  
   
  ArrayList   alrow[]       =   new   ArrayList[9];       //每行可以取的数字  
  ArrayList   alcol[]       =   new   ArrayList[9];       //每列可以取的数字  
  ArrayList   alcel[][]   =   new   ArrayList[9][9];//每个?处可取的数字  
  ArrayList   alerr[]       =   new   ArrayList[9*9];   //无效的组合  
  ArrayList   alhis           =   new   ArrayList();         //回退信息保留  
     
  public   static   void   main(String[]   args)   {  
  NineX   nx   =   new   NineX();  
  nx.show();  
  }  
   
  public   NineX()   {  
  int   i,   j;  
  for   (i=0;   i<9;   i++)   {  
  alrow[i]   =   new   ArrayList();  
  alcol[i]   =   new   ArrayList();  
  for   (j=0;   j<9;   j++)   {  
  alcel[i][j]   =   new   ArrayList();  
  alerr[i*9+j]   =   new   ArrayList();  
  }  
  }  
   
  initialize();  
  }  
   
  public   void   show()   {  
  if   (combine())   {  
  print();  
  }  
  }  
   
  private   void   initialize()   {  
  int   i,   j,   k;  
  String   row,   col,   s;  
   
  //find   the   remain   numbers   in   each   row   or   col  
  String   num[]   =   {"1","2","3","4","5","6","7","8","9"};  
  for   (i=0;   i<9;   i++)   {  
  row   =   "";  
  col   =   "";  
  for   (j=0;   j<9;   j++)   {  
  if   (!result[i][j].equals("?"))   {  
  row   +=   result[i][j];  
  }  
  if   (!result[j][i].equals("?"))   {  
  col   +=   result[j][i];  
  }  
  }  
  for   (j=0;   j<9;   j++)   {  
  if   (row.indexOf(num[j])<0   &&   alrow[i].indexOf(num[j])<0)   {  
  alrow[i].add(num[j]);  
  }  
  if   (col.indexOf(num[j])<0   &&   alcol[i].indexOf(num[j])<0)   {    
  alcol[i].add(num[j]);  
  }  
  }  
  }  
   
  //peek   possible   number   in   each   row  
  // System.out.println("---------------rows---------------");  
  // for   (i=0;   i<alrow.length;   i++)   {  
  // System.out.println("rows["+i+"]="+alrow[i]);  
  // }  
   
  //peek   possible   number   in   each   col  
  // System.out.println("---------------cols---------------");  
  // for   (i=0;   i<alcol.length;   i++)   {  
  // System.out.println("cols["+i+"]="+alcol[i]);  
  // }  
   
  //find   the   same   number   in   each   row   or   col  
  for   (i=0;   i<9;   i++)   {  
  for   (j=0;   j<9;   j++)   {  
  if   (result[i][j].equals("?"))   {  
  for   (k=0;   k<alrow[i].size();   k++)   {  
  s   =   alrow[i].get(k).toString();  
  if   (alcol[j].contains(s)   &&   alcel[i][j].indexOf(s)<0)   {  
  alcel[i][j].add(s);  
  }  
  }  
  }  
  }  
  }  
   
  //peek   the   possible   numbers   in   each   cell  
  // System.out.println("---------------cells---------------");  
  // for   (i=0;   i<9;   i++)   {  
  // for   (j=0;   j<9;   j++)   {  
  // System.out.println("cells["+i+"]["+j+"]="+alcel[i][j]);  
  // }  
  // if   (i   <   8)   {  
  // System.out.println("-----------------------------------");  
  // }  
  // }  
  }  
   
  private   boolean   combine()   {  
   
  int   celidx   =   0;  
  int   row,   col;  
  int   i,   j,   k;  
  boolean   used,   found;  
  String   s,   buf="";  
  alhis.clear();  
  int   count   =   0;   //追加有无?果信息  
   
  while   (celidx   <   9*9)   {  
  row   =   celidx   /   9;  
  col   =   celidx   %   9;  
   
  if   (result[row][col].equals("?"))   {  
  found   =   false;  
  for   (i=0;   i<alcel[row][col].size();   i++)   {  
  s   =   alcel[row][col].get(i).toString();  
  if   (alerr[celidx].contains(buf+s))   {  
  continue;  
  }  
   
  used   =   false;  
  //row   check  
  for   (j=0;   j<col;   j++)   {  
  if   (result[row][j].equals(s))   {  
  used   =   true;  
  break;  
  }  
  }  
  if   (used)   {  
  alerr[celidx].add(buf+s);  
  continue;  
  }  
   
  //col   check  
  for   (j=0;   j<row;   j++)   {  
  if   (result[j][col].equals(s))   {  
  used   =   true;  
  break;  
  }  
  }  
  if   (used)   {  
  alerr[celidx].add(buf+s);  
  continue;  
  }  
   
  //peak   combination  
  // System.out.println("----------possible   combination----------");  
  // System.out.println(buf+s);  
  // System.out.println("cell_index="+celidx);  
   
  //possible   number  
  result[row][col]   =   s;  
  buf   +=   s;  
  found   =   true;  
  alhis.add(String.valueOf(celidx));  
  break;  
  }  
   
  if   (!   found)   {  
  //peak   combination  
  // System.out.println("----------impossible   combination----------");  
  // System.out.println(buf);  
  // System.out.println("cell_index="+celidx);  
   
  //move   back   to   last   cell  
  if   (alhis.size()   >   0)   {  
  celidx   =   Integer.parseInt(alhis.get(alhis.size()-1).toString());  
  alhis.remove(alhis.size()-1);  
  }   else   {  
  celidx--;  
  }  
  if   (celidx   <   0)   {  
  if   (count>0)   {  
  System.out.println("----------total   result----------");  
  System.out.println("total   result:   "   +   count);  
   
  return   true;  
  }   else   {  
  System.out.println("----------impossible   result----------");  
  return   false;  
  }  
  }  
   
  //move   back   to   last   combination  
  if   (!   alerr[celidx].contains(buf))   {  
  alerr[celidx].add(buf);  
  }  
  if   (buf.length()   <=   1)   {  
  buf   =   "";  
  }   else   {  
  buf   =   buf.substring(0,   buf.length()-1);  
  }  
   
  //trun   back   to   the   original   value  
  result[celidx/9][celidx%9]   =   "?";  
  continue;  
  }  
   
  }    
   
  celidx++;  
  if   (celidx   ==   9*9)   {   //继续回退查找结果  
  //move   back   to   last   combination  
  if   (!   alerr[celidx].contains(buf))   {  
  alerr[celidx].add(buf);  
  }  
  if   (buf.length()   <=   1)   {  
  buf   =   "";  
  }   else   {  
  buf   =   buf.substring(0,   buf.length()-1);  
  }  
   
  //trun   back   to   the   original   value  
  result[celidx/9][celidx%9]   =   "?";  
  }  
   
  }  
   
  return   true;  
  }  
   
  private   void   print()   {  
  int   i,   j;  
  System.out.println("---------------result---------------");  
  for   (i=0;   i<9;   i++)   {  
  for   (j=0;   j<8;   j++)   {  
  System.out.print(result[i][j]+"   -   ");  
  }  
  System.out.println(result[i][j]);  
  }  
  }  
  }  
   
  Top

9 楼wddlqd(跑,跑,跑,一直跑到天涯海角)回复于 2006-03-17 10:29:21 得分 0

楼上的真牛啊。。。。Top

10 楼welfarefanwei(伟大)回复于 2006-03-17 10:33:59 得分 0

高手,  
  coding。。。Top

11 楼xubearxx()回复于 2006-03-17 10:49:04 得分 0

太牛B了吧  
  强!!!!Top

12 楼liyi_cdut(猪头毅)回复于 2006-03-17 11:18:53 得分 0

太强了~~Top

13 楼hswr(化石)回复于 2006-03-17 11:32:24 得分 0

继续关注^Top

14 楼discolt(枫)回复于 2006-03-17 11:52:45 得分 0

按照之前qybao(阿宝)的一种求解方法不是很难,  
   
  只需每次填充元素时检查横列和纵列是否有重复元素,填充后递增。  
   
  难的是多个组合的解法,那不是一般难,那是相当的难。  
   
  Top

15 楼wddlqd(跑,跑,跑,一直跑到天涯海角)回复于 2006-03-17 11:58:32 得分 0

求多组的那个我的机子运行了10分钟出来个fatal   error。。。。。。。Top

16 楼fenglibing(流星)回复于 2006-03-17 12:11:09 得分 0

中國的程序員都這樣就好了Top

17 楼sandyen(杉叶)回复于 2006-03-17 12:21:44 得分 0

markTop

18 楼qybao(阿宝)回复于 2006-03-17 13:31:50 得分 0

to   wddlqd(快乐的人)    
  我在自己的机器跑了20分钟,没问题,不过20分钟只也只是一小部分的解而已,不知道谁有空能把程序跑完一遍看看。(我估计跑到后面可能会出现内存溢出,主要是alerr这个集合会不断庞大,我在自己机器跑20分钟,发现内存涨到40M,可怕)  
   
  import   java.util.*;  
   
  //?   -   ?   -   3   -   9   -   ?   -   ?   -   ?   -   ?   -   ?  
  //?   -   9   -   7   -   ?   -   ?   -   1   -   5   -   2   -   ?  
  //?   -   8   -   ?   -   ?   -   ?   -   7   -   ?   -   4   -   9  
  //?   -   4   -   5   -   ?   -   ?   -   ?   -   ?   -   ?   -   7  
  //?   -   ?   -   ?   -   8   -   ?   -   ?   -   ?   -   ?   -   ?  
  //2   -   ?   -   ?   -   ?   -   ?   -   ?   -   9   -   ?   -   ?  
  //7   -   1   -   ?   -   ?   -   ?   -   ?   -   ?   -   9   -   ?  
  //?   -   6   -   9   -   3   -   ?   -   ?   -   1   -   8   -   ?  
  //?   -   ?   -   ?   -   ?   -   ?   -   9   -   7   -   ?   -   ?  
   
  class   NineXAll   {  
  String   result[][]   =   {{"?","?","3","9","?","?","?","?","?"},    
    {"?","9","7","?","?","1","5","2","?"},    
    {"?","8","?","?","?","7","?","4","9"},    
    {"?","4","5","?","?","?","?","?","7"},  
    {"?","?","?","8","?","?","?","?","?"},  
    {"2","?","?","?","?","?","9","?","?"},  
    {"7","1","?","?","?","?","?","9","?"},  
    {"?","6","9","3","?","?","1","8","?"},  
    {"?","?","?","?","?","9","7","?","?"}};  
   
  ArrayList   alrow[]       =   new   ArrayList[9];  
  ArrayList   alcol[]       =   new   ArrayList[9];  
  ArrayList   alcel[][]   =   new   ArrayList[9][9];  
  ArrayList   alerr[]       =   new   ArrayList[9*9];  
  ArrayList   alhis           =   new   ArrayList();  
  long   count;  
     
  public   static   void   main(String[]   args)   {  
  NineXAll   nx   =   new   NineXAll();  
  nx.show();  
  }  
   
  public   NineXAll()   {  
  int   i,   j;  
  for   (i=0;   i<9;   i++)   {  
  alrow[i]   =   new   ArrayList();  
  alcol[i]   =   new   ArrayList();  
  for   (j=0;   j<9;   j++)   {  
  alcel[i][j]   =   new   ArrayList();  
  alerr[i*9+j]   =   new   ArrayList();  
  }  
  }  
   
  initialize();  
  }  
   
  public   void   show()   {  
  combine();  
  }  
   
  private   void   initialize()   {  
  int   i,   j,   k;  
  String   row,   col,   s;  
   
  //find   the   remain   numbers   in   each   row   or   col  
  String   num[]   =   {"1","2","3","4","5","6","7","8","9"};  
  for   (i=0;   i<9;   i++)   {  
  row   =   "";  
  col   =   "";  
  for   (j=0;   j<9;   j++)   {  
  if   (!result[i][j].equals("?"))   {  
  row   +=   result[i][j];  
  }  
  if   (!result[j][i].equals("?"))   {  
  col   +=   result[j][i];  
  }  
  }  
  for   (j=0;   j<9;   j++)   {  
  if   (row.indexOf(num[j])<0   &&   alrow[i].indexOf(num[j])<0)   {  
  alrow[i].add(num[j]);  
  }  
  if   (col.indexOf(num[j])<0   &&   alcol[i].indexOf(num[j])<0)   {    
  alcol[i].add(num[j]);  
  }  
  }  
  }  
   
  //peek   possible   number   in   each   row  
  // System.out.println("---------------rows---------------");  
  // for   (i=0;   i<alrow.length;   i++)   {  
  // System.out.println("rows["+i+"]="+alrow[i]);  
  // }  
   
  //peek   possible   number   in   each   col  
  // System.out.println("---------------cols---------------");  
  // for   (i=0;   i<alcol.length;   i++)   {  
  // System.out.println("cols["+i+"]="+alcol[i]);  
  // }  
   
  //find   the   same   number   in   each   row   or   col  
  for   (i=0;   i<9;   i++)   {  
  for   (j=0;   j<9;   j++)   {  
  if   (result[i][j].equals("?"))   {  
  for   (k=0;   k<alrow[i].size();   k++)   {  
  s   =   alrow[i].get(k).toString();  
  if   (alcol[j].contains(s)   &&   alcel[i][j].indexOf(s)<0)   {  
  alcel[i][j].add(s);  
  }  
  }  
  }  
  }  
  }  
   
  //peek   the   possible   numbers   in   each   cell  
  // System.out.println("---------------cells---------------");  
  // for   (i=0;   i<9;   i++)   {  
  // for   (j=0;   j<9;   j++)   {  
  // System.out.println("cells["+i+"]["+j+"]="+alcel[i][j]);  
  // }  
  // if   (i   <   8)   {  
  // System.out.println("-----------------------------------");  
  // }  
  // }  
  }  
   
  private   boolean   combine()   {  
   
  int   celidx   =   0;  
  int   row,   col;  
  int   i,   j,   k;  
  boolean   used,   found;  
  String   s,   buf="";  
  alhis.clear();  
  count   =   0;  
   
  while   (celidx   <   9*9)   {  
  row   =   celidx   /   9;  
  col   =   celidx   %   9;  
   
  if   (result[row][col].equals("?"))   {  
  found   =   false;  
  for   (i=0;   i<alcel[row][col].size();   i++)   {  
  s   =   alcel[row][col].get(i).toString();  
  if   (alerr[celidx].contains(buf+s))   {  
  continue;  
  }  
   
  used   =   false;  
  //row   check  
  for   (j=0;   j<col;   j++)   {  
  if   (result[row][j].equals(s))   {  
  used   =   true;  
  break;  
  }  
  }  
  if   (used)   {  
  alerr[celidx].add(buf+s);  
  continue;  
  }  
   
  //col   check  
  for   (j=0;   j<row;   j++)   {  
  if   (result[j][col].equals(s))   {  
  used   =   true;  
  break;  
  }  
  }  
  if   (used)   {  
  alerr[celidx].add(buf+s);  
  continue;  
  }  
   
  //peak   combination  
  // System.out.println("----------possible   combination----------");  
  // System.out.println(buf+s);  
  // System.out.println("cell_index="+celidx);  
   
  //possible   number  
  result[row][col]   =   s;  
  buf   +=   s;  
  found   =   true;  
  alhis.add(String.valueOf(celidx));  
  break;  
  }  
   
  if   (!   found)   {  
  //peak   combination  
  // System.out.println("----------impossible   combination----------");  
  // System.out.println(buf);  
  // System.out.println("cell_index="+celidx);  
   
  //move   back   to   last   cell  
  if   (alhis.size()   >   0)   {  
  celidx   =   Integer.parseInt(alhis.get(alhis.size()-1).toString());  
  alhis.remove(alhis.size()-1);  
  }   else   {  
  celidx--;  
  }  
  if   (celidx   <   0)   {  
  if   (count   >   0)   {  
  System.out.println("----------total   result----------");  
  System.out.println(count);  
  return   true;  
  }   else   {  
  System.out.println("----------impossible   result----------");  
  return   false;  
  }  
  }  
   
  //move   back   to   last   combination  
  if   (!   alerr[celidx].contains(buf))   {  
  alerr[celidx].add(buf);  
  }  
  if   (buf.length()   <=   1)   {  
  buf   =   "";  
  }   else   {  
  buf   =   buf.substring(0,   buf.length()-1);  
  }  
   
  //trun   back   to   the   original   value  
  result[celidx/9][celidx%9]   =   "?";  
  continue;  
  }  
   
  }    
   
  celidx++;  
  if   (celidx   ==   9*9)   {  
  count++;  
  print();  
  // System.out.println(count);  
   
  //move   back   to   last   cell  
  if   (alhis.size()   >   0)   {  
  celidx   =   Integer.parseInt(alhis.get(alhis.size()-1).toString());  
  alhis.remove(alhis.size()-1);  
  }   else   {  
  celidx--;  
  }  
  //peak   rolling   back  
  // System.out.println("----------roll   back----------");  
  // System.out.println(buf);  
  // System.out.println("cell_index="+celidx);  
   
  //move   back   to   last   combination  
  if   (!   alerr[celidx].contains(buf))   {  
  alerr[celidx].add(buf);  
  }  
  if   (buf.length()   <=   1)   {  
  buf   =   "";  
  }   else   {  
  buf   =   buf.substring(0,   buf.length()-1);  
  }  
   
  //trun   back   to   the   original   value  
  result[celidx/9][celidx%9]   =   "?";  
   
  }  
  }  
   
  return   true;  
  }  
   
  private   void   print()   {  
  int   i,   j;  
  System.out.println("---------------result   "   +   count   +   "---------------");  
  for   (i=0;   i<9;   i++)   {  
  for   (j=0;   j<8;   j++)   {  
  System.out.print(result[i][j]+"   -   ");  
  }  
  System.out.println(result[i][j]);  
  }  
  }  
  }  
  Top

19 楼qybao(阿宝)回复于 2006-03-17 13:37:43 得分 0

以下是20分钟跑出的结果  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   1   -   6   -   4   -   5   -   3  
  2   -   3   -   8   -   7   -   5   -   4   -   9   -   6   -   1  
  7   -   1   -   6   -   5   -   2   -   3   -   8   -   9   -   4  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   5   -   4   -   6   -   3   -   9   -   7   -   1   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   1   -   6   -   4   -   5   -   3  
  2   -   5   -   8   -   7   -   3   -   4   -   9   -   6   -   1  
  7   -   1   -   4   -   6   -   5   -   3   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   6   -   5   -   2   -   9   -   7   -   1   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   1   -   6   -   4   -   5   -   3  
  2   -   5   -   8   -   7   -   3   -   4   -   9   -   6   -   1  
  7   -   1   -   6   -   5   -   2   -   3   -   8   -   9   -   4  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   6   -   5   -   9   -   7   -   1   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   3   -   6   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   3   -   9   -   6   -   4  
  7   -   1   -   6   -   5   -   2   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   6   -   5   -   9   -   7   -   1   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   3   -   6   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   4   -   9   -   6   -   3  
  7   -   1   -   4   -   6   -   5   -   3   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   6   -   5   -   2   -   9   -   7   -   1   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   3   -   6   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   4   -   9   -   6   -   3  
  7   -   1   -   6   -   5   -   2   -   3   -   8   -   9   -   4  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   6   -   5   -   9   -   7   -   1   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   5   -   3   -   4   -   6   -   1  
  2   -   3   -   8   -   7   -   1   -   6   -   9   -   5   -   4  
  7   -   1   -   6   -   5   -   2   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   5   -   4   -   6   -   3   -   9   -   7   -   1   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   5   -   3   -   4   -   6   -   1  
  2   -   3   -   8   -   7   -   1   -   6   -   9   -   5   -   4  
  7   -   1   -   6   -   5   -   3   -   4   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   5   -   4   -   6   -   2   -   9   -   7   -   1   -   3  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   5   -   3   -   4   -   6   -   1  
  2   -   5   -   8   -   7   -   3   -   6   -   9   -   1   -   4  
  7   -   1   -   6   -   5   -   2   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   6   -   1   -   9   -   7   -   5   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   5   -   6   -   4   -   1   -   3  
  2   -   5   -   8   -   7   -   1   -   3   -   9   -   6   -   4  
  7   -   1   -   6   -   5   -   3   -   4   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   6   -   2   -   9   -   7   -   5   -   1  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   5   -   6   -   4   -   1   -   3  
  2   -   5   -   8   -   7   -   3   -   4   -   9   -   6   -   1  
  7   -   1   -   6   -   5   -   2   -   3   -   8   -   9   -   4  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   6   -   1   -   9   -   7   -   5   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   6   -   8   -   1   -   3   -   4   -   5   -   2  
  2   -   3   -   8   -   7   -   5   -   4   -   9   -   6   -   1  
  7   -   1   -   2   -   5   -   3   -   6   -   8   -   9   -   4  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   5   -   4   -   6   -   2   -   9   -   7   -   1   -   3  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   6   -   8   -   1   -   3   -   4   -   5   -   2  
  2   -   3   -   8   -   7   -   5   -   4   -   9   -   6   -   1  
  7   -   1   -   4   -   5   -   2   -   6   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   5   -   2   -   6   -   3   -   9   -   7   -   1   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   6   -   8   -   1   -   3   -   4   -   5   -   2  
  2   -   5   -   8   -   7   -   3   -   4   -   9   -   6   -   1  
  7   -   1   -   4   -   5   -   2   -   6   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   2   -   6   -   5   -   9   -   7   -   1   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   6   -   8   -   1   -   3   -   4   -   5   -   2  
  2   -   5   -   8   -   7   -   3   -   6   -   9   -   1   -   4  
  7   -   1   -   2   -   6   -   5   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   5   -   2   -   9   -   7   -   6   -   1  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   6   -   8   -   2   -   3   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   4   -   9   -   6   -   3  
  7   -   1   -   2   -   5   -   3   -   6   -   8   -   9   -   4  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   6   -   5   -   9   -   7   -   1   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   6   -   8   -   2   -   3   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   4   -   9   -   6   -   3  
  7   -   1   -   4   -   5   -   3   -   6   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   2   -   6   -   5   -   9   -   7   -   1   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   6   -   8   -   2   -   3   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   3   -   6   -   9   -   1   -   4  
  7   -   1   -   2   -   6   -   5   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   5   -   1   -   9   -   7   -   6   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   6   -   8   -   5   -   3   -   4   -   1   -   2  
  2   -   5   -   8   -   7   -   1   -   4   -   9   -   6   -   3  
  7   -   1   -   2   -   5   -   3   -   6   -   8   -   9   -   4  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   6   -   2   -   9   -   7   -   5   -   1  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   6   -   8   -   5   -   3   -   4   -   1   -   2  
  2   -   5   -   8   -   7   -   3   -   4   -   9   -   6   -   1  
  7   -   1   -   4   -   5   -   2   -   6   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   2   -   6   -   1   -   9   -   7   -   5   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  8   -   4   -   5   -   1   -   9   -   6   -   2   -   3   -   7  
  9   -   7   -   6   -   8   -   1   -   3   -   4   -   5   -   2  
  2   -   5   -   4   -   7   -   3   -   8   -   9   -   6   -   1  
  7   -   1   -   2   -   6   -   5   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  6   -   3   -   8   -   5   -   2   -   9   -   7   -   1   -   4  
  Top

20 楼qybao(阿宝)回复于 2006-03-17 13:38:37 得分 0

---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  8   -   4   -   5   -   6   -   9   -   3   -   2   -   1   -   7  
  9   -   7   -   2   -   8   -   1   -   6   -   4   -   5   -   3  
  2   -   3   -   4   -   7   -   5   -   8   -   9   -   6   -   1  
  7   -   1   -   6   -   5   -   3   -   4   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  6   -   5   -   8   -   1   -   2   -   9   -   7   -   3   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  8   -   4   -   5   -   6   -   9   -   3   -   2   -   1   -   7  
  9   -   7   -   2   -   8   -   5   -   6   -   4   -   3   -   1  
  2   -   5   -   4   -   7   -   1   -   8   -   9   -   6   -   3  
  7   -   1   -   6   -   5   -   3   -   4   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  6   -   3   -   8   -   1   -   2   -   9   -   7   -   5   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  9   -   4   -   5   -   1   -   2   -   6   -   8   -   3   -   7  
  6   -   7   -   2   -   8   -   9   -   3   -   4   -   5   -   1  
  2   -   5   -   6   -   7   -   3   -   8   -   9   -   1   -   4  
  7   -   1   -   8   -   6   -   5   -   4   -   2   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   5   -   1   -   9   -   7   -   6   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  9   -   4   -   5   -   1   -   2   -   6   -   8   -   3   -   7  
  6   -   7   -   2   -   8   -   9   -   3   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   4   -   9   -   6   -   3  
  7   -   1   -   6   -   5   -   3   -   8   -   2   -   9   -   4  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   6   -   5   -   9   -   7   -   1   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  9   -   4   -   5   -   1   -   2   -   6   -   8   -   3   -   7  
  6   -   7   -   4   -   8   -   9   -   3   -   2   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   4   -   9   -   6   -   3  
  7   -   1   -   6   -   5   -   3   -   8   -   4   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   2   -   6   -   5   -   9   -   7   -   1   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  9   -   4   -   5   -   1   -   3   -   8   -   2   -   6   -   7  
  6   -   7   -   2   -   8   -   9   -   3   -   4   -   5   -   1  
  2   -   3   -   8   -   7   -   5   -   6   -   9   -   1   -   4  
  7   -   1   -   6   -   5   -   2   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   5   -   4   -   6   -   1   -   9   -   7   -   3   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  9   -   4   -   5   -   1   -   3   -   8   -   2   -   6   -   7  
  6   -   7   -   2   -   8   -   9   -   3   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   6   -   9   -   3   -   4  
  7   -   1   -   6   -   5   -   2   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   6   -   5   -   9   -   7   -   1   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  9   -   4   -   5   -   6   -   1   -   8   -   2   -   3   -   7  
  6   -   7   -   2   -   8   -   9   -   3   -   4   -   5   -   1  
  2   -   3   -   8   -   7   -   5   -   6   -   9   -   1   -   4  
  7   -   1   -   6   -   5   -   2   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   5   -   4   -   1   -   3   -   9   -   7   -   6   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  9   -   4   -   5   -   6   -   1   -   8   -   2   -   3   -   7  
  6   -   7   -   2   -   8   -   9   -   3   -   4   -   5   -   1  
  2   -   3   -   8   -   7   -   5   -   6   -   9   -   1   -   4  
  7   -   1   -   6   -   5   -   3   -   4   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   5   -   4   -   1   -   2   -   9   -   7   -   6   -   3  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  9   -   4   -   5   -   6   -   1   -   8   -   2   -   3   -   7  
  6   -   7   -   2   -   8   -   9   -   3   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   3   -   6   -   9   -   1   -   4  
  7   -   1   -   6   -   5   -   2   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   1   -   5   -   9   -   7   -   6   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   2   -   6   -   7   -   3   -   4   -   9  
  9   -   4   -   5   -   6   -   3   -   8   -   2   -   1   -   7  
  6   -   7   -   2   -   8   -   9   -   3   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   6   -   9   -   3   -   4  
  7   -   1   -   6   -   5   -   2   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   1   -   5   -   9   -   7   -   6   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   6   -   2   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   1   -   6   -   4   -   5   -   3  
  2   -   3   -   8   -   7   -   5   -   4   -   9   -   6   -   1  
  7   -   1   -   4   -   5   -   6   -   3   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   5   -   6   -   2   -   3   -   9   -   7   -   1   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   6   -   2   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   1   -   6   -   4   -   5   -   3  
  2   -   5   -   8   -   7   -   3   -   4   -   9   -   6   -   1  
  7   -   1   -   4   -   5   -   6   -   3   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   6   -   2   -   5   -   9   -   7   -   1   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   6   -   2   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   1   -   6   -   4   -   5   -   3  
  2   -   5   -   8   -   7   -   3   -   4   -   9   -   6   -   1  
  7   -   1   -   6   -   2   -   5   -   3   -   8   -   9   -   4  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   5   -   6   -   9   -   7   -   1   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   6   -   2   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   1   -   6   -   4   -   5   -   3  
  2   -   5   -   8   -   7   -   6   -   3   -   9   -   1   -   4  
  7   -   1   -   6   -   5   -   3   -   4   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   2   -   5   -   9   -   7   -   6   -   1  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   6   -   2   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   3   -   6   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   3   -   9   -   6   -   4  
  7   -   1   -   6   -   2   -   5   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   5   -   6   -   9   -   7   -   1   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   6   -   2   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   3   -   6   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   4   -   9   -   6   -   3  
  7   -   1   -   4   -   5   -   6   -   3   -   8   -   9   -   2  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   6   -   2   -   5   -   9   -   7   -   1   -   4  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   6   -   2   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   3   -   6   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   1   -   4   -   9   -   6   -   3  
  7   -   1   -   6   -   2   -   5   -   3   -   8   -   9   -   4  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   5   -   6   -   9   -   7   -   1   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   6   -   2   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   3   -   6   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   6   -   3   -   9   -   1   -   4  
  7   -   1   -   6   -   2   -   5   -   4   -   8   -   9   -   3  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   5   -   1   -   9   -   7   -   6   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   -   8   -   1   -   5   -   2   -   6  
  5   -   8   -   1   -   6   -   2   -   7   -   3   -   4   -   9  
  6   -   4   -   5   -   1   -   9   -   8   -   2   -   3   -   7  
  9   -   7   -   2   -   8   -   3   -   6   -   4   -   5   -   1  
  2   -   5   -   8   -   7   -   6   -   4   -   9   -   1   -   3  
  7   -   1   -   6   -   2   -   5   -   3   -   8   -   9   -   4  
  4   -   6   -   9   -   3   -   7   -   2   -   1   -   8   -   5  
  8   -   3   -   4   -   5   -   1   -   9   -   7   -   6   -   2  
  ---------------result---------------  
  1   -   2   -   3   -   9   -   4   -   5   -   6   -   7   -   8  
  3   -   9   -   7   -   4   - &