最近喜欢上了数读游戏，所以想写一个数读游戏的算法，但后来在调试过程中发现，一些very hard级的游戏，解到后来需要试填数字，这就是我这个算法不完全的原因，不支持试填数字。试填数字可能就涉及到了回溯（因为不能保证所填的数字一定正确），我实在不想浪费太多的时间在这个算法上，所以暂时只能让他不完全下去，好在这个算法可以找到所有确定数字位置。
思路：采用位的方式，111111111（511，十进制），如果该空格内的数字不可能是123678，则对应的位应该为100011000。依次类推，把所有空格的可能性全都记录下来。然后按列，按行，按9个小方格判断，该空格得可能数字。不做过多解释了，喜欢数读游戏的人肯定知道怎么回事。
具体算法如下：（没有过多的解释说明，太懒了^_^）
using System;using System.Collections.Generic;using System.Text;using System.Xml;using System.IO;namespace sudoku{ public class soduku { public class NumArray { public int inum = 0; public int ifnum = 511; public bool bstate = false; }
public int Bit(int ibit) { return 1<<--ibit; } public int Num(int inum) { for (int j = 0; j < 9; j++) { if ((inum ^ (1 << j)) == 0) { return j; } } return 0; } private int iSum = 81; private NumArray[,] isoduku; public soduku(int [,] inumber) { isoduku = new NumArray[9, 9]; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { isoduku[i, j] = new NumArray(); if (inumber[i, j] != 0) { isoduku[i, j].inum = inumber[i, j]; isoduku[i, j].bstate = true; iSum--; isoduku[i, j].ifnum = -1; } } } ScanInit(); } public void ScanInit() { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (isoduku[i, j].bstate) { ScanRowCol(i, j); ScanArray(i, j); } } } }
//扫描行列，将不可能的数字去掉 public void ScanRowCol(int i,int j) { for (int k = 0; k < 9; k++) { if (!isoduku[i, k].bstate) { if((isoduku[i,k].ifnum & Bit(isoduku[i, j].inum)) != 0) isoduku[i, k].ifnum ^= Bit(isoduku[i, j].inum); } if (!isoduku[k, j].bstate) { if ((isoduku[k, j].ifnum & Bit(isoduku[i, j].inum)) != 0) isoduku[k, j].ifnum ^= Bit(isoduku[i, j].inum); } } }
//扫描小方格，将不可能的数字去掉 public void ScanArray(int i, int j) { for (int m = (i / 3) * 3; m <= (i / 3) * 3 + 2;m++ ) { for (int n = (j / 3) * 3; n <= (j / 3) * 3 + 2; n++) { if (!isoduku[m, n].bstate) { if ((isoduku[m, n].ifnum & Bit(isoduku[i, j].inum)) != 0) isoduku[m, n].ifnum ^= Bit(isoduku[i, j].inum); }
} } }
//最终的扫描函数 public bool SearchArray() { int iloop = 0; while (true) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (!isoduku[i, j].bstate) { if (SearchRowCol(i, j) != 0) continue; if (SearchArray(i, j) != 0) continue; } } } iloop++; if (iSum == 0) return true; else if (iloop > 10) return false; } return false; }
//搜索行列，确定符合条件的数字，同时去掉该行，该列的其他空格的可能是这个数字的可能性 public int SearchRowCol(int i,int j) { int icount = 0; int iset = 0; for (int k = 0; k < 9; k++) { for (int m = 0; m < 9; m++) { if (!isoduku[i, m].bstate) { if ((isoduku[i, m].ifnum & (1 << k)) == (1 << k)) { icount++; iset = m; } if ((isoduku[i, m].ifnum == (1 << k)) && !isoduku[i, m].bstate) { isoduku[i, m].inum = ++k; isoduku[i, m].bstate = true; ScanRowCol(i, m); ScanArray(i,m); iSum--; return k; }
} } if ((icount == 1) && !isoduku[i, iset].bstate) { isoduku[i, iset].inum = ++k; isoduku[i, iset].bstate = true; ScanRowCol(i, iset); ScanArray(i,iset); iSum--; return k;
} icount = 0; } for (int k = 0; k < 9; k++) { for (int m = 0; m < 9; m++) { if (!isoduku[m, j].bstate) { if ((isoduku[m, j].ifnum & (1 << k)) == (1 << k)) { icount++; iset = m; } if ((isoduku[m, j].ifnum == (1 << k)) && !isoduku[m, j].bstate) {
isoduku[m, j].inum = ++k; isoduku[m, j].bstate = true; ScanRowCol(m, j); ScanArray(m, j); iSum--; return k; }
} } if ((icount == 1) && !isoduku[iset, j].bstate) { isoduku[iset, j].inum = ++k; isoduku[iset, j].bstate = true; ScanRowCol(iset , j); ScanArray(iset, j); iSum--; return k;
} icount = 0; } return 0; }
//搜索小方块（3X3）,同上 public int SearchArray(int i,int j) { int icount = 0; int isetx = 0; int isety = 0; for (int k = 0; k < 9; k++) { for (int m = (i / 3) * 3; m <= (i / 3) * 3 + 2; m++) { for (int n = (j / 3) * 3; n <= (j / 3) * 3 + 2; n++) { if (!isoduku[m, n].bstate) { if ((isoduku[m, n].ifnum & (1 << k)) == (1 << k)) { icount++; isetx = m; isety = n; } if ((isoduku[m, n].ifnum == (1 << k)) && !isoduku[m,n].bstate) { isoduku[m, n].inum = ++k; isoduku[m, n].bstate = true; ScanRowCol(m, n); ScanArray(m, n); iSum--; return k; }
} } } if ((icount == 1) && !isoduku[isetx, isety].bstate) { isoduku[isetx, isety].inum = ++k; isoduku[isetx, isety].bstate = true; ScanRowCol(isetx, isety); ScanArray(isetx, isety); iSum--; return k; } icount = 0; } return 0; } public void Show() { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if(isoduku[i,j].ifnum == -1) System.Console.Write("{0,4}","["+isoduku[i,j].inum.ToString()+"]"); else System.Console.Write("{0,4}", isoduku[i, j].inum.ToString() + " "); } System.Console.Write("/r/n"); } } public void Show(string strpath) { //FileStream fs = new FileStream(strpath, FileAccess.Write); StreamWriter sw = File.AppendText(strpath); //sw = sw.WriteLine("------------------------------------"); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (isoduku[i, j].ifnum == -1) sw.Write("{0,4}", "[" + isoduku[i, j].inum.ToString() + "]"); else sw.Write("{0,4}", isoduku[i, j].inum.ToString() + " "); } sw.Write("/r/n"); } sw.Close(); } } class Program { static void Main(string[] args) { int[,] iarray = new int[9, 9]{ {2,3,0,6,0,0,0,9,0}, {0,0,0,0,0,0,0,4,0}, {0,5,0,9,0,1,0,0,0}, {7,0,0,0,2,0,0,0,3}, {1,0,0,3,0,5,0,0,9}, {3,0,0,0,6,0,0,0,5}, {0,0,0,2,0,4,0,1,0}, {0,2,0,0,0,0,0,0,0}, {0,1,0,0,0,6,0,7,8}};
int[,] iarray1 = new int[9, 9]{ {5,0,0,0,0,0,0,0,1}, {0,0,0,0,1,0,0,3,0}, {0,3,4,0,0,0,2,6,0},
{0,7,3,0,0,6,4,5,0}, {0,0,0,2,0,4,0,0,0}, {0,4,6,9,0,0,8,1,0},
{0,6,1,0,0,0,3,9,0}, {0,8,0,0,4,0,0,0,0}, {3,0,0,0,0,0,0,0,8}};
int[,] iarray2 = new int[9, 9]{ {0,1,0,9,0,4,0,8,0}, {0,0,0,0,3,0,0,0,0}, {0,0,3,2,0,5,6,0,0},
{7,0,2,0,0,0,5,0,8}, {5,3,0,0,0,0,0,6,9}, {8,0,9,0,0,0,1,0,7},
{0,0,7,5,0,8,4,0,0}, {0,0,0,0,9,0,0,0,0}, {0,2,0,7,0,3,0,9,0}}; int[,] iarray3 = new int[9, 9]{ {0,0,0,1,5,8,0,9,0}, {1,0,0,2,0,3,0,0,4}, {0,0,0,0,0,0,0,0,3},
{0,6,0,0,3,0,0,2,8}, {0,0,5,0,0,0,4,0,0}, {3,4,0,0,9,0,0,5,0},
{7,0,0,0,0,0,0,0,0}, {5,0,0,3,0,7,0,0,1}, {0,3,0,4,2,9,0,0,0}}; int[,] iarray4 = new int[9, 9]{ {4,8,0,0,0,0,0,0,3}, {0,0,0,0,7,0,0,4,6}, {0,0,6,4,0,3,0,0,0},
{0,0,0,0,0,7,1,3,0}, {6,0,0,5,0,9,0,0,8}, {0,1,8,3,0,0,0,0,0},
{0,0,0,9,0,1,3,0,0}, {7,9,0,0,5,0,0,0,0}, {2,0,0,0,0,0,0,8,9}}; int[,] iarray5 = new int[9, 9]{ {4,9,0,0,0,6,0,0,0}, {0,0,0,0,0,0,0,2,9}, {7,0,0,0,0,8,0,0,3},
{0,4,5,0,1,9,0,0,8}, {0,0,0,8,0,7,0,0,0}, {8,0,0,3,4,0,6,9,0},
{1,0,0,6,0,0,0,0,2}, {2,3,0,0,0,0,0,0,0}, {0,0,0,7,0,0,0,8,4}}; int[,] iarray6 = new int[9, 9]{ {0,0,0,0,0,1,0,9,0}, {2,0,7,0,0,0,4,0,0}, {0,4,0,0,2,0,0,1,0},
{0,0,0,2,0,3,0,0,7}, {0,0,2,0,6,0,5,0,0}, {8,0,0,1,0,7,0,0,0},
{0,7,0,0,3,0,0,4,0}, {0,0,5,0,0,0,8,0,3}, {0,6,0,5,0,0,0,0,0}}; sudoku.soduku isoduku = new soduku(iarray5); isoduku.SearchArray(); isoduku.Show();/* XmlDocument xdoc = new XmlDocument(); xdoc.Load(@"./sudoku.xml"); int[,] sudokuarray = new int[9, 9]; XmlNodeList xnodelist = xdoc.SelectNodes(@"/sudoku/item"); foreach (XmlNode xnode in xnodelist) { XmlNodeList xlist = xnode.ChildNodes; int i = 0; foreach (XmlElement xele in xlist) { string str = xele.InnerText; for (int j = 0; j < 9; j++) { sudokuarray[i, j] = int.Parse(str[j].ToString()); } i++; } sudoku.soduku isoduku = new soduku(sudokuarray); isoduku.SearchArray(); isoduku.Show(@"./result.txt"); }*/
} }}
