[ create a new paste ] login | about

Link: http://codepad.org/QlDAfnjE    [ raw code | output | fork ]

C++, pasted on Sep 13:
#include <iostream>
#include <vector>
#include <list>
using namespace std;
typedef vector<vector<int> > STATUS;
typedef list<STATUS*> FRINGE;
typedef void (FRINGE::*COMBINER)(FRINGE::const_reference);
void report(STATUS* s)
{
	for (int i=0; i<9; ++i) {
		for (int j=0; j<9; ++j) cout<<(*s)[i][j];
		cout<<endl;
	}
	cout<<endl;
}
bool goal(STATUS* s)
{
	for (int i=0; i<9; ++i) {
		for (int j=0; j<9; ++j) if ((*s)[i][j]==0) return false;
	}
	return true;
}
void findCandidates(STATUS* s, int i, int j, bool* candidates)
{
	for (int n=1; n<=9; ++n) *(candidates+n)=true;
	for (int k=0; k<9; ++k) {
		*(candidates+(*s)[i][k])=false;
		*(candidates+(*s)[k][j])=false;
	}
	for (int r=0; r<3; ++r) {
		for (int c=0; c<3; ++c) *(candidates+(*s)[3*(i/3)+r][3*(j/3)+c])=false;
	}
}
void expand(FRINGE* fringe, STATUS* s, COMBINER combiner)
{
	int i=0, j=0;
	for (i=0; i<9; ++i) {
		for (j=0; j<9; ++j) if ((*s)[i][j]==0) goto FOUND;
	}
FOUND:
	bool candidates[10];
	findCandidates(s, i, j, candidates);
	for (int n=1; n<=9; ++n) {
		if (candidates[n]) {
			STATUS* newSTATUS=new STATUS(*s);
			(*newSTATUS)[i][j]=n;
			(fringe->*combiner)(newSTATUS);
		}
	}
}
void search(FRINGE* fringe, COMBINER combiner, bool findAll)
{
	if (fringe->size()!=0) {
		STATUS* s=fringe->front();
		fringe->pop_front();
		if (goal(s)) {
			report(s);
			if (!findAll) fringe->clear();
		}
		else expand(fringe, s, combiner);
		delete s;
		search(fringe, combiner, findAll);
	}
}
int main ()
{
	int problem[][9]={
		{0, 0, 7, 9, 0, 0, 0, 0, 0},
		{0, 3, 0, 0, 0, 0, 4, 0, 0},
		{9, 0, 0, 0, 0, 5, 0, 6, 0},
		{0, 8, 0, 0, 0, 2, 3, 0, 0},
		{6, 0, 0, 0, 7, 0, 0, 1, 0},
		{0, 0, 3, 5, 0, 0, 0, 0, 4},
		{0, 0, 5, 0, 1, 0, 0, 7, 0},
		{0, 2, 0, 0, 0, 0, 0, 0, 8},
		{0, 0, 0, 0, 0, 3, 5, 0, 0}};
	STATUS* s=new STATUS(9);
	for (int i=0; i<9; ++i) {
		(*s)[i].resize(9);
		for (int j=0; j<9; ++j) (*s)[i][j]=problem[i][j];
	}
	FRINGE fringe;
	fringe.push_back(s);
	search(&fringe, &FRINGE::push_front, false); //depth-first search
	//search(&fringe, &FRINGE::push_back, false); //breadth-first search
	return 0;
}


Output:
1
Timeout


Create a new paste based on this one


Comments: