九宫阵

看到了这个游戏，玩了几期，感觉不错

游戏简介：
智力游戏“九宫阵”，它是一个9×9的方阵，由9个“九宫格”（下图中粗黑色实线围住的3×3个小方阵）构成，每个九宫格又由3×3共9个小格子构成。请在图中每个空白小格子里面填上1～9的数字，使每个数字在每个九宫格内以及在整个“九宫阵”中每行、每列上均只出现一次。

网上有一个用c写的免费版本，没仔细去用，不过看起来功能很强，可自动出题，自动解题，给予提示等等。自动出题这个功能我还不知道应该怎么做，学识浅薄啊:(

我用java写了个程序去解

用java代码来解决此问题，具体是以Web方式实现的
算法是采用排除法，而不是穷举法
原始数据中未知的数据用0表示，每一行数据两两之间可以不用分隔符分开，或者可用除了0～9之外的任意分隔符分开，注意分隔符必须统一
npl.jsp中有一些原始数据的示例

com.hxm.NPL.java
[code]
/**
* Created on 2006-3-5
* 转载请注明出处：http://lastwinner.itpub.net
*/
package com.hxm;

import java.util.StringTokenizer;
import java.util.Vector;
import javax.servlet.http.*;

/**
* @author SOFTADMIN
*/
public class NPL
{
/**
* 以下变量，i相当于纵坐标(即行索引)，j相当于横坐标(即列索引)
*/

//源九宫阵
String sNPLSrc = "";

//store guess data
Vector[][] vNPL = new Vector[9][9];

String m_sResult = "";
String m_sFinalResult = "";
/**
* Constructor for NinePalaceLineup.
*/
public NPL()
{
super();
}
/**
* ConvertNull：将null转换为空字符串
* @param s String
* @return String
*/
public static String ConvertNull(String s)
{
return (s == null) ? "" : s;
}

/**
* 将一个用sDelim分隔的字符串s转换为数组
*
* @param sDelimStr 用sDelim分隔的字符串
* @param sDelim 分隔符
* @return String 二维String数组
*/
public static String[] convertDelimStr2Str(String sDelimStr, String sDelim)
{
Vector v = new Vector();
StringTokenizer st = new StringTokenizer(ConvertNull(sDelimStr),sDelim);
while(st.hasMoreTokens())
{
v.addElement(st.nextToken());
}
return (String[])v.toArray(new String[]{});
}

public void calculateResult(HttpServletRequest req)
{
sNPLSrc = ConvertNull(req.getParameter("Question"));
if(!sNPLSrc.equals(""))
{
initNPLdata(sNPLSrc);
deleteAllDupliData();

boolean bHasNew = false;
int iLoops = 1;
do
{
printAllDataHTML();
System.out.println("----======开始第 " + iLoops + " 轮循环=======-------");
//find unique value
Vector vUniVal = new Vector();
bHasNew = false;
for (int type = 0; type < 3; type++)
{
System.out.println("----======Now Processing " + type + ", Loops:" + iLoops + "=======-------");
vUniVal.clear();
for (int i = 0; i < 9; i++)
{
vUniVal = getUniqueValues(i, type);
System.out.println("type: " + type + ", idx: " + i + " 唯一值数量:" + vUniVal.size() + " ");
if(vUniVal.size()>0)
{
bHasNew = true;
System.out.print("分别是: ");
printVector(vUniVal);
System.out.println();
setNewDeterminedValue(i, type, vUniVal);
}
chkNPLValid(i, type);
}
chkVNPL();
printDeterminedData();
System.out.println("----======Now Ending " + type + ", Loops:" + iLoops + "=======-------");
printAllDataHTML();
m_sResult += "第 " + iLoops + " 轮循环，" + getTypeName(type) + "rn";
m_sResult += getDeterminedDataFromVector();
}
System.out.println("======--------第 " + iLoops + " 轮循环结束--------------=======");
iLoops ++;
} while(bHasNew && iLoops<10);

System.out.println("-----===final data===-----");
printDeterminedData();
m_sFinalResult = getDeterminedDataFromVector();
}
}

/**
* @param i
* @param j
* @return int 获得方阵代码，从左往右从上往下为0～8
*/
public int getPhalanxBelongedTo(int i, int j)
{
return (i/3)*3+(j/3);
}

/**
* 删除多余数据
* 将vNPL(i,j)中和vExists有重复的数字删除
*
* @param i
* @param j
*/
public void deleteDupliData(int i, int j, Vector vExists)
{
for (int k = 0; k < vExists.size(); k++)
{
vNPL[i][j].remove(vExists.get(k));
}
//如果重复数据删除完成后，只剩下一个数字A，那么还要从与此单元格相关联的单元格中（同一方阵同一横线同一竖线）
//删除这个数字A
if(vNPL[i][j].size()==1) deleteSpecialDataFromRelatedCells(i, j);
}

/**
* 从与指定单元格相关联的单元格中（同一方阵同一横线同一竖线）
* 删除指定单元格中已确定的数据
*
* @param i
* @param j
*/
public void deleteSpecialDataFromRelatedCells(int i, int j)
{
if(vNPL[i][j].size()==1)
{
Object o = vNPL[i][j].get(0);
boolean bTmp = false;
for (int k = 0; k < 9; k++)
{
if(k!=i)
{
bTmp = vNPL[k][j].remove(o);
//如果重复数据删除完成后，只剩下一个数字...
if(bTmp && vNPL[k][j].size()==1) deleteSpecialDataFromRelatedCells(k, j);
}
if(k!=j)
{
bTmp = vNPL[i][k].remove(o);
if(bTmp && vNPL[i][k].size()==1) deleteSpecialDataFromRelatedCells(i, k);
}
}

int idxPhalanx = getPhalanxBelongedTo(i, j);
for (int l = idxPhalanx%3*3; l < (idxPhalanx%3*3+3); l++)
{
for (int k = idxPhalanx/3*3; k < idxPhalanx/3*3+3; k++)
{
if(k!=i && l!=j)
{
bTmp = vNPL[k][l].remove(o);
if(bTmp && vNPL[k][l].size()==1) deleteSpecialDataFromRelatedCells(k, l);
}
}
}
}
else
{
System.out.println("Err.....This vNPL has more than one elements.");
}
}

/**
* 获得与当前单元格在同一横线同一竖线同一方阵的所有已确定的数字
* 不包括当前单元格的数字，重复数字只存储一次
* 当前单元格数字若已确定，则返回大小为0的Vector对象
*
* @param i
* @param j
* @return Vector
*/
public Vector getExistsData(int i, int j)
{
Vector v = new Vector();
if(vNPL[i][j].size()!=1)
{
for (int k = 0; k < 9; k++)
{
if(k!=i)
{
if(vNPL[k][j].size()==1 && v.indexOf(vNPL[k][j].get(0))==-1)
{
v.addElement(vNPL[k][j].get(0));
}
}
if(k!=j)
{
if(vNPL[i][k].size()==1 && v.indexOf(vNPL[i][k].get(0))==-1)
{
v.addElement(vNPL[i][k].get(0));
}
}
}

int idxPhalanx = getPhalanxBelongedTo(i, j);
for (int l = idxPhalanx%3*3; l < (idxPhalanx%3*3+3); l++)
{
for (int k = idxPhalanx/3*3; k < idxPhalanx/3*3+3; k++)
{
if(k!=i && l!=j && vNPL[k][l].size()==1 && v.indexOf(vNPL[k][l].get(0))==-1)
{
v.addElement(vNPL[k][l].get(0));
}
}
}
}
return v;
}

/**
* 获得一个方阵／横线／竖线中只有一个单元格包含的值
*
* @param idx 横线竖线方阵的索引
* @param type 查找类型，0－方阵，1－横线，2－竖线
* @return Vector
*/
public Vector getUniqueValues(int idx, int type)
{
Vector v = new Vector();
int[] iUniVal = new int[10];
switch(type)
{
case 0:
for (int l = idx%3*3; l < (idx%3*3+3); l++)
{
for (int k = idx/3*3; k < idx/3*3+3; k++)
{
if(vNPL[k][l].size()!=1)
{
for (int i = 0; i < vNPL[k][l].size(); i++)
{
iUniVal[Integer.parseInt((String)vNPL[k][l].get(i))]++;
}
}
}
}
break;
case 1:
for (int l = 0; l < 9; l++)
{
if(vNPL[idx][l].size()!=1)
{
for (int i = 0; i < vNPL[idx][l].size(); i++)
{
iUniVal[Integer.parseInt((String)vNPL[idx][l].get(i))]++;
}
}
}
break;
case 2:
for (int l = 0; l < 9; l++)
{
if(vNPL[l][idx].size()!=1)
{
for (int i = 0; i < vNPL[l][idx].size(); i++)
{
iUniVal[Integer.parseInt((String)vNPL[l][idx].get(i))]++;
}
}
}
break;
}
//System.out.println("type: " + type + ", idx: " + idx);
for (int i = 0; i < iUniVal.length; i++)
{
//System.out.println("i: " + i + "iUniVal[" + i + "]=" + iUniVal[i]);
if(iUniVal[i]==1) v.addElement(String.valueOf(i));
}
return v;
}

/**
* 设置新确定的值
*
* @param idx 方阵／横线／竖线索引
* @param type 类型,0－方阵，1－横线，2－竖线
* @param vUniVal 唯一值
*/
public void setNewDeterminedValue(int idx, int type, Vector vUniVal)
{
int ls=0, le=-1;
int ks=0, ke=-1;
switch(type)
{
case 0:
ls=idx%3*3;
le=(idx%3*3+3);
ks=idx/3*3;
ke=idx/3*3+3;
break;
case 1:
ls=0;
le=9;
ks=idx;
ke=idx+1;
break;
case 2:
ls=idx;
le=idx+1;
ks=0;
ke=9;
break;
}

boolean bNeedRecycle = false;
do
{
for (int l = ls; l < le; l++)
{
for (int k = ks; k < ke; k++)
{
if(vNPL[k][l].size()>1)
{
for (int i = 0; i < vUniVal.size(); i++)
{
if(vNPL[k][l].indexOf(vUniVal.get(i))!=-1)
{
setNewValue(k, l, vUniVal, i);
//printAllDataHTML();
continue;
}
}
}
}
}
}while(bNeedRecycle && false);
}

/**
* @param k 行索引，即纵坐标
* @param l 列索引，即横坐标
* @param vUniVal 包含唯一值的Vector对象
*/
public void setNewValue(int k, int l, Vector vUniVal, int i)
{
Vector v = new Vector();
int iDebug=0;
vNPL[k][l].clear();
vNPL[k][l].addElement(vUniVal.get(i));
if(iDebug==0)
{
deleteSpecialDataFromRelatedCells(k,l);
}
else if(iDebug==1)
{
v=getExistsData(k, l);
deleteDupliData(k, l, v);
}
vUniVal.remove(i);
}

/**
* 打印已确定的数据
*/
public void printDeterminedData()
{
System.out.println(getDeterminedDataFromVector());
}

/**
* @return String
*/
public String getDeterminedDataFromVector()
{
String sRlt="";
sRlt += "rn";
sRlt +=">>>>>>>>>>>Data from Vector<<<<<<<<<<n";
for (int i = 0; i < vNPL.length; i++)
{
for (int j = 0; j < vNPL[i].length; j++)
{
sRlt += (vNPL[i][j].size()==1 ? vNPL[i][j].get(0) : "0") + " ";
}
sRlt += "rn";
}
return sRlt;
}

/**
* 打印所有数据（包括猜测数据）的html代码
*/
public void printAllDataHTML()
{
StringBuffer sb = new StringBuffer("n");
sb.append("<table border=1>");
for (int i = 0; i < vNPL.length; i++)
{
sb.append("<tr>");
for (int j = 0; j < vNPL[i].length; j++)
{
sb.append("<td>");
for (int k = 0; k < vNPL[i][j].size(); k++)
{
sb.append(vNPL[i][j].get(k));
}
sb.append("</td>");
}
sb.append("</tr>n");
}
sb.append("</table>n");
System.out.println(sb.toString());
}

/**
* 初始化九宫阵数据
*
* @param sNPLSrc 九宫阵源字符串
*/
public void initNPLdata(String sNPLSrc)
{
//split string
String[] sNPLList = convertDelimStr2Str(sNPLSrc, "nr");

//init NPL data
char chTmp = sNPLList[0].charAt(1);
//store init data
String[][] sNPL = new String[9][9];

if(chTmp >= '0' && chTmp <= '9')
{
for (int i = 0; i < sNPLList.length; i++)
{
for (int j = 0; j < sNPLList[i].length(); j++)
{
sNPL[i][j] = sNPLList[i].substring(j,j+1);
//Trace.print("i:"+i+" j:"+j+" "+sNPL[i][j]);
}
}
}
else
{
for (int i = 0; i < sNPLList.length; i++)
{
sNPL[i] = convertDelimStr2Str(sNPLList[i], String.valueOf(chTmp));
}
}

//init guess data
for (int i = 0; i < vNPL.length; i++)
{
for (int j = 0; j < vNPL[i].length; j++)
{
vNPL[i][j] = new Vector();
if(!sNPL[i][j].equals("0"))
{
//known data
vNPL[i][j].addElement(sNPL[i][j]);
}
else
{
//guess data
for (int k = 0; k < 9; k++)
{
vNPL[i][j].addElement(String.valueOf(k+1));
}
}
}
}
}

public void deleteAllDupliData()
{
//delete duplicate data
for (int i = 0; i < vNPL.length; i++)
{
for (int j = 0; j < vNPL[i].length; j++)
{
Vector v = getExistsData(i, j);
//序号
String sTmp = String.valueOf(i*9+j+1);
System.out.print((sTmp.length()==1 ? "0" :"") + sTmp+": ");

printVector(v);
for (int k = 0; k < 9-v.size(); k++)
{
System.out.print("-");
}

deleteDupliData(i, j, v);

printVector(vNPL[i][j]);
for (int k = 0; k < 9 - vNPL[i][j].size(); k++)
{
System.out.print("-");
}
System.out.print(vNPL[i][j].size()!=1 ? " " : vNPL[i][j].get(0));
System.out.print(vNPL[i][j].size()==0 ? "~BAD~" :"");

System.out.println();
}
}
return;
}

public void chkVNPL()
{
for (int i = 0; i < vNPL.length; i++)
{
for (int j = 0; j < vNPL[i].length; j++)
{
if(vNPL[i][j].size()==0)
{
System.out.println("Error... VNPL is Empty, i=" + i + ", j=" +j);
}
}
}
return;
}

/**
* @param idx 方阵／横线／竖线索引
* @param type 类型,0－方阵，1－横线，2－竖线
*/
public void chkNPLValid(int idx, int type)
{
int[] iUniVal = new int[10];
switch(type)
{
case 0:
for (int l = idx%3*3; l < (idx%3*3+3); l++)
{
for (int k = idx/3*3; k < idx/3*3+3; k++)
{
if(vNPL[k][l].size()==1)
iUniVal[Integer.parseInt((String)vNPL[k][l].get(0))]++;
}
}
break;
case 1:
for (int l = 0; l < 9; l++)
{
if(vNPL[idx][l].size()==1)
iUniVal[Integer.parseInt((String)vNPL[idx][l].get(0))]++;
}
break;
case 2:
for (int l = 0; l < 9; l++)
{
if(vNPL[l][idx].size()==1)
iUniVal[Integer.parseInt((String)vNPL[l][idx].get(0))]++;
}
break;
}
for (int i = 1; i < iUniVal.length; i++)
{
if(iUniVal[i]>1)
{
System.out.println("Error occurs while checking NPL, idx=" + idx + ", type=" +type
+ ", Number=" +i + ", count=" + iUniVal[i]);
}
}
}

/**
* Returns the result.
* @return String
*/
public String getResult()
{
return m_sResult;
}

/**
* Returns the finalResult.
* @return String
*/
public String getFinalResult()
{
return m_sFinalResult;
}

/**
* @return String
*/
public String getTypeName(int type)
{
return (type==0 ? "方阵" : (type==1 ? "行" : "列"));
}

/**
* Returns the sNPLSrc.
* @return String
*/
public String getNPLSrc()
{
return sNPLSrc;
}

/**
* @param v
*/
public void printVector(Vector v)
{
for (int i = 0; i < v.size(); i++)
{
System.out.print(v.get(i));
}
}

}

[/code]

npl.jsp
[code]
<%@ page language="java" contentType="text/html; charset=GBK" pageEncoding="GBK"%>
<jsp:useBean id="NPL" scope="page" class="com.hxm.NPL"/>
<HTML>
<BODY>
<%
boolean b = NPL.ConvertNull(request.getParameter("Question")).length()>0;
if(b)
try
{
NPL.calculateResult(request);
}catch (Throwable e){
out.print(e.getMessage());
e.printStackTrace();
}%>
<FORM action="<%=request.getRequestURI()%>" method=post><TEXTAREA rows="13" cols="20" name="Question"><%if(b){%><%=NPL.getNPLSrc()%><%}else{%>0 0 6 8 0 0 0 0 9
0 9 0 0 6 0 0 4 0
0 8 2 0 0 5 1 0 0
0 5 0 0 4 2 0 0 7
0 0 4 5 3 0 0 0 0
9 0 0 0 0 0 0 2 0
0 0 8 0 5 0 3 0 2
0 4 0 0 0 0 0 7 1
7 0 0 9 0 0 0 0 0<%}%></TEXTAREA><INPUT type="submit" value="计算">
最终结果：<TEXTAREA rows="13" cols="40" name="answer"><%=b ? NPL.getFinalResult() : ""%></TEXTAREA>
<BR>
中间计算过程：
<TEXTAREA rows="24" cols="50" name="scratch"><%=b ? NPL.getResult() : ""%></TEXTAREA>
<TEXTAREA rows="9" cols="20" name="Question2" style="display:none" disabled>380040050
205600008
019000000
000300820
860090040
007002000
000107090
603800001
020000600
-------------
0 0 6 8 0 0 0 0 9
0 9 0 0 6 0 0 4 0
0 8 2 0 0 5 1 0 0
0 5 0 0 4 2 0 0 7
0 0 4 5 3 0 0 0 0
9 0 0 0 0 0 0 2 0
0 0 8 0 5 0 3 0 2
0 4 0 0 0 0 0 7 1
7 0 0 9 0 0 0 0 0
--------------
000140700
000006023
000070009
094008500
601000040
003700000
069007300
540200000
020000060</TEXTAREA>

</FORM>
</BODY>
</HTML>

[/code]

代码中注释不是很多，了解了题目解法之后再来看算法就会很清晰了

这个游戏叫“数独”(sudoku)，现在挺流行的。你可以去网上多找一些题目，来试试你的这个算法是否能够处理所有的局。

嗯，谢谢大虾指导
网上的题目我试过很多，都没有问题了我才敢放出来的
不过程序还有可完善的地方，比如检验是否已经得到了结果，校验最终结果是否正确等，懒得做了:P

很高兴看到您是做JAVA的。
我从事人力资源咨询行业，现在受一家美资公司所托，招IT方面人才。目前较急的事j2ee方向的架构工程师。期待您能与我联系：
13810935417，zhang.jing.jing@hotmail.com
如果您能帮忙问问身边的朋友，我将不慎感激！！

第一次看到java原来是这样

介绍一下你用的算法啊

算法见帖子开头：排除法
1、已确定数字的位置直接填该数字，未确定数字的位置可能取值为1～9
2、根据规则将未知格子中的不可能存在的数字除去
3、如果某格子只剩下一个可能数字，则该数字就是此格子的值，并转2；若还剩下多个数字，则转4
4、找出同一行／列／方阵中还有哪些数字未确定，并查找这样的格子，它包含一个其他未确定格子中没有的数字A。如果数字A存在，则A为该格子的值
5、转2，直至每个格子中的数字都已确定

排除法不能解决所有的九宫阵，网上还介绍了模糊分析法，你可以查到解题思路

这个问题我已经发现了
谢谢fish（fishlyi？）

这只程序能跑吗,我想跑出来TRY TRY!!

回贝佳
可以跑,不过一些难度大的没法得到完全的解

太简单了吧……

Ray兄指的是哪里简单？

是数独游戏,LZ能自己做出来还是要点功夫的

谢谢
有空我再加上揣测功能，应该就能解更多的甚至所有的局了

o为什么我运行时,得到的是NULL呢~~~
可以给我发一个做好了的我研究下吗?发我邮箱.谢谢了

嗯，得到null的话，先检查一下你输入的数据是否正确吧^_^
程序就是上面那些内容呀
请留下你的邮箱，我给你发，呵呵

好像很oo嘛
可惜太长了把

嗯，程序是长了点
不过还不够完善，呵呵

使用的是第几代java啊，我那是4.0有错误。

E:>javac NPL.java
NPL.java:9: package javax.servlet.http does not exist
import javax.servlet.http.*;

NPL.java:63: cannot resolve symbol
symbol : class HttpServletRequest
location: class com.hxm.NPL
public void calculateResult(HttpServletRequest req)
^
2 errors 就这两个错误

HttpServletRequest
yy你需要导入这个类才可以编译通过

我好像用的树形穷举法 感觉速度还是还是很快的嘛

我计算机编程不通，数学也不好，在桌子上排除法试用了半天，还是没见到庐山真面目，哎...脖子那叫一个酸~
急盼大家能推荐一个我这样愚钝的人可以用的方法，感激之情，溢于言表！

to 回眸那一瞬：排除法其实也不赖的，呵呵
有专门的数独网站提供一些方法可供你参考
上网一搜 数独，就会出来了