April 28th, 2006, 04:08 PM
|
|
Registered User
|
|
Join Date: Apr 2006
Posts: 2
Time spent in forums: 19 m 32 sec
Reputation Power: 0
|
|
|
SuDoKu Backtracking program
I need to write a c++ SuDoKu solver using backtracking. I am using a Vector-Vector-Deque where the Vector-Vector is the coordinate system for the puzzle and the Deque is the available numbers for each cell. I distinguish the constant numbers as a negative number(yes, i use abs() when i actually use them). Through thorough testing I'm near positive my functions to check if the number conflicts are all working perfectly. The backtracking function seems perfect, and I am just starting to wonder if, for some reason, it just takes forever to complete. Using the provided puzzle, it took about 15 minutes before it back tracked to the original cell and it popped the 1 to increse up to 2. Anyway, here is the code:
main.cpp:
Code:
#include <iostream>
#include "SuDoKu.h"
using namespace std;
int main(){
string PuzzleName;
cout << "Which puzzle would you like to load?" << endl;
cin >> PuzzleName;
SuDoKu puzzle;
if(!puzzle.Solve(PuzzleName)){
cout << "The puzzle is not solvable" << endl;
}
return 0;
}
SuDoKu.h:
Code:
#ifndef SUDOKU
#define SUDOKU
#include <fstream>
#include <iostream>
#include <vector>
#include <deque>
#include <string>
using namespace std;
class SuDoKu {
public:
SuDoKu();//Default Constructor
bool CheckRow(int R, int Val, vector<vector<deque<int > > > Puzzle);
bool CheckCol(int C, int Val, vector<vector<deque<int > > > Puzzle);
bool CheckSquare(int R, int C, int Val, vector<vector<deque<int > > > Puzzle);
bool CheckAll(int R, int C, int Val, vector<vector<deque<int > > > Puzzle);
bool Solve(string PuzzleName);
};
#endif
SuDoKu.cpp:
Code:
#include <fstream>
#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include "SuDoKu.h"
using namespace std;
SuDoKu::SuDoKu(){
//nothing for default constructor to do
}
bool SuDoKu::CheckAll(int R, int C, int Val, vector<vector<deque<int > > > Puzzle){
//debug msg
cout << "Row: " << R << ", Col: " << C << ", Val: " << Val << endl;
if(CheckCol(C, Val, Puzzle) && CheckRow(R, Val, Puzzle) && CheckSquare(R, C, Val, Puzzle)){
return true;
}
else{
return false;
}
}
bool SuDoKu::CheckCol(int C, int Val, vector<vector<deque<int > > > Puzzle){
int x = 0;//counter
int conflicts = 0;
for(x = 0; x < 9; x++){
if(abs(Puzzle[x][C].front()) == Val){
conflicts++;
}
}
if(conflicts == 1){
//debug msg
cout << "Col is OK" << endl;
return true;
}
else if(conflicts > 1){
//debug msg
cout << "Col is not OK" << endl;
return false;
}
}
bool SuDoKu::CheckRow(int R, int Val, vector<vector<deque<int > > > Puzzle){
int x = 0;//counter
int conflicts = 0;
for(x = 0; x < 9; x++){
if(Puzzle[R][x].front() < 0){
if(int((Puzzle[R][x].front()))*(-1) == Val){
conflicts++;
}
}
if(Puzzle[R][x].front() == Val){
conflicts++;
}
}
if(conflicts == 1){
//debug msg
cout << "Row is OK" << endl;
return true;
}
else{
//debug msg
cout << "Row is not OK" << endl;
return false;
}
}
bool SuDoKu::CheckSquare(int R, int C, int Val, vector<vector<deque<int > > > Puzzle){
int squareC = 0;//sub-grib col
int squareR = 0;//sub-grid row
int x = 0;//counter
int y = 0;//counter
int conflicts = 0;
//which sub-grid row is the space in
if(R < 3){
squareR = 0;
}
else if(R > 2 && R < 6){
squareR = 1;
}
else if(R > 5 && R < 9){
squareR = 2;
}
//which sub-grid col is the space in
if(C < 3){
squareC = 0;
}
else if(C > 2 && C < 6){
squareC = 1;
}
else if(C > 5 && C < 9){
squareC = 2;
}
//actually check the grid now
for(x = (squareR*3); x < (squareR*3 + 3); x++){
for(y = (squareC*3); y < (squareC*3 + 3); y++){
if(Puzzle[x][y].front() < 0){
if(int((Puzzle[x][y].front()))*(-1) == Val){//****need int? here and above********************************************* *********************
conflicts++;
}
}
if(Puzzle[x][y].front() == Val){
conflicts++;
}
}
}
if(conflicts == 1){
//debug msg
cout << "Square is OK" << endl;
return true;
}
else{
//debug msg
cout << "Square is not OK" << endl;
return false;
}
}
bool SuDoKu::Solve(string PuzzleName){
int a = 0;//counter
int b = 0;//counter
int num = 0;//input number
vector<vector<deque<int > > > Puzzle(9, vector<deque<int > >(9, deque<int>(0)));
ifstream fin;
fin.open(PuzzleName.c_str());
cout << "The puzzle loaded is: " << endl;
for(a = 0; a < 9; a++){
if(a == 3 || a == 6){
cout << endl;
}
for(b = 0; b < 9; b++){
fin >> num;
if(num == 0){
for(num = 0; num < 10; num++){
Puzzle[a][b].push_back(num);
}
cout << Puzzle[a][b].front() << " ";
}
else{
Puzzle[a][b].push_back(-1*num);
cout << -1*(Puzzle[a][b].front()) << " ";
}
if(b == 2 || b == 5){
cout << " ";
}
}
cout << endl;
}
cout << endl;
fin.close();
//Puzzle is now loaded, will begin solving:
a = 0;//row counter
b = 0;//col counter
num = 0;//counter for refilling in backtracking
while(!(a == 9 && b == 0)){
if(Puzzle[a][b].front() == 0){
Puzzle[a][b].pop_front();
}
if(Puzzle[0][0].front() == 2){
cout << "poop" << endl;
}
//begin
//for debugging purposes, displays the puzzle as it is currently. stop at end of big while to see other debug msgs
cout << endl << "currently..." << endl << endl;
for(int r = 0; r < 9; r++){
if(r == 3 || r == 6){
cout << endl;
}
for(int d = 0; d < 9; d++){
if(Puzzle[r][d].front() < 0){
cout << Puzzle[r][d].front()*-1 << " ";
}
else{
cout << Puzzle[r][d].front() << " ";
}
if(d == 2 || d == 5){
cout << " ";
}
}
cout << endl;
}
//end
if(Puzzle[a][b].front() < 0){//this is not a changeable space
//debug msg
cout << "Not a changeable space..." << endl;
if(b < 8){
b++;
}
else{
b = 0;
a++;
}
}
else{
if(CheckAll(a, b, Puzzle[a][b].front(), Puzzle)){
if(b < 8){
b++;
}
else{
b = 0;
a++;
}
}
else{
if(Puzzle[a][b].size() == 1){
Puzzle[a][b].pop_front();
for(num = 0; num < 10; num++){
Puzzle[a][b].push_back(num);
}
//debug msg
cout << "At Row " << a << " and Col " << b << " the numbers were pushed on" << endl;
if(a == 0 && b == 0){
return false;
}
else if(b == 0){
a--;
b = 8;
}
else{
b--;
}
while(Puzzle[a][b].size() == 1){//need a check for the const or single
if(Puzzle[a][b].front() < 0){
if(b == 0){
a--;
b = 8;
}
else{
b--;
}
}
else{
Puzzle[a][b].pop_front();
for(num = 0; num < 10; num++){
Puzzle[a][b].push_back(num);
}
//debug msg
cout << "At Row " << a << " and Col " << b << " the numbers were pushed on" << endl;
if(b == 0){
a--;
b = 8;
}
else{
b--;
}
}
}
Puzzle[a][b].pop_front();
}
else{
Puzzle[a][b].pop_front();
}
}
}
}//stop here if debuging
cout << "The solved puzzle is: " << endl;
//solved so display
for(a = 0; a < 9; a++){
if(a == 3 || a == 6){
cout << endl;
}
for(b = 0; b < 9; b++){
if(Puzzle[a][b].front() < 0){
cout << abs(Puzzle[a][b].front()) << " ";
}
else{
cout << Puzzle[a][b].front() << " ";
}
if(b == 2 || b == 5){
cout << " ";
}
}
cout << endl;
}
return true;
}
Included puzzle:
Code:
0 0 0 0 8 6 0 9 0
7 0 0 0 0 0 3 0 2
0 0 0 0 0 0 0 1 0
0 8 1 2 0 0 0 0 0
0 0 0 5 0 0 6 0 7
0 3 0 0 0 0 0 0 4
0 0 0 0 9 0 0 0 0
0 6 0 0 0 2 0 0 1
0 0 0 7 4 0 0 0 0
I left all the debuging cout's in. There is a spot marked in the solving section that I reccomend a stop to be placed if you wanna look how it executes.
Its due at midnight so hopefully I get it done and can move on to more pressing final projects and studying. For now, I'm going to let it run a while since about 30 minutes have passed now and the original cell is still 2.
|
Dev Articles Community Forums Sponsor:
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
