编用回溯法解决跳棋销子的程序http://home.jlu.edu.cn/~z/Algorithms/JumpChess_1.rar

Question

输入 72 2 1 1 1 2 2
2 2 1 1 1 2 2
1 1 1 1 1 1 1
1 1 1 0 1 1 1
1 1 1 1 1 1 1
2 2 1 1 1 2 2
2 2 1 1 1 2 2
Make2DArray(maze, 10, 10);改:Make2DArray(maze, 11, 11);我那个亚书包 有演示

Answer 1

Unhandled exception at 0x00413446 in JumpChess_1.exe: 0xC0000005: Access violation writing location 0x01d4c9c8.
那个黄的指针老指向 stack.h文件中的 stack[++top] = x;语句怎么板?

Answer 2

调试的时候看看top的值啊，是否超出了数组下界，这个异常是非法写内存造成的

Answer 3

//----------------Function.cpp-------------------#include "stdafx.h"
#include "Function.h"BOOL  g_bContinue = TRUE;
BOOL  g_bInterrupt = FALSE;
int   g_ResultCount = 0;
int   gMaxMoveList = 0;HWND  g_DlghWnd;
BOARD JumpGame_Board;
MOVE  gMoveRecord[MAX_MOVERECORD];const INT16 delta_array[MAX_AXES] = {-11, 11, -9, 9, -1, 1, -10, 10};
const INT16 axes_array[MAX_AXES][MAX_XY] = {
    -1, -1, 1, 1, -1, 1, 1, -1, 0, -1, 0, 1, -1, 0, 1, 0
};void init_chess_board(BOARD * board_ptr)
{
    UINT8 boardstartup[10][10] = {
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255,  1,   1,   1,  255, 255, 255, 255,
        255, 255, 255,  1,   1,   1,  255, 255, 255, 255,
        255,  1,   1,   1,   1,   1,   1,   1,  255, 255,
        255,  1,   1,   1,   0,   1,   1,   1,  255, 255,
        255,  1,   1,   1,   1,   1,   1,   1,  255, 255,
        255, 255, 255,  1,   1,   1,  255, 255, 255, 255,
        255, 255, 255,  1,   1,   1,  255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 255, 255
    };
    /* 设置初始棋盘状态 */
    memcpy(board_ptr->board, boardstartup, sizeof(BOARD));
}int get_chess_number(BOARD *board_ptr)
{
    int number = 0;
    for(int y=0; y<BOARD_ROWS; y++)
        for(int x=0; x<BOARD_COLS; x++) {
            if (board_ptr->board[y][x] == CHESS_HAVE)
                number++;
        }    return number;
}int generate_legal_moves(BOARD *node, MOVE *moveList, int depth)
{
    UINT8 start_pos = 13;
    UINT8 *start_ptr = node->board[0];
    UINT8 *cel_ptr = node->board[0] + start_pos;
    UINT8 *stop_ptr = &node->board[7][6], *p;
    int axes;   /* axes */
    int movetotal = 0;
    UINT8 movepos, eatpos, destpos;    /* 第一步 */
    if (depth == 32) {
        /* [64] --> [44] */
        moveList[0].movepos = 64;
        moveList[0].eatpos  = 54;
        moveList[0].destpos = 44;
        return 1;
    }
    /* 第二步 */
    else if (depth == 31) {
        /* [34] --> [54] */
        moveList[0].movepos = 34;
        moveList[0].eatpos  = 44;
        moveList[0].destpos = 54;
        
        /* [32] --> [54] */
        moveList[1].movepos = 32;
        moveList[1].eatpos  = 43;
        moveList[1].destpos = 54;        /* [52] --> [54] */
        moveList[2].movepos = 52;
        moveList[2].eatpos  = 53;
        moveList[2].destpos = 54;        /* [42] --> [64] */
        moveList[3].movepos = 42;
        moveList[3].eatpos  = 53;
        moveList[3].destpos = 64;        return 4;
    }    while (TRUE) {
        /*找到一个有棋子的格子*/
        while(*cel_ptr != CHESS_HAVE)
            if(++cel_ptr >= stop_ptr)
                return movetotal;
        
        /*检查在8个方向上是否能吃掉一颗棋子，并记录被吃掉棋子的位置*/
        movepos = cel_ptr - start_ptr;
        for(axes=0; axes<MAX_AXES; axes++)
        {
            p = cel_ptr + delta_array[axes];
            if (*p == CHESS_HAVE)
            {
                eatpos = p - start_ptr;
                p += delta_array[axes];
                if (*p == CHESS_NONE)
                {
                    /* Record move list */
                    destpos = p - start_ptr;
                    moveList[movetotal].movepos = movepos;
                    moveList[movetotal].eatpos  = eatpos;
                    moveList[movetotal].destpos = destpos;
                    movetotal++;
                }
            }
        }
        cel_ptr++;
    }    return movetotal;
}void make_next_move(BOARD *node, MOVE move)
{
    node->board[0][move.movepos] = CHESS_NONE;
    node->board[0][move.eatpos]  = CHESS_NONE;
    node->board[0][move.destpos] = CHESS_HAVE;
}void unmake_move(BOARD *node, MOVE move)
{
    node->board[0][move.movepos] = CHESS_HAVE;
    node->board[0][move.eatpos]  = CHESS_HAVE;
    node->board[0][move.destpos] = CHESS_NONE;
}void worm_thinking(BOARD *node, int depth, int step)
{
    if (g_bInterrupt) return;
    /* success? */
    if (depth <= 1) {
        /* scan whether success? */
        if (get_chess_number(node) == 1) {
            /* print the result */
            g_ResultCount++;
            ::SendMessage(g_DlghWnd, WM_PRINT_RESULT, 0, 0);
            g_bContinue = FALSE;
            delay(1); g_bContinue = TRUE;
            while (!g_bContinue && !g_bInterrupt) {
                delay(200);
            }
        }
        else {
            MessageBeep(MB_OK);
        }
    }
    else {
        MOVE moveList[MAX_MOVELIST], move;
        int movetotal = generate_legal_moves(node, moveList, depth);
        gMaxMoveList = max(movetotal, gMaxMoveList);
        while (movetotal) {
            /* move the chess */
            move = moveList[movetotal-1];
            make_next_move(node, move);
            gMoveRecord[step-1] = move;
            worm_thinking(node, depth-1, step+1);
            movetotal--;
            unmake_move(node, move);
        }
    }
}

Answer 4

//----------------Function.h-------------------#ifndef ___JUMPGAME_FUNCTION_H__
#define ___JUMPGAME_FUNCTION_H__typedef unsigned char     UINT8;
typedef unsigned short    UINT16;
typedef unsigned __int64  UINT64;
typedef unsigned __int64  U64;
typedef char              INT8;
typedef short             INT16;
typedef __int64           INT64;#define   CHESS_NONE     0x00
#define   CHESS_HAVE     0x01
#define   CHESS_BORDER   0xFF#define   BOARD_COLS     9
#define   BOARD_ROWS     9#define   MAX_AXES       8
#define   MAX_XY         2#define  MAX_MOVELIST    100
#define  MAX_MOVERECORD  33#define  WM_PRINT_RESULT  (WM_USER+100)typedef struct tagBOARD
{
    UINT8 board[BOARD_ROWS+1][BOARD_COLS+1];
}   BOARD;typedef struct tagMOVE
{
    UINT8  movepos;
    UINT8  eatpos;
    UINT8  destpos;
}   MOVE;extern BOOL g_bContinue;
extern BOOL g_bInterrupt;
extern int  g_ResultCount;
extern int  gMaxMoveList;
extern HWND g_DlghWnd;extern BOARD JumpGame_Board;
extern MOVE  gMoveRecord[MAX_MOVERECORD];extern void delay(DWORD millisecond);
extern void init_chess_board(BOARD * board_ptr);
extern int get_chess_number(BOARD * board_ptr);
extern void worm_thinking(BOARD * node, int depth, int step);
#endif

Answer 5

// JumpGameDlg.h : header file
//#if !defined(AFX_JUMPGAMEDLG_H__4EF1465A_32D6_49F6_A1A6_BFFFA49F564F__INCLUDED_)
#define AFX_JUMPGAMEDLG_H__4EF1465A_32D6_49F6_A1A6_BFFFA49F564F__INCLUDED_#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000/////////////////////////////////////////////////////////////////////////////
// CJumpGameDlg dialogclass CJumpGameDlg : public CDialog
{
// Construction
public:
    CJumpGameDlg(CWnd* pParent = NULL); // standard constructor
    ~CJumpGameDlg();// Dialog Data
    //{{AFX_DATA(CJumpGameDlg)
    enum { IDD = IDD_JUMPGAME_DIALOG };
        // NOTE: the ClassWizard will add data members here
    //}}AFX_DATA    // ClassWizard generated virtual function overrides
    //{{AFX_VIRTUAL(CJumpGameDlg)
    protected:
    virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
    //}}AFX_VIRTUAL// Implementation
protected:
    HICON m_hIcon;    // Generated message map functions
    //{{AFX_MSG(CJumpGameDlg)
    virtual BOOL OnInitDialog();
    afx_msg void OnSysCommand(UINT nID, LPARAM lParam);
    afx_msg void OnPaint();
    afx_msg HCURSOR OnQueryDragIcon();
    afx_msg void OnCalcGame();
    virtual void OnOK();
    afx_msg void OnContinue();
    afx_msg void OnStopSearch();
    afx_msg void OnDestroy();
    afx_msg void OnClose();
    //}}AFX_MSG
    DECLARE_MESSAGE_MAP()
    afx_msg void OnPrintResult(WPARAM wParam, LPARAM lParam);
};//{{AFX_INSERT_LOCATION}}
// Microsoft Visual C++ will insert additional declarations immediately before the previous line.#endif // !defined(AFX_JUMPGAMEDLG_H__4EF1465A_32D6_49F6_A1A6_BFFFA49F564F__INCLUDED_)

Answer 6

// JumpGameDlg.cpp : implementation file
//#include "stdafx.h"
#include <mmsystem.h>
#include "Function.h"
#include "JumpGame.h"
#include "JumpGameDlg.h"#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App Aboutclass CAboutDlg : public CDialog
{
public:
    CAboutDlg();// Dialog Data
    //{{AFX_DATA(CAboutDlg)
    enum { IDD = IDD_ABOUTBOX };
    //}}AFX_DATA    // ClassWizard generated virtual function overrides
    //{{AFX_VIRTUAL(CAboutDlg)
    protected:
    virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
    //}}AFX_VIRTUAL// Implementation
protected:
    //{{AFX_MSG(CAboutDlg)
    //}}AFX_MSG
    DECLARE_MESSAGE_MAP()
};CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
    //{{AFX_DATA_INIT(CAboutDlg)
    //}}AFX_DATA_INIT
}void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
    CDialog::DoDataExchange(pDX);
    //{{AFX_DATA_MAP(CAboutDlg)
    //}}AFX_DATA_MAP
}BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
    //{{AFX_MSG_MAP(CAboutDlg)
        // No message handlers
    //}}AFX_MSG_MAP
END_MESSAGE_MAP()/////////////////////////////////////////////////////////////////////////////
// CJumpGameDlg dialogCJumpGameDlg::CJumpGameDlg(CWnd* pParent /*=NULL*/)
    : CDialog(CJumpGameDlg::IDD, pParent)
{
    //{{AFX_DATA_INIT(CJumpGameDlg)
        // NOTE: the ClassWizard will add member initialization here
    //}}AFX_DATA_INIT
    // Note that LoadIcon does not require a subsequent DestroyIcon in Win32
    m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
    /* init Game Board*/
    init_chess_board(&JumpGame_Board);
}CJumpGameDlg::~CJumpGameDlg()
{
    g_bContinue = TRUE;
    g_bInterrupt = TRUE;
}void CJumpGameDlg::DoDataExchange(CDataExchange* pDX)
{
    CDialog::DoDataExchange(pDX);
    //{{AFX_DATA_MAP(CJumpGameDlg)
        // NOTE: the ClassWizard will add DDX and DDV calls here
    //}}AFX_DATA_MAP
}BEGIN_MESSAGE_MAP(CJumpGameDlg, CDialog)
    //{{AFX_MSG_MAP(CJumpGameDlg)
    ON_WM_SYSCOMMAND()
    ON_WM_PAINT()
    ON_WM_QUERYDRAGICON()
    ON_BN_CLICKED(IDC_CALCGAME, OnCalcGame)
    ON_BN_CLICKED(IDC_CONTINUE, OnContinue)
    ON_BN_CLICKED(IDC_STOPSEARCH, OnStopSearch)
    ON_WM_DESTROY()
    ON_WM_CLOSE()
    //}}AFX_MSG_MAP
    ON_MESSAGE(WM_PRINT_RESULT, OnPrintResult)
END_MESSAGE_MAP()/////////////////////////////////////////////////////////////////////////////
// CJumpGameDlg message handlers////////////////////////////////////////
//   -- 短暂延时并能相应消息 --       //
////////////////////////////////////////
void delay(DWORD millisecond)
{
    DWORD start, nowtime;
    start = timeGetTime();
    do
    { 
        MSG msg;
        if ( ::PeekMessage(&msg, g_DlghWnd, 0, 0, PM_NOREMOVE) ) 
        { 
            //::TranslateMessage(&msg); //翻译消息
            //::DispatchMessage(&msg);  //撤去消息
            
            if ( !AfxGetApp()->PumpMessage() ) 
            {
                ::PostQuitMessage(0);
                return;
            }
        }
        nowtime = timeGetTime();
    } while( (nowtime-start) < millisecond );
}BOOL CJumpGameDlg::OnInitDialog()
{
    CDialog::OnInitDialog();    // Add "About..." menu item to system menu.    // IDM_ABOUTBOX must be in the system command range.
    ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
    ASSERT(IDM_ABOUTBOX < 0xF000);    CMenu* pSysMenu = GetSystemMenu(FALSE);
    if (pSysMenu != NULL)
    {
        CString strAboutMenu;
        strAboutMenu.LoadString(IDS_ABOUTBOX);
        if (!strAboutMenu.IsEmpty())
        {
            pSysMenu->AppendMenu(MF_SEPARATOR);
            pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
        }
    }    // Set the icon for this dialog.  The framework does this automatically
    //  when the application's main window is not a dialog
    SetIcon(m_hIcon, TRUE);         // Set big icon
    SetIcon(m_hIcon, FALSE);        // Set small icon
    
    g_DlghWnd = m_hWnd;
    
    return TRUE;  // return TRUE  unless you set the focus to a control
}void CJumpGameDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
    if ((nID & 0xFFF0) == IDM_ABOUTBOX)
    {
        CAboutDlg dlgAbout;
        dlgAbout.DoModal();
    }
    else
    {
        CDialog::OnSysCommand(nID, lParam);
    }
}// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.void CJumpGameDlg::OnPaint() 
{
    if (IsIconic())
    {
        CPaintDC dc(this); // device context for painting        SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);        // Center icon in client rectangle
        int cxIcon = GetSystemMetrics(SM_CXICON);
        int cyIcon = GetSystemMetrics(SM_CYICON);
        CRect rect;
        GetClientRect(&rect);
        int x = (rect.Width() - cxIcon + 1) / 2;
        int y = (rect.Height() - cyIcon + 1) / 2;        // Draw the icon
        dc.DrawIcon(x, y, m_hIcon);
    }
    else
    {
        CDialog::OnPaint();
    }
}// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CJumpGameDlg::OnQueryDragIcon()
{
    return (HCURSOR) m_hIcon;
}void CJumpGameDlg::OnCalcGame() 
{
    g_bContinue = FALSE;
    g_bInterrupt = FALSE;
    g_ResultCount = 0;
    /* 开始搜索棋盘求解 */
    worm_thinking(&JumpGame_Board, get_chess_number(&JumpGame_Board), 1);
}void CJumpGameDlg::OnPrintResult(WPARAM wParam, LPARAM lParam)
{
    /* print the result in the edit box */
    CString result, move;
    result = "Move order of the result:\r\n";
    move.Format("Result total(s): %d.   MaxMoveList is: %d.\r\n", g_ResultCount, gMaxMoveList);
    result += move;
    for(int i=0; i<MAX_MOVERECORD; i++) {
        if (gMoveRecord[i].movepos) {
            move.Format("No.%d: \t(%d) --> (%d).\r\n", 
                i+1, gMoveRecord[i].movepos, gMoveRecord[i].destpos);
            result += move;
        }
        else {
            i = MAX_MOVERECORD;
        }
    }
    result += "The end.";
    /* set the edit box's text */
    SetDlgItemText(IDC_EDIT_RESULT, (LPCTSTR) result);
}void CJumpGameDlg::OnOK() 
{
    SetDlgItemText(IDC_EDIT_RESULT,"Print the result.");    
}void CJumpGameDlg::OnContinue() 
{
    /* 继续搜索其余解 */
    g_bContinue = TRUE;
}void CJumpGameDlg::OnStopSearch() 
{
    /* 完全终止搜索 */
    g_bInterrupt = TRUE;
}void CJumpGameDlg::OnDestroy() 
{
    CDialog::OnDestroy();
    
    g_bContinue = TRUE;
    g_bInterrupt = TRUE;
}void CJumpGameDlg::OnClose() 
{
    g_bContinue = TRUE;
    g_bInterrupt = TRUE;
    
    CDialog::OnClose();
}

Answer 7

 shines老大。这个是mfc工程。谁能实现了。发我油箱好么？
[email protected]谢谢了。

Answer 8

我打包了一下（源码和EXE程序），放到
http://www.cuntn.com/guozi/web/jumpgame.zip我写得不是很好，调试几次，OK就没有继续写了，程序可终止搜索，但继续搜索还没有做好。
当初没有使用多线程，和CEvent等来做线程通信，那时候水平有限。