C++

Forum

 
Question about backtracking issue

rva03 (3)
Hello, i'm writing a backtracking program. The program ask the user for a height and width of the field and how long the placed stones are. Then the program must calculate how many different completely filled fields with these stones there are possible.

For example a 2 by 6 field and a stonelength of 2 gives 13 possible filled fields.

My program can calculate this example correct, but with a higher amount of possible fields it seems it counts some of the possible fields double. Because a 3 by 6 field with a stonelength of 2 should give 41 possible fields and my program calculates a possible 96 fields.

This isn't working properly, but I can't find the part where it goes wrong.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 

#include <iostream>
#include <ostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include "schaakbord.h"

using namespace std;

schaakbord schaak;

int main(){
	cout<<"wat is de m?"<< endl;
	cin>> schaak.m;
	if(schaak.m>schaak.mmax|| schaak.m<=0){
		cout<< "deze waarde mag niet"<<endl;
	}
	cout<<"wat is de n?"<<endl;
	cin>> schaak.n;
	if(schaak.n>schaak.nmax || schaak.n<=0){
		cout<< "deze waarde mag niet"<<endl;
	}
	cout<<"wat is de s?"<<endl;
	cin>> schaak.s;
	if(schaak.s>schaak.smax|| schaak.s<=0){
		cout<< "deze waarde mag niet"<<endl;
	}
	if((schaak.m*schaak.n)%schaak.s==0){
    	schaak.print();
   		schaak.menu();
	}
	else{
		return 0;
	}
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
#include <iostream>
#include <ostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include "schaakbord.h"

using namespace std;

schaakbord::schaakbord(){

}

void schaakbord::print(){
    for(int i=0; i<m; i++){
       	for(int j=0; j<n; j++){
			if(A[i][j]==true){
				cout << "x ";
			}
			else{
				cout << "0 ";
			}
		}//for
		cout << endl;
  	}//for
	cout << endl;
}
bool schaakbord::eindstand(){
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(A[i][j]==false){
				return false;
			}
		}
	}
	return true;
}

void schaakbord::beginstand(){
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(A[i][j]==false){
				y = i;
				x = j;
				return;
			}
		}
	}
}

void schaakbord::doezet(bool hor){
	for(int i=0; i<s; i++){
		if(!hor){
			A[y+i][x]=true;
		}
		else{
			A[y][x+i]=true;
		}
	}
}

void schaakbord::ontdoezet(bool hor){
	for(int i=0; i<s; i++){
		if(!hor){
			A[y+i][x]=false;
		}
		else{
			A[y][x+i]=false;
		}
	}
}

void schaakbord::optie1(){
   kanzet = true;
	int Xres, Yres;
	if ( eindstand() == true){ // het bord is vol
		teller++;
		cout << teller << " ---------------------------- " << endl;
		}
	else {
		beginstand();
	// directe vervolgstanden aflopen
      for(int i=0; i<s-1;i++){
            if(A[y][x+i] == true){
               kanzet = false;
            }
      }
		if (((x + s) <= n) && (kanzet = true)){
			Xres = x;
			Yres = y;
         doezet(true);
			print();
			optie1();
			x = Xres;
			y = Yres;
			ontdoezet(true);
		}
		if ( ((y+s )<= m) && (s != 1)){ 
			Xres = x;
			Yres = y;
			doezet(false);
			print();
			optie1();
			x = Xres;
			y = Yres;
			ontdoezet(false);
		}

	}
}

void schaakbord::menu(){
   char actie = 'Y';
   while (actie != 'Q') {
      cout << "optie 1, 2, 3" << endl;
      cin >> actie;
      switch(actie) {
         case '1':
            optie1();
         break;
      }//switch
      switch(actie) {
         case '2':
            cout << "U heeft zojuist een random veld gekregen!" << endl;
         break;
      }//switch
      switch(actie) {
         case '3':
            cout << "U heeft zojuist een random veld gekregen!" << endl;
         break;
      }//switch
   }//while

}


Maybe someone here who knows where it goes wrong?
I also have a header file:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
//schaakbord.h

class schaakbord {

	public:
		int m, n, s, x, y, teller, hori, horimax;
		int A[100][100];
  		static const int mmax = 10;
                static const int nmax = 10;
		static const int smax = 4;

		schaakbord();
		char actie;
		void menu();//maakt een menu aan
                void print();
		void optie1();
		void optie2();
		void beginstand();
		bool eindstand();
		bool kanzet;
		void doezet(bool hor);
		void ontdoezet(bool hor);

};
Last edited on
ne555 (10692)
The code that you've posted does not compile
extra } in line 116
`optie1()' was not declared as a non-member function


Also putting a //classes.h comment in the `schaakbord.h' file is confusing
Last edited on
rva03 (3)
Sorry, that was my old code which didn't compile as you said.

So now I posted my new code which does compile and where it doesn't calculate right with the larger fields.

ne555 (10692)
/tmp/cc6uhkMp.o: In function `schaakbord::menu()':
foo.cpp:181: undefined reference to `schaakbord::optie2()'
collect2: error: ld returned 1 exit status



Look at line 88 if (((x + s) <= n) && (kanzet = true)){ you've got assignment there.
Comparing a boolean variable seems like a conceptual error, you should do simply if( foo ) or if( not foo )
Last edited on
rva03 (3)
Ok, I changed the thing you said to if (((x + s) <= n) && (kanzet)){

But that doesn't change anything to the output of the program.
Topic archived. No new replies allowed.