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

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

其他智力游戏

开发平台：

Visual C++

EightQueenDlg.cpp：源码内容
  1. // EightQueenDlg.cpp : implementation file
  2. //
  3. #include "stdafx.h"
  4. #include "EightQueen.h"
  5. #include "EightQueenDlg.h"
  6. #include "QueenPanel.h"
  8. #ifdef _DEBUG
  9. #define new DEBUG_NEW
  10. #undef THIS_FILE
  11. static char THIS_FILE[] = __FILE__;
  12. #endif
  14. /////////////////////////////////////////////////////////////////////////////
  15. // CAboutDlg dialog used for App About
  17. class CAboutDlg : public CDialog
  18. {
  19. public:
  20. CAboutDlg();
  22. // Dialog Data
  23. //{{AFX_DATA(CAboutDlg)
  24. enum { IDD = IDD_ABOUTBOX };
  25. //}}AFX_DATA
  27. // ClassWizard generated virtual function overrides
  28. //{{AFX_VIRTUAL(CAboutDlg)
  29. protected:
  30. virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
  31. //}}AFX_VIRTUAL
  33. // Implementation
  34. protected:
  35. //{{AFX_MSG(CAboutDlg)
  36. virtual BOOL OnInitDialog();
  37. //}}AFX_MSG
  38. DECLARE_MESSAGE_MAP()
  39. };
  41. CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
  42. {
  43. //{{AFX_DATA_INIT(CAboutDlg)
  44. //}}AFX_DATA_INIT
  45. }
  47. void CAboutDlg::DoDataExchange(CDataExchange* pDX)
  48. {
  49. CDialog::DoDataExchange(pDX);
  50. //{{AFX_DATA_MAP(CAboutDlg)
  51. //}}AFX_DATA_MAP
  52. }
  54. BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
  55. //{{AFX_MSG_MAP(CAboutDlg)
  56. //}}AFX_MSG_MAP
  57. END_MESSAGE_MAP()
  59. /////////////////////////////////////////////////////////////////////////////
  60. // CEightQueenDlg dialog
  62. CEightQueenDlg::CEightQueenDlg(CWnd* pParent /*=NULL*/)
  63. : CDialog(CEightQueenDlg::IDD, pParent)
  64. {
  65. //{{AFX_DATA_INIT(CEightQueenDlg)
  66. //}}AFX_DATA_INIT
  67. // Note that LoadIcon does not require a subsequent DestroyIcon in Win32
  68. m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
  69. }
  71. void CEightQueenDlg::DoDataExchange(CDataExchange* pDX)
  72. {
  73. CDialog::DoDataExchange(pDX);
  74. //{{AFX_DATA_MAP(CEightQueenDlg)
  75. DDX_Control(pDX, IDC_QUEEN_PANEL, m_panel);
  76. //}}AFX_DATA_MAP
  77. }
  79. BEGIN_MESSAGE_MAP(CEightQueenDlg, CDialog)
  80. //{{AFX_MSG_MAP(CEightQueenDlg)
  81. ON_WM_SYSCOMMAND()
  82. ON_WM_PAINT()
  83. ON_WM_QUERYDRAGICON()
  84. ON_BN_CLICKED(IDC_START, OnStart)
  85. ON_BN_CLICKED(IDC_PAUSE, OnPause)
  86. ON_BN_CLICKED(IDC_CONTINUE, OnContinue)
  87. ON_WM_CLOSE()
  88. ON_BN_CLICKED(IDC_STEP_BY, OnStepBy)
  89. ON_BN_CLICKED(IDC_ABOUT, OnAbout)
  90. ON_BN_CLICKED(IDC_STOP, OnStop)
  91. ON_BN_CLICKED(IDC_NO_INT, OnNoInt)
  92. //}}AFX_MSG_MAP
  93. END_MESSAGE_MAP()
  95. /////////////////////////////////////////////////////////////////////////////
  96. // CEightQueenDlg message handlers
  98. BOOL CEightQueenDlg::OnInitDialog()
  99. {
  100. CDialog::OnInitDialog();
  102. // Add "About..." menu item to system menu.
  104. // IDM_ABOUTBOX must be in the system command range.
  105. ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
  106. ASSERT(IDM_ABOUTBOX < 0xF000);
  108. CMenu* pSysMenu = GetSystemMenu(FALSE);
  109. if (pSysMenu != NULL)
  110. {
  111. CString strAboutMenu;
  112. strAboutMenu.LoadString(IDS_ABOUTBOX);
  113. if (!strAboutMenu.IsEmpty())
  114. {
  115. pSysMenu->AppendMenu(MF_SEPARATOR);
  116. pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
  117. }
  118. }
  120. // Set the icon for this dialog.  The framework does this automatically
  121. //  when the application's main window is not a dialog
  122. SetIcon(m_hIcon, TRUE); // Set big icon
  123. SetIcon(m_hIcon, FALSE); // Set small icon
  125. // TODO: Add extra initialization her
  126. this_mutex = CreateMutex(NULL,FALSE,NULL);
  127. pause_event = CreateEvent( 
  128. NULL,     // no security attributes
  129. TRUE,    // manual-reset event
  130. FALSE,     // initial state is signaled
  131. NULL);  
  132. GetDlgItem(IDC_BOARD_SIZE)->SetWindowText("8");
  133. m_panel.SetSize(8);
  134. CButton *step = (CButton *)GetDlgItem(IDC_STEP_BY);
  135. m_step = (step->GetCheck()==BST_CHECKED)?TRUE:FALSE;
  136. CButton *no_int = (CButton *)GetDlgItem(IDC_NO_INT);
  137. m_no_int = (step->GetCheck()==BST_CHECKED)?TRUE:FALSE;
  138. canceling = running = FALSE;
  139. UpdateUI();
  140. return TRUE;  // return TRUE  unless you set the focus to a control
  141. }
  143. void CEightQueenDlg::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 CEightQueenDlg::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 CEightQueenDlg::OnQueryDragIcon()
  188. {
  189. return (HCURSOR) m_hIcon;
  190. }
  192. void CEightQueenDlg::OnStart() 
  193. {
  194. // TODO: Add your control notification handler code here
  195. DWORD dwThreadId; 
  196.     HANDLE hThread;    
  198. CString str;
  199. GetDlgItem(IDC_BOARD_SIZE)->GetWindowText(str);
  200. int newn = atoi(str);
  201. if( newn<=0 )
  202. {
  203. MessageBox("大小不能小于1", "警告", MB_OK);
  204. return;
  205. }
  206. else  n = newn;
  207. m_panel.SetSize(n);
  208. step = m_step;
  209. no_int = m_no_int;
  210. running = TRUE;
  211. pausing = canceling = FALSE;
  212. UpdateUI();
  213.     hThread = CreateThread( 
  214.         NULL,                        // default security attributes 
  215.         0,                           // use default stack size  
  216.         ThreadGo,                  // thread function 
  217.         this,                // argument to thread function 
  218.         0,                           // use default creation flags 
  219.         &dwThreadId);                // returns the thread identifier 
  221. // Check the return value for success. 
  223. if (hThread == NULL)
  224. MessageBox( NULL, "CreateThread failed.", MB_OK );
  225. }
  227. DWORD WINAPI CEightQueenDlg::ThreadGo( LPVOID lpParam )
  228. { 
  229. CEightQueenDlg *dlg = (CEightQueenDlg *)lpParam;    
  230. dlg->Go();
  231.     return 0; 
  232. } 
  234. void WINAPI CEightQueenDlg::Go( )
  235. {
  236.     count = 0;
  237.     queen = new int[n];
  238.     rk = new BOOLEAN[2 * n - 1];
  239.     lk = new BOOLEAN[2 * n - 1];
  240.     mk = new BOOLEAN[n];
  241.     for(int i = 0; i < n; i++)
  242. queen[i] = -1;
  243. memset(rk, 0, (2*n-1)*sizeof(BOOLEAN));
  244. memset(lk, 0, (2*n-1)*sizeof(BOOLEAN));
  245. memset(mk, 0, n*sizeof(BOOLEAN));
  246. ResetEvent(pause_event);
  247.     Step(0);
  248. delete [] queen;
  249. delete [] rk;
  250. delete [] lk;
  251. delete [] mk;
  252. if(!canceling)
  253. {
  254. TCHAR msg[30];
  255. sprintf(msg, "找到%d种组合。", count);
  256. MessageBox(msg, "八皇后", MB_OK);
  257. }
  258. count = 0;
  259. canceling = running = FALSE;
  260. UpdateUI();
  261. }
  263. /**
  264. * 安排皇后的递归算法：   
  265. */
  267. void WINAPI CEightQueenDlg::Step(int i)
  268. {
  269.     for( int j = 0; j < n; j++ )
  270. {
  271. WaitForSingleObject(this_mutex, INFINITE);
  272. if(canceling)  return;
  273. ReleaseMutex(this_mutex);
  274. if( !mk[j] && !rk[i + j]  && !lk[n - 1 + i - j] )
  275. {
  276. queen[i] = j;
  277. rk[i + j] = TRUE;
  278. lk[n - 1 + i - j] = TRUE;
  279. mk[j] = TRUE;
  280. if( i == n - 1 )
  281. {
  282. count++;          
  283. UpdateQPanel(i, queen[i]);   
  284. WaitForSingleObject(this_mutex,INFINITE);
  285. if(!step&&!no_int)
  286. {
  287. ReleaseMutex(this_mutex);
  288. UpdateUI();
  289. DoPause();   
  290. }
  291. else
  292. {
  293. ReleaseMutex(this_mutex);
  294. }
  295. }
  296. else
  297. {
  298. UpdateQPanel(i, queen[i]);
  299. Step(i + 1);
  300. }
  301. queen[i] = -1;
  302. rk[i + j] = FALSE;
  303. lk[i + n - 1 - j] = FALSE;
  304. mk[j] = FALSE;
  305. UpdateQPanel(i, queen[i]);
  306. }
  307.     }
  308. }
  310. void CEightQueenDlg::OnPause() 
  311. {
  312. // TODO: Add your control notification handler code here
  313. WaitForSingleObject(this_mutex,INFINITE);
  314. step = TRUE;
  315. if(pausing)  SetEvent(pause_event);
  316. ReleaseMutex(this_mutex);    
  317. UpdateUI();
  318. }
  320. void CEightQueenDlg::OnContinue()
  321. {
  322. // TODO: Add your control notification handler code here
  323. WaitForSingleObject(this_mutex,INFINITE);
  324. step = FALSE;
  325. if(pausing)  SetEvent(pause_event);
  326. ReleaseMutex(this_mutex);
  327. UpdateUI();
  328. }
  330. void CEightQueenDlg::OnClose() 
  331. {
  332. // TODO: Add your message handler code here and/or call default
  333. if(running)
  334. this->MessageBox("正在运行，请先按“停止”按钮停止。", "警告");
  335. else  CDialog::EndDialog(0);
  336. }
  338. void CEightQueenDlg::OnStepBy() 
  339. {
  340. CButton *step = (CButton *)GetDlgItem(IDC_STEP_BY);
  341. m_step = (step->GetCheck()==BST_CHECKED)?TRUE:FALSE;
  342. if(m_step)
  343. {
  344. CButton *autoBtn = (CButton *)GetDlgItem(IDC_NO_INT);
  345. autoBtn->SetCheck(FALSE);
  346. m_no_int = FALSE;
  347. }
  348. }
  350. void CEightQueenDlg::UpdateUI()
  351. {
  352. WaitForSingleObject(this_mutex, INFINITE);
  353. GetDlgItem(IDC_BOARD_SIZE)->EnableWindow(!running&&!canceling);
  354. GetDlgItem(IDC_NO_INT)->EnableWindow(!running&&!canceling);
  355. GetDlgItem(IDC_STEP_BY)->EnableWindow(!running&&!canceling);
  356. GetDlgItem(IDC_START)->EnableWindow(!running&&!canceling);
  358. GetDlgItem(IDC_PAUSE)->EnableWindow(running&&!canceling);
  359. GetDlgItem(IDC_CONTINUE)->EnableWindow(running&&!canceling&&pausing);
  360. GetDlgItem(IDC_STOP)->EnableWindow(running&&!canceling);
  361. ReleaseMutex(this_mutex);
  362. }
  364. void CEightQueenDlg::OnAbout() 
  365. {
  366. // TODO: Add your control notification handler code here
  367. CAboutDlg dlgAbout;
  368. dlgAbout.DoModal();
  369. }
  371. void CEightQueenDlg::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 CEightQueenDlg::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 CEightQueenDlg::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 CEightQueenDlg::OnStop() 
  409. {
  410. // TODO: Add your control notification handler code here
  411. WaitForSingleObject(this_mutex, INFINITE);
  412. step = FALSE;
  413. canceling = TRUE;
  414. if(pausing)  SetEvent(pause_event);
  415. ReleaseMutex(this_mutex);
  416. UpdateUI();
  417. }
  419. void CEightQueenDlg::OnNoInt() 
  420. {
  421. // TODO: Add your control notification handler code here
  422. CButton *autoBtn = (CButton *)GetDlgItem(IDC_NO_INT);
  423. m_no_int = (autoBtn->GetCheck()==BST_CHECKED)?TRUE:FALSE;
  424. if( m_no_int )
  425. {
  426. CButton *step = (CButton *)GetDlgItem(IDC_STEP_BY);
  427. step->SetCheck(FALSE);
  428. m_step = FALSE;
  429. }
  430. }
  432. BOOL CAboutDlg::OnInitDialog() 
  433. {
  434. CDialog::OnInitDialog();
  436. // TODO: Add extra initialization here
  437. return TRUE;
  438. }