[转]数独的核心算法

时间:04/30/2014 14:13:59   作者:ChenReal    阅读:385

先收藏,有空自己再弄个小游戏来玩玩~~

=============================

package tiger;

import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;

import javax.swing.JPanel;

/**
 * 
 * @author tiger
 * 
 * 应该注意数组的横纵坐标和界面的行列之间的对应关系
 *
 */
@SuppressWarnings("serial")
public class GamePanel extends JPanel implements MouseListener{

 /** 屏幕的宽和高 */
 private int width,height;
 /** 方格的宽和高 */
 private int blockW = 40, blockH = 40;
 /** 方格区左上角坐标 */
 private int startX,startY;
 /** 数独数组 */
 private sodu sodu ;
 private int[][] array ;
 /** 标记方格是否可修改 */
 private boolean[][] flag ;

 /** 所选数字 */
 private int number;

 // 选项区左上角坐标
 private int nx ;
 private int ny ;

 private boolean isWin = false;
 private boolean isNoPress = true;

 /**
 * 构造方法
 */
 public GamePanel(int width, int height) {
 this.width = width;
 this.height = height;
// this.startX = (width - blockW * 9) / 2;
// this.startY = (width - blockH * 9) / 2;
 this.startX = 30;
 this.startY = 30;
 this.nx = (width - blockW * 10) / 2;
 this.ny = 425;

 this.setFocusable(true);
 this.setSize(width, height);
 this.addMouseListener(this);

 this.sodu = new sodu();
 this.array = sodu.getArray();
 this.initFlag();
 }

 /**
 * 初始化flag
 */
 private void initFlag()
 {
 flag = new boolean[array.length][array[0].length];
 for (int i = 0; i < array.length; i++) {
 for (int j = 0; j < array[i].length; j++) {
 if(array[i][j] == 0)
 {
 flag[i][j] = true;
 }else{
 flag[i][j] = false;
 }
 }
 }
 }


 /**
 * 画出页面
 */
 private void draw(Graphics g) {

 //画背景
 g.setColor(new Color(0x839156));
 g.fillRect(0, 0, width, height);

 //如果胜利,画出提示
 if(isWin){
 g.setColor(Color.blue);
 g.drawString("太棒了!已完成!要再来一盘吗?点我!", 35, 20);
 }

 //刚打开游戏显示的字符串。
 if(isNoPress == true){
 g.setColor(Color.black);
 g.fillRect(15, 395, 400, 25);
 g.setColor(Color.green);
 g.drawString("because you looks beautiful like tiger, so you can play this game. let's go!", 16, 410);
 }


 //画方格
// g.setColor(Color.lightGray);
 g.setColor(new Color(0x696B63));
 for (int i = 0; i < 10; i++) {
 g.drawLine(startX + i * blockW, startY, startX + i * blockW, startY + 9 * blockH);
 g.drawLine(startX, startY + i * blockH, startX + 9 * blockW, startY + i * blockH);
 }

 //画小矩阵间的分割线
 g.setColor(Color.black);
 g.drawLine(startX + 0 * blockW, startY, startX + 0 * blockW, startY + 9 * blockH);
 g.drawLine(startX + 3 * blockW, startY, startX + 3 * blockW, startY + 9 * blockH);
 g.drawLine(startX + 6 * blockW, startY, startX + 6 * blockW, startY + 9 * blockH);
 g.drawLine(startX + 9 * blockW, startY, startX + 9 * blockW, startY + 9 * blockH);

 g.drawLine(startX, startY + 0 * blockH, startX + 9 * blockW, startY + 0 * blockH);
 g.drawLine(startX, startY + 3 * blockH, startX + 9 * blockW, startY + 3 * blockH);
 g.drawLine(startX, startY + 6 * blockH, startX + 9 * blockW, startY + 6 * blockH);
 g.drawLine(startX, startY + 9 * blockH, startX + 9 * blockW, startY + 9 * blockH);

 //画方格中的数字
 g.setFont(new Font("", 7, 26));
 for (int i = 0; i < 9; i++) {
 for (int j = 0; j < 9; j++) {
 if(array.length > i && array[i].length > j && array[i][j] != 0)
 {
 //与当前选中数字相同,画标记
 if(array[i][j] == number){
 g.setColor(new Color(0x317C1E));
 g.fillRect(startX + j * blockW + 2, startY + i * blockH + 2, blockW - 3, blockH - 3);
 }
 //画出数字
 g.setColor(new Color(0x070707));
 g.drawString(array[i][j] + "", startX + j * blockW + blockW / 2 - 6, startY + i * blockH + blockH / 2 + 8);
 }
 //是组成数独题目的元素,画不可编辑标记
 if(flag[i][j] == false) 
 {
 g.setColor(new Color(0x696B63));
 g.drawLine(startX + j * blockW + 3, startY + i * blockH + 3, startX + j * blockW + 5, startY + i * blockH + 3); // 画标记
 } 
 }
 }


 //画选项数字
 for (int i = 0; i <= 9; i++) {
 g.setColor(Color.black);
 g.drawRect(nx + i * blockW, ny, blockW, blockH);
 if(i == number)
 {
 g.setColor(new Color(0x317C1E));
 g.fillRect(nx + i * blockW + 2, ny + 2, blockW - 3, blockH - 3);
 }
 g.setColor(Color.black);
 g.drawString(i + "", nx + i * blockW + blockW / 2 - 6 , ny + blockH / 2 + 8);
 }

 }

 /**
 * 覆盖paintComponent()方法
 */
 public void paintComponent(Graphics g) {
 super.paintComponent(g);
 this.draw(g);
 }

 /**
 * 判断数组a的元素是否是1到9
 * @return
 */
 private boolean isYesArray(int[] a)
 {
 if(a.length > 9)
 {
 return false;
 }
 int flag = 0x3fe;
 for (int i = 0; i < a.length; i++) {
 int abc = 0;
 abc = flag & (1 << a[i]);
 flag = flag - abc;
 if(abc == 0)return false;
 }
 return true;
 }


 /**
 * 判断游戏是否胜利
 */
 private boolean isWin()
 {
 //判断所有列是否满足条件
 for (int i = 0; i < array.length; i++) {
 if(!this.isYesArray(array[i]))return false;
 }

 //判断所有行是否满足条件
 for (int i = 0; i < array.length; i++) {
 int[] a = new int[9];
 for (int j = 0; j < a.length; j++) {
 a[j] = array[j][i];
 }
 if(!this.isYesArray(a))return false;
 }

 //判断所有小矩阵
 int[] a1 = this.getSubJuzhen(0, 0);
 if(!this.isYesArray(a1))return false;
 int[] a2 = this.getSubJuzhen(0, 3);
 if(!this.isYesArray(a2))return false;
 int[] a3 = this.getSubJuzhen(0, 6);
 if(!this.isYesArray(a3))return false;
 int[] a4 = this.getSubJuzhen(3, 0);
 if(!this.isYesArray(a4))return false;
 int[] a5 = this.getSubJuzhen(3, 3);
 if(!this.isYesArray(a5))return false;
 int[] a6 = this.getSubJuzhen(3, 6);
 if(!this.isYesArray(a6))return false;
 int[] a7 = this.getSubJuzhen(6, 0);
 if(!this.isYesArray(a7))return false;
 int[] a8 = this.getSubJuzhen(6, 3);
 if(!this.isYesArray(a8))return false;
 int[] a9 = this.getSubJuzhen(6, 6);
 if(!this.isYesArray(a9))return false;


 return true;
 }

 /**
 * 得到小矩阵
 * x、y:标记 小矩阵左上角
 * @return
 */
 private int[] getSubJuzhen(int x, int y)
 {
 int[] arr = new int[9];
 for (int i = 0; i < 3; i++) {
 for (int j = 0; j < 3; j++) {
 arr[i * 3 + j] = array[x + i][y + j];
 }
 }
 return arr;
 }


 /****************以下是鼠标事件******************/

 @Override
 public void mousePressed(MouseEvent e) {

 isNoPress = false; 
 int x = e.getX();
 int y = e.getY();
// System.out.println(x +" " + y);

 // 选项区
 if(y >= ny && y <= ny + blockH && x >= nx && x <= nx + 10 * blockW){
 this.number = (x - nx) / blockW;
 }

 //游戏区
 if(y >= startY && y <= startY + 9 * blockH && x >= startX && x <= startX + 9 * blockW){
 int i = (y - startY) / blockH;
 int j = (x - startX) / blockW;
 if(flag[i][j] == true)
 {
 array[i][j] = number;
 }
 }

 //判断是否胜利
 if(isWin())
 {
 this.isWin = true;
 }

 // 重启游戏
 if(isWin && y >= 8 && y <= 25 && x >= 35 && x <= 251){
 sodu = new sodu();
 this.array = sodu.getArray();
 this.initFlag();
 isWin = false;
 isNoPress = true; 
 number = 0;
 }

 //重绘界面
 this.repaint();

 }


 @Override
 public void mouseReleased(MouseEvent arg0) {
 }
 @Override
 public void mouseClicked(MouseEvent arg0) {
 }
 @Override
 public void mouseEntered(MouseEvent arg0) {
 }
 @Override
 public void mouseExited(MouseEvent arg0) {
 }


} 

package tiger;
import java.util.Random;


public class sodu {
 private int[][] sodu = null;
 private int[] tai = null;

 /**
 * 构造方法
 * 因为每执行一次递归都会把数组tai元素全置为-1.
 * 所以在执行一次递归后需要重新给tai赋值。
 */
 public sodu(){

 do{
 this.init();

 tai = getMixArray();
 tiger(0,0,0,0); //upleft

 tai = getMixArray();
 tiger(0,3,0,3); //up

 tai = getMixArray();
 tiger(0,6,0,6); //upright

 tai = getMixArray();
 tiger(3,0,3,0); //left

 tai = getMixArray();
 tiger(3,6,3,6); //right

 tai = getMixArray();
 tiger(6,0,6,0); //downleft

 tai = getMixArray();
 tiger(6,3,6,3); //down

 tai = getMixArray();
 tiger(6,6,6,6); //downright
 }while(this.isHaveZero());

 }


 /**
 * 得到一个随机数组(元素1到9无重复)
 * @param array
 */
 private int[] getMixArray()
 {
 int[] array = {1,2,3,4,5,6,7,8,9};
 for (int i = 0; i < array.length; i++) 
 {
 int rand = (int) (Math.random() * 9);
 int middle = array[i];
 array[i] = array[rand];
 array[rand] = middle;
 }
 return array;
 }


 /**
 * 初始化数独数组
 * 会初始化正中间的3*3矩阵
 */
 private void init()
 {
 sodu = new int[9][9];

 int[] array = this.getMixArray();
 for (int i = 0; i < 3; i++) {
 for (int j = 0; j < 3; j++) {
 sodu[3+i][3+j] = array[i * 3 + j];
 }
 } 
 }

 /**
 * 递归方法
 * 
 * 生成(i,j)处的值
 * 
 * xi和xj 分别是初始调用该方法时的i和j
 * @return
 */
 private boolean tiger(int i, int j, int xi, int xj)
 {
 if(i - xi == 3)return true;
 for (int j2 = 0; j2 < tai.length; j2++) {
 if(tai[j2] != -1 && isGood(i,j,tai[j2]))
 {
 sodu[i][j] = tai[j2];
 tai[j2] = -1;
 if(j-xj < 2){
 if(tiger(i,j+1,xi,xj))
 {
 return true;
 }else{
 tai[j2] = sodu[i][j];
 sodu[i][j] = 0;
 continue;
 }
 }else{
 if(tiger(i+1,xj,xi,xj))
 {
 return true;
 }else{
 tai[j2] = sodu[i][j];
 sodu[i][j] = 0;
 continue;
 }
 }
 }
 }
 return false;
 }

 /**
 * 判断数字number是否可以用在坐标(x,y)处
 */
 private boolean isGood(int i, int j, int number) {
 for (int m = 0; m < 9; m++) {
 if (sodu[i][m] == number) {
 return false;
 }
 }
 for (int n = 0; n < 9; n++) {
 if (sodu[n][j] == number) {
 return false;
 }
 }
 return true;
 }
 /**
 * 判断数独数组中是否有0
 */
 private boolean isHaveZero()
 {
 for (int i = 0; i < sodu.length; i++) {
 for (int j = 0; j < sodu[i].length; j++) {
 if(sodu[i][j] == 0)
 {
 return true;
 }
 }
 }
 return false;
 }

 /**
 * 得到一个为数独程序用的数独初始数组
 * 是在sodu数组的基础上,对一些随机的位置赋为0而得
 */
 public int[][] getArray()
 {
 int time = 50; //赋值为0的位置个数
 Random rdm = new Random();
 while(time > 0)
 {
 int rand = rdm.nextInt(81);
 int i = rand / 9;
 int j = rand % 9;
 sodu[i][j] = 0;
 time-- ;
 }
 return sodu;
 }
}

 

评论
0/200