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
分享到:
相关推荐
NULL 博文链接:https://zwhc.iteye.com/blog/711186
NULL 博文链接:https://zwhc.iteye.com/blog/713818
本程序为求解关灯游戏的算法,同时还有一个测试程序,
双层规划模型的遗传算法求解的Matlab源码-双层规划模型的遗传算法求解的Matlab源码.doc 非常实用,值得一看
关灯游戏(Lights Out)最强解题程序,包含多彩颜色情况解题,程序可以给出全部解法。
C++大作业基于C++实现Eigen求解曲线拟合源码.zipC++大作业基于C++实现Eigen求解曲线拟合源码.zipC++大作业基于C++实现Eigen求解曲线拟合源码.zipC++大作业基于C++实现Eigen求解曲线拟合源码.zipC++大作业基于C++实现...
双层规划模型的遗传算法求解的Matlab源码.doc
Python 实现的有限元方程求解程序源码课设项目.zipPython 实现的有限元方程求解程序源码课设项目.zipPython 实现的有限元方程求解程序源码课设项目.zipPython 实现的有限元方程求解程序源码课设项目.zipPython 实现...
VC游戏编写中的求解最短路径算法源码,本示例是自动寻径演示,篮点是起点,红点是终点,按确定键开始。源码爱好者注:编译后运行的时候请把EXE文件从Debug目录中拷贝到项目根目录中,若不然会出错。 编著、程序...
数据结构课设基于SAT的二进制数独游戏求解C++源码+课设报告+代码注释.zip 数据结构课设基于SAT的二进制数独游戏求解C++源码+课设报告+代码注释.zip 数据结构课设基于SAT的二进制数独游戏求解C++源码+课设报告+代码...
基于MATLAB实现微分方程有限元离散+隐式梯度计算+SQP求解优化问题源码(常微分系统).zip基于MATLAB实现微分方程有限元离散+隐式梯度计算+SQP求解优化问题源码(常微分系统).zip基于MATLAB实现微分方程有限元离散+隐式...
推箱子界面程序, 可以玩游戏, 包括源码 推箱子界面程序内置演示解法和求解调用, 使用sokoban.exe的解法表达式 推箱子也叫搬运工,仓库小子 ************************* 算法DLL模块已经完全成熟并完成32位Windows...
高等应用数学问题的MATLAB求解_matlab源码.rar
基于Python实现的迷宫求解小游戏.zip 这是95分以上高分必过课程设计项目,下载即用无需修改,确保可以运行。也可作为期末大作业。 基于Python实现的迷宫求解小游戏.zip 这是95分以上高分必过课程设计项目,下载即...
22个城市TSP问题求解,matlab源码,可运行
【优化求解】粒子群优化和重力搜索算法求解MLP问题matlab源码.md
自动求解各种难度的数独游戏 瞬间完成 源码开放,无需积分,学习编程的油条们赶紧下载吧
基于Matlab实现连续模型求解方法(源码).rar
对布朗运动的方程求解 是个随机微分方程 进行求解,matlab源码
基于SAT的二进制数独游戏求解程序 介绍 要求基于DPLL算法实现一个完备SAT求解器,对输入的CNF范式算例文件,解析并建立其内部表示;精心设计问题中变元、文字、子句、公式等有效的物理存储结构以及一定的分支变元...