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 <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,5,3,0,0,0,0,0}, {8,0,0,0,0,0,0,2,0}, {0,7,0,0,1,0,5,0,0}, {4,0,0,0,0,5,3,0,0}, {0,1,0,0,7,0,0,0,6}, {0,0,3,2,0,0,0,8,0}, {0,6,0,5,0,0,0,0,9}, {0,0,4,0,0,0,0,3,0}, {0,0,0,0,0,9,7,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; }
Private
[
?
]
Run code
Submit