问题描述

棋盘问题，求解和为15的棋盘游戏问题

求解和为15的棋盘游戏问题，求解和为15的棋盘游戏问题，求解和为15的棋盘游戏问题

解决方案

package chapter_four;

public class J_Grid15 {
int [] [] m_board;

J_Grid15(){
    m_board = new int [3][3];
}

//输出棋盘的格线行
private void mb_outputGridRowBoard(){
    int i;
    System.out.print("+");
    for(i=0; i<5; i++){
        System.out.print("-");
    }
    System.out.println("+");
}

//输出棋盘的数据行
private void mb_outputGridRowBoard(int i){
    int j;
    for(j=0; j< m_board.length; j ++){
        System.out.print("|"+m_board[i][j]);
    }
    System.out.println("|");
}

//输出棋盘
public void mb_outputGrid(){
    int i;
    mb_outputGridRowBoard();
    for(i=0; i< m_board.length; i++){
        mb_outputGridRowBoard(i);
        mb_outputGridRowBoard();
    }
}

//初始化数据
private void mb_dataInit(){
    int i,j,k;
    for(i=0, k=1; i < m_board.length; i++){
        for(j=0; j < m_board.length; j++,k++)
            m_board[i][j] = k;
    }
}

//数据结束检测
//这里琼穷举是由后面开始不断的由1-9的变化，所以棋盘的数字位置回到初始化状态，那么穷举结束
private boolean mb_dataEnd(){
    int i,j,k;
    for(i=0,k=9; i < m_board.length; i++)
        for(j=0; j < m_board.length; j++,k--)
            if(m_board[i][j] != k)
                return false;
    return true;
}

//取下一个数据
//这里取下一个数据就是后面的棋盘位置不断从1-9变化，举一个例子，
//当第7，8,9的位置的值为1,2,3,则下一个值为124，然后是125.。。。。。131，139,141。。。。
private void mb_dataNext(){
    int i,j;
    for(i = m_board.length-1; i>=0; i--)
        for(j = m_board.length-1; j>=0; j--)
            if(m_board[i][j] ==9)
                m_board[i][j] = 1;
            else{
                m_board[i][j] ++;
                return;
            }
}

//数据检测：判断数据中是否含有相同的数字
//这里认真看会明白的，就是如果有相同的数字，则1-9的位置必定有空值，所以j会不等于9
private boolean mb_dataCheckDifferent(){
    int i,j;
    int [] digit = new int [10];
    for(i = 0 ; i < m_board.length; i++){
        for(j = 0; j < m_board.length; j ++)
            digit[m_board[i][j]] = 1;
    }
    for(i = 1,j=0; i< digit.length; i++){
        j+= digit[i];
    }
    if( j == 9)
        return true;
    return false;
}

//数据检测：各行和是否为15
private boolean mb_dataCheckSumRow(){
    int i,j,k;
    for(i=0; i < m_board.length; i++){
        for(j=0,k=0; j<m_board.length; j++)
            k+= m_board[i][j];
        if (k!=15)
            return false;
    }
    return true;
}

//数据检测：各列和是否为15
private boolean mb_dataCheckSumColumn(){
    int i,j,k;
    for(i=0; i < m_board.length; i++){
        for(j=0,k=0; j<m_board.length; j++)
            k+= m_board[j][i];
        if (k!=15)
            return false;
    }
    return true;
}

private boolean mb_dataCheck(){
    if (!mb_dataCheckDifferent())
        return false;
    if (!mb_dataCheckSumRow())
        return false;
    if (!mb_dataCheckSumColumn())
        return false;

    //检测对角线的和是否为15
    if (m_board[0][0] + m_board[1][1] + m_board[2][2] != 15)
        return false;
    if (m_board[0][2] + m_board[1][1] + m_board[2][0] != 15)
        return false;
    return true;
}

//求解并输出棋盘问题
public void mb_arrage(){
    int n=1;
    for( mb_dataInit(); !mb_dataEnd(); mb_dataNext()){  //mb_dataEnd若返回false则继续,否则结束循环
        if(mb_dataCheck()){
            System.out.println("第"+n+"个结果：");
            n++;
            mb_outputGrid();
        }
    }
}

public static void main(String args[])
{
    J_Grid15 a = new J_Grid15();
    a.mb_arrage();
}

}

以上和为15的棋盘游戏的代码，对于我这个初学者来说，其实那两个mb_dataEnd() ,mb_dataNext() 函数的理解花了一些时间

因为上网查找资料，没有解释这两个函数，然后我就在这说说：

这是一个穷举过程，即每一种可能都列举了，我举一个例子：

例如在棋盘的m_board[2][0]、m_board[2][1]、m_board[2][2]分别为1、2、3，使用一次mb_dataNext() 函数后变成1、2、4

使用第二次mb_dataNext() 函数后变成1、2、5 .... ....

到1、2、9时，再使用就是1、3、1，............

不断使用， 到1、9、9时，再使用则变成2、1、1......... 之后是2、1、2

这样不断穷举，产生很多组数，判断时候满足和为15，满足则输出！！！

mb_dataEnd() 就不用说了吧，穷举回到初始状态就结束，使得每一种情况都出现过.....

解决方案二：

http://download.csdn.net/detail/csrych/3254299