codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <iostream> #include <list> #define N 9 #define B 3//square root of N using namespace std; typedef int STATUS; typedef list<STATUS*> FRINGE; typedef void (FRINGE::*COMBINER)(FRINGE::const_reference); void report(STATUS* s) { for (int i=0; i<N*N; ++i) { cout<<s[i]; if (i%N==N-1) cout<<endl; } cout<<endl; } bool goal(STATUS* s) { for (int i=0; i<N*N; ++i) { if (s[i]==0) return false; } return true; } bool canBePlaced(STATUS* s, int pos, int x) { int row=pos/N; int col=pos%N; int i, j, topLeft; for (i=0; i<N; ++i) { if (s[row*N+i]==x) return false; if (s[col+i*N]==x) return false; } topLeft=N*(row/B)*B+(col/B)*B; for (i=0; i<B; ++i) { for (j=0; j<B; ++j) { if (s[topLeft+i*N+j]==x) return false; } } return true; } void expand(FRINGE* fringe, STATUS* s, COMBINER combiner) { int pos; for (pos=0; pos<N*N; ++pos) { if (s[pos]==0) break; } for (int x=1; x<=N; ++x) { if (canBePlaced(s, pos, x)) { STATUS* newStatus=new STATUS[N*N]; for (int i=0; i<N*N; ++i) newStatus[i]=s[i]; newStatus[pos]=x; (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) { while (!fringe->empty()) { STATUS* tmp=fringe->front(); fringe->pop_front(); delete tmp; } } } else expand(fringe, s, combiner); delete s; search(fringe, combiner, findAll); } } int main () { int problem[]={ 1,0,0,0,0,7,0,9,0, 0,3,0,0,2,0,0,0,8, 0,0,9,6,0,0,5,0,0, 0,0,5,3,0,0,9,0,0, 0,1,0,0,8,0,0,0,2, 6,0,0,0,0,4,0,0,0, 3,0,0,0,0,0,0,1,0, 0,4,0,0,0,0,0,0,7, 0,0,7,0,0,0,3,0,0}; STATUS* s=new STATUS[N*N]; for (int i=0; i<N*N; ++i) s[i]=problem[i]; FRINGE* fringeP=new FRINGE(); fringeP->push_back(s); //search(fringeP, &FRINGE::push_front, true); //depth-first search search(fringeP, &FRINGE::push_back, true); //breadth-first search return 0; }
Private
[
?
]
Run code
Submit