Click here to Skip to main content
15,885,278 members
Search within:


Articles / Desktop Programming / MFC
 

Solve the Pentomino puzzle with C++ and dancing links

Rate me:
Please Sign up or sign in to vote.
4.80/5 (22 votes)
2 Dec 2011CPOL11 min read 121.2K   3.1K   37  
Program to find all the solutions to a Pentomino puzzle.
 
// PuzzleSolverDlg.cpp : implementation file
//

#include "stdafx.h"
#include "PuzzleSolver.h"
#include "PuzzleSolverDlg.h"
#include "Globals.h"
#include <math.h>

#define MAXPROG 1000000

#ifdef _DEBUG
#define new DEBUG_NEW
#endif

HTREEITEM GetNextTreeItem(CTreeCtrl* m_tree, HTREEITEM hItem)
{
	if (m_tree->ItemHasChildren(hItem))
	{
		return m_tree->GetNextItem(hItem, TVGN_CHILD);
	}
	else if (m_tree->GetNextItem(hItem, TVGN_NEXT) != NULL)
	{
		// the next item at this level
		return m_tree->GetNextItem(hItem, TVGN_NEXT);
	}
	else
	{
		// return the next item after our parent
		hItem = m_tree->GetParentItem(hItem);
		if (hItem == NULL)
		{
			// no parent
			return NULL;
		}
		while (m_tree->GetNextItem(hItem, TVGN_NEXT) == NULL)
		{
			if (!hItem)
				return NULL;
			else
				hItem = m_tree->GetParentItem(hItem);
		}
		// next item that follows our parent
		return m_tree->GetNextItem(hItem, TVGN_NEXT);
	}
}
// CPuzzleSolverDlg dialog
CPuzzleSolverDlg::CPuzzleSolverDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CPuzzleSolverDlg::IDD, pParent)
{
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	
}

void CPuzzleSolverDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	DDX_Control(pDX, IDC_CBOPIEZA, CboPiezas);
	DDX_Control(pDX, IDC_IMAGEN, dibpieza);
	DDX_Control(pDX, IDC_PROBLEMA, dibtablero);
	DDX_Control(pDX, IDC_PROGRESO, prog);
	DDX_Control(pDX, IDC_PROCESAR, BtnProc);
	DDX_Control(pDX, IDCANCEL, BtnSalir);

	DDX_Control(pDX, IDC_SOLUCIONES, LstSoluciones);
	DDX_Control(pDX, IDC_MENSAJE, LblMensajes);
	DDX_Control(pDX, IDC_PROCESARDL, BtnProcDL);
	DDX_Control(pDX, IDC_CHKAVOID_TRIVIAL, ChkAvoidTrivial);
}

BEGIN_MESSAGE_MAP(CPuzzleSolverDlg, CDialog)
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_CBN_SELCHANGE(IDC_CBOPIEZA, OnCbnSelchange)
	//}}AFX_MSG_MAP
	ON_BN_CLICKED(IDC_PROCESAR, &CPuzzleSolverDlg::OnBnClickedProcesar)
	ON_NOTIFY(LVN_ITEMCHANGED, IDC_SOLUCIONES, &CPuzzleSolverDlg::OnLvnItemchangedSoluciones)
	ON_BN_CLICKED(IDC_PROCESARDL, &CPuzzleSolverDlg::OnBnClickedProcesardl)
END_MESSAGE_MAP()


// CPuzzleSolverDlg message handlers

BOOL CPuzzleSolverDlg::OnInitDialog()
{
	CDialog::OnInitDialog();
	IsProcessing = FALSE;
	ChkAvoidTrivial.SetCheck(TRUE);

	// 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

	// TODO: Add extra initialization here
	try
	{
		piezas.CargarPiezas(PathApplication + "Files\\Piezas.xml");
	}
	catch (...)
	{
		AfxMessageBox("Debe existir el archivo Piezas.xml en el directorio Files y su formato debe ser correcto");
		exit(0);
	}
	LoadCbo();
	dibtablero.Ancho = ANCHO;
	dibtablero.Alto = ALTO;
	dibtablero.piezas = &piezas;
	dibtablero.mappiezas = &(board.mappiezas);
	dibtablero.Invalidate();
	board.piezas = &piezas;
	prog.SetRange32(0, MAXPROG);
	OnCbnSelchange();
	
	FormatList();
	LoadConfig();

	return TRUE;  // return TRUE  unless you set the focus to a control
}
void CPuzzleSolverDlg::FormatList()
{
	LstSoluciones.InsertColumn(0, "Soluciones",0,360);
}
void CPuzzleSolverDlg::LoadCbo()
{
	CString cad;

	CPiezaInfo* piezainfo;
	CPieza* pieza;

	map<int, CPiezaInfo>::iterator itr;
	vector<CPieza>::iterator itr1;
	
	CString strinvertido;
	for(itr = piezas.piezasinfo.begin(); itr != piezas.piezasinfo.end(); ++itr)
	{
		piezainfo = &(*itr).second;
		for(itr1 = piezainfo->piezas.begin(); itr1 != piezainfo->piezas.end(); ++itr1)
		{
			pieza = &(*itr1);
			if (pieza->Invertido)
				strinvertido = "Invertido";
			else
				strinvertido = "";
			cad.Format("%s %d grados %s", piezainfo->Nombre, pieza->Angulo, strinvertido);
			CboPiezas.AddString(cad);
			int value = pieza->GetPiezaId();
			CboPiezas.SetItemData(CboPiezas.GetCount() - 1, value);
		}
	}
	CboPiezas.SetCurSel(0);
}
// 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 CPuzzleSolverDlg::OnPaint()
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, reinterpret_cast<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 function to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CPuzzleSolverDlg::OnQueryDragIcon()
{
	return static_cast<HCURSOR>(m_hIcon);
}
void CPuzzleSolverDlg::OnCbnSelchange()
{
	//int selec = CboType.GetItemData(CboType.GetCurSel());
	int data = CboPiezas.GetItemData(CboPiezas.GetCurSel());
	int idpiezainfo;
	piezas.GetIndexPieza(data, pieza, idpiezainfo);
	dibpieza.pieza = &pieza;
	dibpieza.CantPiezas = piezas.piezasinfo.size();
	dibpieza.idPInfo = idpiezainfo;
	dibpieza.Invalidate();
}

void CPuzzleSolverDlg::OnBnClickedProcesar()
{
	IsDancingLinks = FALSE;
	if (!IsProcessing)
	{
		FDesde = CTime::GetCurrentTime();
		IsProcessing = TRUE;
		ChangeToProcess(TRUE);

		Contador = 0;
		board.Ancho = ANCHO;
		board.Alto = ALTO;
		board.nodeseval = 0;
		
		dibtablero.nodos = &(board.nodos);
		dibtablero.ConComienzo = TRUE;

		SolvePuzzle();
		if (IsProcessing)
		{
			solman.ConComienzo = TRUE;
			solman.mappiezas = &(board.mappiezas);
			solman.piezas = board.piezas;
			solman.soluciones = &(this->soluciones);
			solman.LimpiarDuplicados();

			MostrarSoluciones();
			CString cad;
			cad.Format("Proceso terminado \n %d soluciones encontradas", soluciones.size());
			ChangeToProcess(FALSE);
			AfxMessageBox(cad);
			IsProcessing = FALSE;
		}
	}
	else
	{
		IsProcessing = FALSE;
		ChangeToProcess(FALSE);
		prog.SetPos(0);
		soluciones.clear();
		dibtablero.nodos = 0;
		dibtablero.Invalidate();
	}
	// TODO: Add your control notification handler code here
}
void CPuzzleSolverDlg::ChangeToProcess(BOOL process)
{
	if (process)
	{
		if (IsDancingLinks)
		{
			BtnProcDL.SetWindowTextA("Cancelar Proceso");
			BtnProc.ShowWindow(SW_HIDE);
		}	
		else
		{
			BtnProc.SetWindowTextA("Cancelar Proceso");
			BtnProcDL.ShowWindow(SW_HIDE);
		}
		BtnSalir.ShowWindow(SW_HIDE);
	}
	else
	{
		BtnProc.SetWindowTextA("Buscar Soluciones");
		BtnProcDL.SetWindowTextA("Buscar Soluciones Dancing Links");
		BtnProc.ShowWindow(SW_SHOW);
		BtnProcDL.ShowWindow(SW_SHOW);
		BtnSalir.ShowWindow(SW_SHOW);
	}
}
void CPuzzleSolverDlg::MostrarMensaje(int CantNodos)
{
	CString cad;
	//cad.Format("Profundidad = %d, Nodos = %d",rondas, CantNodos);
	GetDlgItem(IDC_MENSAJE)->SetWindowTextA(cad);
	DoEvents();
}
void CPuzzleSolverDlg::MostrarMensaje(CString strmensaje)
{
	GetDlgItem(IDC_MENSAJE)->SetWindowTextA(strmensaje);
	DoEvents();
}
void CPuzzleSolverDlg::MostrarSoluciones()
{
	int isol = 1;
	CString cad;
	LstSoluciones.SetRedraw(FALSE);
	for (auto itr=soluciones.begin(); itr != soluciones.end(); itr++)
	{
		cad.Format("Solucion Numero %04d", isol);
		LstSoluciones.InsertItem(isol - 1, cad);
		isol++;
	}
	LstSoluciones.SetRedraw(TRUE);
}
void CPuzzleSolverDlg::MostrarProgreso(CNodo* nodo)
{
	double max = pow((double)piezas.CantPiezas,(double)piezas.piezasinfo.size());
	double pos = GetValueNodo(nodo);
	int posctrl = ConvCoord(0, MAXPROG, 0, max,pos);
	prog.SetPos(posctrl);

	Contador++;
	if (Contador == 5000)
	{
		dibtablero.Invalidate();
		ActualizarMsg();
		Contador = 0;
		DoEvents();
	}
}
void CPuzzleSolverDlg::ActualizarMsg()
{
	CTime FHasta = CTime::GetCurrentTime();
	CTimeSpan duracion = FHasta - FDesde;
	CString strmsgtime, strmsgnodes, strspace, strsols;
	strmsgtime.Format("Tiempo transcurrido: %02d:%02d:%02d", duracion.GetHours(), duracion.GetMinutes(), duracion.GetSeconds());
	strmsgnodes = "Nodos procesados: " + FormatNum(board.nodeseval, 0);
	strsols = "Soluciones encontradas: " + FormatNum(soluciones.size(), 0);
	strspace = "       ";
	LblMensajes.SetWindowText(strmsgtime + strspace + strmsgnodes + strspace + strsols);
}
double CPuzzleSolverDlg::GetValueNodo(CNodo* nodo)
{
	double Sumador = 0;
	CNodo* partedato = nodo;
	
	int totpiezas = piezas.piezasinfo.size();
	for (int i=0; i<= board.inodo; i++)
	{
		partedato = &(board.nodos[i]);
		Sumador+=(double)(partedato->Index-1) * pow((double)piezas.CantPiezas, (double)(totpiezas - i - 1));
	}
	return Sumador;
}

void CPuzzleSolverDlg::OnLvnItemchangedSoluciones(NMHDR *pNMHDR, LRESULT *pResult)
{
	LPNMLISTVIEW pNMLV = reinterpret_cast<LPNMLISTVIEW>(pNMHDR);
	// TODO: Add your control notification handler code here
	*pResult = 0;

	dibtablero.nodos = &(soluciones[pNMLV->iItem]);
	dibtablero.Invalidate();
}
void CPuzzleSolverDlg::LoadConfig()
{
	if (::GetLocaleInfo(LOCALE_USER_DEFAULT, LOCALE_SDECIMAL, NULL, 0))
		::GetLocaleInfo(LOCALE_USER_DEFAULT, LOCALE_SDECIMAL, &DecimalSep, sizeof(DecimalSep));
	
	// Get the system's group separator
	if (::GetLocaleInfo(LOCALE_USER_DEFAULT, LOCALE_STHOUSAND, NULL, 0))
		::GetLocaleInfo(LOCALE_USER_DEFAULT, LOCALE_STHOUSAND, &ThousandSep, sizeof(ThousandSep));
}
CString CPuzzleSolverDlg::FormatNum(double num, int decimals)
{
	CString Cad;
	CString strformat, strdec;
	BOOL EsNeg = FALSE;
	if (num < 0)
	{
		num *= -1;
		EsNeg = TRUE;
	}
	strdec.Format("%d", decimals);
	strformat = "%." + strdec + "f";
	Cad.Format(strformat, num);
	Cad.Replace('.', DecimalSep);
	
	int intlen = Cad.GetLength() - decimals;
	int idecimals = ((intlen-1)/3);

	for (int i=1;i<=idecimals;i++)
		Cad.Insert(intlen - i*3,ThousandSep);
	if (EsNeg)
		Cad = "-" + Cad;
	return Cad;
}

void CPuzzleSolverDlg::OnBnClickedProcesardl()
{
	IsDancingLinks = TRUE;
	if (!IsProcessing)
	{
		Contador = 0;
		soluciones.clear();
		FDesde = CTime::GetCurrentTime();
		IsProcessing = TRUE;
		ChangeToProcess(TRUE);
	
		dibtablero.mappiezas = &dlsolver.mappiezas;
		dibtablero.ConComienzo = FALSE;

		dlsolver.solver.msg = this;
		dlsolver.Init(10, 6, ChkAvoidTrivial.GetCheck() == 1, &piezas);
		dlsolver.solver.Solve();
		if (IsProcessing)
		{
			if (ChkAvoidTrivial.GetCheck() == 0)
			{
				dibtablero.nodos = 0;

				board.InitPiezasDisp();
				solman.ConComienzo = FALSE;
				solman.mappiezas = &(board.mappiezas);
				solman.piezas = board.piezas;
				solman.soluciones = &(this->soluciones);
				solman.LimpiarDuplicados();
			}
		
			MostrarSoluciones();
			ChangeToProcess(FALSE);
			IsProcessing = FALSE;

			CString cad;
	
			cad.Format("Proceso terminado \n %d soluciones encontradas", soluciones.size());
			ChangeToProcess(FALSE);
			AfxMessageBox(cad);
			IsProcessing = FALSE;
		}
	}
	else
	{
		IsProcessing = FALSE;
		dlsolver.solver.finished = TRUE;
		ChangeToProcess(FALSE);
		prog.SetPos(0);
		soluciones.clear();
		dibtablero.nodos = 0;
		dibtablero.Invalidate();
	}
	// TODO: Add your control notification handler code here
}
void CPuzzleSolverDlg::ShowMsg(int nodes, int sols)
{
	if (!IsProcessing) return;

	Contador++;
	if (Contador != 10000) return;
	
	Contador = 0;

	CTime FHasta = CTime::GetCurrentTime();
	CTimeSpan duracion = FHasta - FDesde;
	CString strmsgtime, strmsgnodes, strspace, strsols;
	strmsgtime.Format("Tiempo transcurrido: %02d:%02d:%02d", duracion.GetHours(), duracion.GetMinutes(), duracion.GetSeconds());
	strmsgnodes = "Nodos procesados: " + FormatNum(dlsolver.solver.nodes, 0);
	strsols = "Soluciones encontradas: " + FormatNum(dlsolver.solver.solutions.size(), 0);
	strspace = "       ";
	LblMensajes.SetWindowText(strmsgtime + strspace + strmsgnodes + strspace + strsols);

	DoEvents();
	
}
void CPuzzleSolverDlg::FoundSol(void* sol)
{
	if (!IsProcessing) return;

	tsolution* soldlink = (tsolution*)sol;
	CNodo nodosol;
	CNode* node;
	nodeitem* nitem;
	vecnodos solarr;

	solarr.clear();
	for (auto itr1 = soldlink->begin(); itr1 != soldlink->end(); itr1++)
	{
		node = (*itr1);
		nitem = (nodeitem*)node->nodedata;
			
		nodosol.Columna = nitem->col;
		nodosol.Fila = nitem->row;
		nodosol.IdPieza = nitem->idpieza;

		solarr.push_back(nodosol);
	}
	soluciones.push_back(solarr);
	dibtablero.nodos = &(soluciones.at(soluciones.size() - 1));
	dibtablero.Invalidate();
}
void CPuzzleSolverDlg::ShowProgress(int mincollen, int colprg)
{
	if (!IsProcessing) return;

	int nLower, nUpper;
	prog.GetRange(nLower, nUpper);
	if (nUpper != mincollen)
		prog.SetRange(0, mincollen);

	prog.SetPos(colprg);
	prog.Invalidate();

}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
ErnestoNet
Software Developer
Argentina Argentina
System developer from Argentina.

Programmed in VB 5,6,.NET, C#, Java, PL-SQL, Transac-SQL, C, C++ and even some "calculator" language.

Love to build small, useful applications.
Usually building big and complicated apps based on solid, reliable components.

Hobbies: reading, photography, chess, paddle, running.

Comments and Discussions

Permalink
Advertise
Privacy
Cookies
Terms of Use
Layout: fixed | fluid

Posted 20 Oct 2011

Article Copyright 2011 by ErnestoNet
Everything else Copyright © CodeProject, 1999-2024

Web02 2.8:2024-04-02:1