《求解关灯游戏》源码分析

http://blog.163.com/prevBlogPerma.do?host=simplesource&srl=10341406200981362416959&mode=prev

 

这个代码写得相当不错。

 

这里先对蛮力搜索做个分析。

 

LightsOffAppDlg.h 添加了些调试内容。

 

// LightsOffAppDlg.h : 头文件
//

#pragma once
#include "lightsoff.h"
#include "afxwin.h"

// CLightsOffAppDlg 对话框
class CLightsOffAppDlg : public CDialog
{
// 构造
public:
	CLightsOffAppDlg(CWnd* pParent = NULL);	// 标准构造函数

// 对话框数据
	enum { IDD = IDD_LIGHTSOFFAPP_DIALOG };

	protected:
	virtual void DoDataExchange(CDataExchange* pDX);	// DDX/DDV 支持

    int m_iUnitWidth;
    int m_iX0;
    int m_iY0;
    CField m_field;
    CField m_mask;
    CField m_recorder;
    bool   m_bKillMsg;
    int    m_iState;
    CMatrix m_trans;
    CMatrix m_switch;

	FILE * fp ;

    // 设置大小
    void SetSize()
    {
        int iWidth = m_cbWidth.GetCurSel() + 1;
        int iHeight = m_cbHeight.GetCurSel() + 1;
        m_field.Create(iWidth, iHeight);
        m_mask = m_field;
        m_recorder = m_field;
        int w, h;
        int fw = m_iUnitWidth * iWidth;
        int fh = m_iUnitWidth * iHeight;
        w = fw + 128;
        h = fh + 100;
        if(w < 360)
        {
            w = 360;
        }
        if(h < 200)
        {
            h = 200;
        }
        MoveWindow(
            (::GetSystemMetrics(SM_CXSCREEN) - w) / 2,
            (::GetSystemMetrics(SM_CYSCREEN) - h) / 2,
            w, h);
        CRect rect;
        GetClientRect(&rect);
        m_iX0 = 50 + (rect.Width() - fw) / 2;
        m_iY0 = 50;
        // 计算求解矩阵
        m_switch.Create(iWidth, iHeight);
        m_trans.Create(iWidth, iHeight);
        m_trans.SetAsI();
        m_switch.SetAsL(m_mask);
        m_switch.Inverse(m_trans);
        m_switch.SetAsL(m_mask);
        Invalidate();
    }
    // 执行线程
    static UINT ThreadProc(LPVOID pParm)
    {
        CLightsOffAppDlg * pClass = (CLightsOffAppDlg *)pParm;
        //pClass->m_iMode = PRO_MODE_ASYN;

        pClass->m_iState = 1;
        CField fld;
        fld.Create(pClass->m_field.Width(), pClass->m_field.Height());
        pClass->m_recorder = fld;
		
		pClass->fp = fopen("m.txt", "w");
        if(pClass->fp)
        {
            fld.Print(pClass->fp);
            pClass->m_recorder.Print(pClass->fp);
			pClass->m_mask.Print(pClass->fp);
			pClass->m_field.Print(pClass->fp);
        }

        if(pClass->FindRecord(fld, pClass->m_recorder))
        {
            pClass->Invalidate(false);
            if(pClass->m_bKillMsg == false)
            {
                pClass->MessageBox("找到解", "成功", MB_ICONINFORMATION);
            }
        }
        else
        {
            pClass->Invalidate(false);
            if(pClass->m_bKillMsg == false)
            {
                pClass->MessageBox("未找到解", "失败", MB_ICONERROR);
            }
        }
        pClass->KillTimer(0);
        pClass->m_iState = 0;
        pClass->SetDlgItemText(IDC_BT_SEARCH, "蛮力搜索");
        //pClass->m_iMode = PRO_MODE_BLOCK;

		if(pClass->fp)
		{
			fclose(pClass->fp);
		}

        return 0;
    }
    bool FindRecord(CField &fld, CField &rcd, int x = 0, int y = 0)
    {
        if(m_bKillMsg)
        {
            return false;
        }
        fld.AndNot(m_mask);
		
        if(fld == m_field)
        {
            return true;
        }
        if(x >= fld.Width())
        {
            y++;
            x = 0;
            if(y >= fld.Height())
            {
				if(fp)
				{
					fprintf(fp, "out of range. x=%d, y=%d", x, y);
					fprintf(fp, "\n");
				}

                return false;
            }
        }
        int i;

        if(fp)
        {
			fprintf(fp, "x=%d, y=%d", x, y);
			fprintf(fp, "\n");
            fld.Print(fp);
            rcd.Print(fp);
			m_mask.Print(fp);
			m_field.Print(fp);
        }


        if(m_mask.IsLightOn(x, y))
        {
			fprintf(fp, "m_mask.IsLightOn(%d, %d)", x, y);
			fprintf(fp, "\n");

            if(FindRecord(fld, rcd, x + 1, y))
            {
                return true;
            }
        }
        else
        {
			fprintf(fp, "not m_mask.IsLightOn(%d, %d)", x, y);
			fprintf(fp, "\n");
            for(i = 0; i < 2 && !m_bKillMsg; i++)
            {
                if(FindRecord(fld, rcd, x + 1, y))
                {
                    return true;
                }
								if(fp)
								{
									fprintf(fp, "x=%d, y=%d", x, y);
									fprintf(fp, "\n");
									fprintf(fp, "i=%d", i);
									fprintf(fp, "\n");
								}
                fld.LightsOff(x, y);
                rcd.SetLight(x, y);

								if(fp)
								{
									fprintf(fp, "fld.LightsOff(%d, %d);", x, y);
									fprintf(fp, "\n");
									fld.Print(fp);
									rcd.Print(fp);
									m_mask.Print(fp);
									m_field.Print(fp);
								}

            }
        }
        return false;
    }

// 实现
protected:
	HICON m_hIcon;

	// 生成的消息映射函数
	virtual BOOL OnInitDialog();
	afx_msg void OnSysCommand(UINT nID, LPARAM lParam);
	afx_msg void OnPaint();
	afx_msg HCURSOR OnQueryDragIcon();
	DECLARE_MESSAGE_MAP()
public:
    afx_msg void OnLButtonDown(UINT nFlags, CPoint point);
    afx_msg void OnRButtonDown(UINT nFlags, CPoint point);
    afx_msg void OnLButtonDblClk(UINT nFlags, CPoint point);
    afx_msg void OnLButtonUp(UINT nFlags, CPoint point);
    afx_msg void OnTimer(UINT nIDEvent);
    afx_msg void OnBnClickedBtCompute();
    CComboBox m_cbWidth;
    CComboBox m_cbHeight;
    afx_msg void OnBnClickedBtSearch();
    afx_msg void OnCbnSelchangeCbWidth();
    afx_msg void OnCbnSelchangeCbHeight();
    afx_msg void OnRButtonDblClk(UINT nFlags, CPoint point);
    afx_msg void OnBnClickedBtReverse();
    afx_msg void OnBnClickedBtClear();
};

 

他这解法，是从右下角开始往回开灯求解的。如果用我这个测试代码，千万别从左上角进行测试。否则，日志信息将极宠大。

 

以下列出一小段开灯的递归顺序。

 

44
44

34
 44
 44
34

24
 44
 44

 34
  44
  44
 34
24

14
 44
 44

 34
  44
  44
 34

 24
  44
  44

  34
   44
   44
  34
 24
14