开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 游戏 > 其他智力游戏 > 查看源码
NQueenDlg.cpp
资源名称：NQueen.rar　[点击查看]
上传用户：hncsjd
上传日期：2022-07-08
资源大小：3772k
文件大小：10k
源码类别：

其他智力游戏

开发平台：

Visual C++

NQueenDlg.cpp：源码内容
  1. // NQueenDlg.cpp : implementation file
  2. //
  3. #include "stdafx.h"
  4. #include "NQueen.h"
  5. #include "NQueenDlg.h"
  7. #ifdef _DEBUG
  8. #define new DEBUG_NEW
  9. #undef THIS_FILE
  10. static char THIS_FILE[] = __FILE__;
  11. #endif
  13. /////////////////////////////////////////////////////////////////////////////
  14. // CAboutDlg dialog used for App About
  16. class CAboutDlg : public CDialog
  17. {
  18. public:
  19. CAboutDlg();
  21. // Dialog Data
  22. //{{AFX_DATA(CAboutDlg)
  23. enum { IDD = IDD_ABOUTBOX };
  24. //}}AFX_DATA
  26. // ClassWizard generated virtual function overrides
  27. //{{AFX_VIRTUAL(CAboutDlg)
  28. protected:
  29. virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
  30. //}}AFX_VIRTUAL
  32. // Implementation
  33. protected:
  34. //{{AFX_MSG(CAboutDlg)
  35. //}}AFX_MSG
  36. DECLARE_MESSAGE_MAP()
  37. };
  39. CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
  40. {
  41. //{{AFX_DATA_INIT(CAboutDlg)
  42. //}}AFX_DATA_INIT
  43. }
  45. void CAboutDlg::DoDataExchange(CDataExchange* pDX)
  46. {
  47. CDialog::DoDataExchange(pDX);
  48. //{{AFX_DATA_MAP(CAboutDlg)
  49. //}}AFX_DATA_MAP
  50. }
  52. BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
  53. //{{AFX_MSG_MAP(CAboutDlg)
  54. // No message handlers
  55. //}}AFX_MSG_MAP
  56. END_MESSAGE_MAP()
  58. /////////////////////////////////////////////////////////////////////////////
  59. // CNQueenDlg dialog
  61. CNQueenDlg::CNQueenDlg(CWnd* pParent /*=NULL*/)
  62. : CDialog(CNQueenDlg::IDD, pParent)
  63. {
  64. //{{AFX_DATA_INIT(CNQueenDlg)
  65. //}}AFX_DATA_INIT
  66. // Note that LoadIcon does not require a subsequent DestroyIcon in Win32
  67. m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
  68. }
  70. void CNQueenDlg::DoDataExchange(CDataExchange* pDX)
  71. {
  72. CDialog::DoDataExchange(pDX);
  73. //{{AFX_DATA_MAP(CNQueenDlg)
  74. DDX_Control(pDX, IDC_QUEEN_PANEL, m_panel);
  75. //}}AFX_DATA_MAP
  76. }
  78. BEGIN_MESSAGE_MAP(CNQueenDlg, CDialog)
  79. //{{AFX_MSG_MAP(CNQueenDlg)
  80. ON_WM_SYSCOMMAND()
  81. ON_WM_PAINT()
  82. ON_WM_QUERYDRAGICON()
  83. ON_BN_CLICKED(IDC_START, OnStart)
  84. ON_BN_CLICKED(IDC_PAUSE, OnPause)
  85. ON_BN_CLICKED(IDC_CONTINUE, OnContinue)
  86. ON_BN_CLICKED(IDC_STOP, OnStop)
  87. ON_BN_CLICKED(IDC_ABOUT, OnAbout)
  88. ON_BN_CLICKED(IDC_STEP_BY, OnStepBy)
  89. ON_BN_CLICKED(IDC_NO_INT, OnNoInt)
  90. ON_WM_CLOSE()
  91. //}}AFX_MSG_MAP
  92. END_MESSAGE_MAP()
  94. /////////////////////////////////////////////////////////////////////////////
  95. // CNQueenDlg message handlers
  97. BOOL CNQueenDlg::OnInitDialog()
  98. {
  99. CDialog::OnInitDialog();
  101. // Add "About..." menu item to system menu.
  103. // IDM_ABOUTBOX must be in the system command range.
  104. ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
  105. ASSERT(IDM_ABOUTBOX < 0xF000);
  107. CMenu* pSysMenu = GetSystemMenu(FALSE);
  108. if (pSysMenu != NULL)
  109. {
  110. CString strAboutMenu;
  111. strAboutMenu.LoadString(IDS_ABOUTBOX);
  112. if (!strAboutMenu.IsEmpty())
  113. {
  114. pSysMenu->AppendMenu(MF_SEPARATOR);
  115. pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
  116. }
  117. }
  119. // Set the icon for this dialog.  The framework does this automatically
  120. //  when the application's main window is not a dialog
  121. SetIcon(m_hIcon, TRUE); // Set big icon
  122. SetIcon(m_hIcon, FALSE); // Set small icon
  124. // TODO: Add extra initialization here
  125. this_mutex = CreateMutex(NULL,FALSE,NULL);
  126. pause_event = CreateEvent( 
  127. NULL,     // no security attributes
  128. TRUE,    // manual-reset event
  129. FALSE,     // initial state is signaled
  130. NULL);  
  131. GetDlgItem(IDC_BOARD_SIZE)->SetWindowText("8");
  132. m_panel.SetSize(8);
  133. CButton *step = (CButton *)GetDlgItem(IDC_STEP_BY);
  134. m_step = (step->GetCheck()==BST_CHECKED)?TRUE:FALSE;
  135. CButton *no_int = (CButton *)GetDlgItem(IDC_NO_INT);
  136. m_no_int = (step->GetCheck()==BST_CHECKED)?TRUE:FALSE;
  137. canceling = running = FALSE;
  138. UpdateUI();
  140. return TRUE;  // return TRUE  unless you set the focus to a control
  141. }
  143. void CNQueenDlg::OnSysCommand(UINT nID, LPARAM lParam)
  144. {
  145. if ((nID & 0xFFF0) == IDM_ABOUTBOX)
  146. {
  147. CAboutDlg dlgAbout;
  148. dlgAbout.DoModal();
  149. }
  150. else
  151. {
  152. CDialog::OnSysCommand(nID, lParam);
  153. }
  154. }
  156. // If you add a minimize button to your dialog, you will need the code below
  157. //  to draw the icon.  For MFC applications using the document/view model,
  158. //  this is automatically done for you by the framework.
  160. void CNQueenDlg::OnPaint() 
  161. {
  162. if (IsIconic())
  163. {
  164. CPaintDC dc(this); // device context for painting
  166. SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);
  168. // Center icon in client rectangle
  169. int cxIcon = GetSystemMetrics(SM_CXICON);
  170. int cyIcon = GetSystemMetrics(SM_CYICON);
  171. CRect rect;
  172. GetClientRect(&rect);
  173. int x = (rect.Width() - cxIcon + 1) / 2;
  174. int y = (rect.Height() - cyIcon + 1) / 2;
  176. // Draw the icon
  177. dc.DrawIcon(x, y, m_hIcon);
  178. }
  179. else
  180. {
  181. CDialog::OnPaint();
  182. }
  183. }
  185. // The system calls this to obtain the cursor to display while the user drags
  186. //  the minimized window.
  187. HCURSOR CNQueenDlg::OnQueryDragIcon()
  188. {
  189. return (HCURSOR) m_hIcon;
  190. }
  192. void CNQueenDlg::OnStart() //"开始"按钮单击事件响应函数
  193. {
  194. DWORD dwThreadId; 
  195.     HANDLE hThread;    
  197. CString str;
  198. GetDlgItem(IDC_BOARD_SIZE)->GetWindowText(str);
  199. int newn = atoi(str);
  200. if( newn<=0 )
  201. {
  202. MessageBox("大小不能小于1", "警告", MB_OK);
  203. return;
  204. }
  205. else  N = newn;
  206. m_panel.SetSize(N);
  207. step = m_step;
  208. no_int = m_no_int;
  209. running = TRUE;
  210. pausing = canceling = FALSE;
  211. UpdateUI();
  212.     hThread = CreateThread( 
  213.         NULL,                        // default security attributes 
  214.         0,                           // use default stack size  
  215.         ThreadGo,                  // thread function 
  216.         this,                // argument to thread function 
  217.         0,                           // use default creation flags 
  218.         &dwThreadId);                // returns the thread identifier 
  220. // Check the return value for success. 
  222. if (hThread == NULL)
  223. MessageBox( NULL, "CreateThread failed.", MB_OK );
  224. }
  226. void CNQueenDlg::OnPause() //"暂停/单步"按钮单击事件响应函数
  227. {
  228. WaitForSingleObject(this_mutex,INFINITE);
  229. step = TRUE;
  230. if(pausing)  SetEvent(pause_event);
  231. ReleaseMutex(this_mutex);    
  232. UpdateUI();
  233. }
  235. void CNQueenDlg::OnContinue() //"继续"按钮单击事件响应函数
  236. {
  237. WaitForSingleObject(this_mutex,INFINITE);
  238. step = FALSE;
  239. if(pausing)  SetEvent(pause_event);
  240. ReleaseMutex(this_mutex);
  241. UpdateUI();
  242. }
  244. void CNQueenDlg::OnStop() //"停止"按钮单击事件响应函数
  245. {
  246. WaitForSingleObject(this_mutex, INFINITE);
  247. step = FALSE;
  248. canceling = TRUE;
  249. if(pausing)  SetEvent(pause_event);
  250. ReleaseMutex(this_mutex);
  251. UpdateUI();
  252. }
  254. void CNQueenDlg::OnStepBy() //"单步"复选框按钮单击事件响应函数
  255. {
  256. CButton *step = (CButton *)GetDlgItem(IDC_STEP_BY);
  257. m_step = (step->GetCheck()==BST_CHECKED)?TRUE:FALSE;
  258. if(m_step)
  259. {
  260. CButton *autoBtn = (CButton *)GetDlgItem(IDC_NO_INT);
  261. autoBtn->SetCheck(FALSE);
  262. m_no_int = FALSE;
  263. }
  264. }
  266. void CNQueenDlg::OnNoInt() //"不中断"复选框按钮单击事件响应函数
  267. {
  268. CButton *autoBtn = (CButton *)GetDlgItem(IDC_NO_INT);
  269. m_no_int = (autoBtn->GetCheck()==BST_CHECKED)?TRUE:FALSE;
  270. if( m_no_int )
  271. {
  272. CButton *step = (CButton *)GetDlgItem(IDC_STEP_BY);
  273. step->SetCheck(FALSE);
  274. m_step = FALSE;
  275. }
  276. }
  278. void CNQueenDlg::OnAbout() //"关于"按钮单击事件响应函数
  279. {
  280. CAboutDlg dlgAbout;
  281. dlgAbout.DoModal();
  282. }
  284. DWORD WINAPI CNQueenDlg::ThreadGo( LPVOID lpParam )
  285. { 
  286. CNQueenDlg *dlg = (CNQueenDlg *)lpParam;    
  287. dlg->Go();
  288.     return 0; 
  289. } 
  291. void WINAPI CNQueenDlg::Go( )
  292. {
  293.     count = 0;
  294.     queen = new int[N];
  295.     rk = new BOOLEAN[2 * N - 1];
  296.     lk = new BOOLEAN[2 * N - 1];
  297.     mk = new BOOLEAN[N];
  298.     for(int i = 0; i < N; i++)
  299. queen[i] = -1;
  300. memset(rk, 0, (2*N-1)*sizeof(BOOLEAN));
  301. memset(lk, 0, (2*N-1)*sizeof(BOOLEAN));
  302. memset(mk, 0, N*sizeof(BOOLEAN));
  303. ResetEvent(pause_event);
  304.     Step(0);
  305. delete [] queen;
  306. delete [] rk;
  307. delete [] lk;
  308. delete [] mk;
  309. if(!canceling)
  310. {
  311. TCHAR msg[30];
  312. sprintf(msg, "找到%d种组合。", count);
  313. MessageBox(msg, "八皇后", MB_OK);
  314. }
  315. count = 0;
  316. canceling = running = FALSE;
  317. UpdateUI();
  318. }
  320. //安排皇后的递归算法
  321. void WINAPI CNQueenDlg::Step(int i)
  322. {
  323.     for( int j = 0; j < N; j++ )
  324. {
  325. WaitForSingleObject(this_mutex, INFINITE);
  326. if(canceling)  return;
  327. ReleaseMutex(this_mutex);
  328. if( !mk[j] && !rk[i + j]  && !lk[N - 1 + i - j] )
  329. {
  330. queen[i] = j;
  331. rk[i + j] = TRUE;
  332. lk[N - 1 + i - j] = TRUE;
  333. mk[j] = TRUE;
  334. if( i == N - 1 )
  335. {
  336. count++;          
  337. UpdateQPanel(i, queen[i]);   
  338. WaitForSingleObject(this_mutex,INFINITE);
  339. if(!step&&!no_int)
  340. {
  341. ReleaseMutex(this_mutex);
  342. UpdateUI();
  343. DoPause();   
  344. }
  345. else
  346. {
  347. ReleaseMutex(this_mutex);
  348. }
  349. }
  350. else
  351. {
  352. UpdateQPanel(i, queen[i]);
  353. Step(i + 1);
  354. }
  355. queen[i] = -1;
  356. rk[i + j] = FALSE;
  357. lk[i + N - 1 - j] = FALSE;
  358. mk[j] = FALSE;
  359. UpdateQPanel(i, queen[i]);
  360. }
  361.     }
  362. }
  364. void CNQueenDlg::OnClose() 
  365. {
  366. if(running)
  367. this->MessageBox("正在运行，请先按“停止”按钮停止。", "警告");
  368. else  CDialog::EndDialog(0);
  369. }
  371. void CNQueenDlg::UpdateQPanel(int *queen)
  372. {
  373. m_panel.SetQueen(queen);
  374. WaitForSingleObject(this_mutex, INFINITE);
  375. if( step )
  376. {
  377. ReleaseMutex(this_mutex);
  378. DoPause();
  379. } 
  380. else  ReleaseMutex(this_mutex);
  381. }
  383. void CNQueenDlg::UpdateQPanel(int row, int col)
  384. {
  385. m_panel.SetQueen(row, col);
  386. if(step)
  387. {
  388. ReleaseMutex(this_mutex);
  389. DoPause();
  390. } 
  391. else  ReleaseMutex(this_mutex);
  392. }
  394. void CNQueenDlg::DoPause()
  395. {
  396. WaitForSingleObject(this_mutex, INFINITE);
  397. pausing = TRUE;
  398. ReleaseMutex(this_mutex);
  399. UpdateUI();
  400. WaitForSingleObject(pause_event,INFINITE);
  401. ResetEvent(pause_event);
  402. WaitForSingleObject(this_mutex, INFINITE);
  403. pausing  = FALSE;
  404. ReleaseMutex(this_mutex);
  405. UpdateUI();
  406. }
  408. void CNQueenDlg::UpdateUI()
  409. {
  410. WaitForSingleObject(this_mutex, INFINITE);
  411. GetDlgItem(IDC_BOARD_SIZE)->EnableWindow(!running&&!canceling);
  412. GetDlgItem(IDC_NO_INT)->EnableWindow(!running&&!canceling);
  413. GetDlgItem(IDC_STEP_BY)->EnableWindow(!running&&!canceling);
  414. GetDlgItem(IDC_START)->EnableWindow(!running&&!canceling);
  416. GetDlgItem(IDC_PAUSE)->EnableWindow(running&&!canceling);
  417. GetDlgItem(IDC_CONTINUE)->EnableWindow(running&&!canceling&&pausing);
  418. GetDlgItem(IDC_STOP)->EnableWindow(running&&!canceling);
  419. ReleaseMutex(this_mutex);
  420. }