C++

Forum

 
Sudoku Solver Inference Rules debugging

wtf (670)
please look at my code and help me to see what is going wrong. gridcomopletion() had seemed to work, but at closer inspection, it is not correctly elimininating the possibilities from a square when it makes a deduction.

also rowscompletion() and rowselimination() do not work, as far as I can tell.

Also I would like to have a display function that will allow for 2x2, 3x3, and 4x4 minigrids (so 4x4, 9x9, and 16x16 gameboards respectively), but in a 16x16 gameboard that allows for 2 digit numbers, i am having trouble formatting the results correctly to allow for the additional space if needed, but also to fit the double thick bars in the correct spots. Any helps would be appreciated thanks. 
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
 
void sudoku:: gridcompletion()
{
    for (int rgrids = 0; rgrids < size; ++rgrids)
        {
            for (int cgrids = 0; cgrids < size; ++cgrids)
                {
                    for (int nums = 1; nums <=SIZE; ++nums)
                        {
                            int solor, soloc;
                            bool solo = false; bool second = false;
                            for (int rows = 0; rows < size; ++rows)
                                {
                                    for (int cols = 0; cols < size; ++cols)
                                        {
                                            if (possibilities[size*rgrids+rows][size*cgrids+cols].containsN(nums))
                                                {
                                                    if (solo == true)
                                                        {
                                                            second = true;
                                                        }
                                                    else
                                                        {
                                                            solo = true; second = false;
                                                            solor = rows;
                                                            soloc = cols;
                                                        }
                                                }
                                        }
                                    /*if ( (solo == true) && (second == false) )
                                        {
                                            SU[size*rgrids + solor][size *cgrids + soloc] = nums;
                                            //eliminate possibilities;
                                            for (int k = 1; k < 10; ++k)
                                                {
                                                    possibilities[size*rgrids + solor][size *cgrids + soloc].removeN(k);
                                                }
                                                    possibilities[size*rgrids + solor][size *cgrids + soloc].addN(nums);
                                        }*/
                                }       //maybe if (( solo == true )) yada yada goes here



                            if ( (solo == true) && (second == false) )
                                {
                                    SU[size*rgrids + solor][size *cgrids + soloc] = nums;
                                    //deduce(nums,size*rgrids + solor,size *cgrids + soloc);
                                    //eliminate possibilities;
                                    int kk;
                                    for (int k = 1; k < 10; ++k)
                                        {/*if (k == 9)
                                                {
                                                    if ((size*rgrids + solor) == 0)
                                                        if ((size * cgrids + soloc) == 0)

                                                    cout << "zzz" << endl;
                                                    ;
                                                }
                                                */
                                                //debugging
                                            //possibilities[size*rgrids + solor][size *cgrids + soloc].removeN(k);
                                            kk = k;
                                            cout << "ok1" << endl;
                                            cout << "size = " << size << " rgrids = " << rgrids << " solor = " << solor << " " << endl;
                                            int tr = size%rgrids+solor; int tc = size*cgrids+soloc;
                                            cout << "ok2" << endl;
                                            cout << "tr = " << tr << " tc = " << tc << " k = " << k << " " << endl;
                                            eliminatepossibilities(tr,tc, k);
                                            cout << "ok" << endl;

                                        }
                                    possibilities[size*rgrids + solor][size *cgrids + soloc].addN(nums);
                                    //debugging

                                }



                        }
                }
        }
}
wtf (670)
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
 
void sudoku::eliminatepossibilities(const int & r, const int & c, const int & n)
{
    if ( (r == 0) && (c == 2) )
        {
            //cout << " amazing n = " << n << " " << endl;
        }

    for (int i = 0; i < SIZE; ++i)
        {
            //if ( ( r == 0) && (i == 2) )
            //    cout << "n = " << n << " " << endl;
            //if ( ( c == 2) && ( i == 0) )
            //    cout << "but n = " << n << " " << endl;
            possibilities[r][i].removeN(n);
            possibilities[i][c].removeN(n);
        }
    for (int k = 1; k <= SIZE; ++k)
        {
            //if ( (r == 0) && (n == 2) )
            //    cout << "and k = " << k << " " << endl;
            if (n!=0)
                possibilities[r][c].removeN(k);
        }

            //possibilities[r][c].addN(n);

    //grids:
   //
   int g = getgrid(r,c);
    int pivotr = r / size;
    int pivotc = c / size;

    for (int row = pivotr; row < pivotr + size; ++row)
        {
            for (int col = pivotc; col < pivotc + size; ++col)
                {
                    if ( (row == 0) && (col == 2) )
                        //cout << "jesus n = " << n << " " << endl;//debugging
                        ;
                    //possibilities[row][col].removeN(n);
                }
        }


    possibilities[r][c].addN(n); //



}


void sudoku:: deduce(const int & n, const int & r, const int & c)
{
    if (n == 3)
        if (r == 1)
            if (c == 6)
                cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"<<endl;
    if (!contradiction(n, r, c) )
        {
            if ( ( (r == 1) && (c == 6) ) && ( n == 3) )
                {
                    cout << "ok folks !!! " << endl;
                    possibilities[r][c].display();
                    SU[r][c] = n;
                    eliminatepossibilities(r, c, n);
                    possibilities[r][c].display();
                }
            else
            {
            SU[r][c] = n;
            //listcheck();
            eliminatepossibilities(r, c, n);
            }
        }
    return;
}
wtf (670)
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
 
const void sudoku::display()
{
    char block = -70;
    char block2 = -78;
    cout << endl << endl << " ";
    for (int k = 0; k < (SIZE*3 +SIZE + 2); ++k)
        {
            if (k % ( (size+1)*3 ) == 0)
                {
                    if (k != 0)
                    cout << block2;
                }
                else
            cout << block2;
        }

    cout << endl;
    for (int i = 0; i < SIZE; ++i)
        {
            cout << " " << block2;
            for (int j = 0; j < SIZE; ++j)
                {
                    if (j % size == size-1)
                        {
                            if (SU[i][j] == 0)
                                cout << "  " << " " << block2;
                            else cout << " " << SU[i][j] << " " << block2;
                        }
                    else if (SU[i][j] == 0)
                        cout << " " << " " << " |";
                        else cout << " " << SU[i][j] << " |"; //testing
                }
            cout << endl;
            cout << " ";
            if (i % size == size-1)
                {
                        {
                            for (int k = 3; k <= 3*SIZE + SIZE+3; ++k)
                                cout << block2;
                        }
                }
            else    for (int k = 0; k < (3*SIZE + SIZE); ++k)
                        {
                            if (k == 0)
                                cout << block2 ;

                            else if (k % ( (size+1)*3 ) == 0)
                                {

                                    cout << block2;//debugging
                                    ;
                                }
                            else cout << "-";
                            if (k == (3*SIZE + SIZE) - 1) cout << block2;

                        }

            cout << endl;
        }
    return;
}
wtf (670)
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
 
inline int sudoku::firstrowofgrid(const int & g)
{
    for (int x = 0; x < SIZE; ++x)
        {
            for (int y = 0; y < SIZE; ++y)
                {
                    if (getgrid(x,y) == g)
                        return x;
                }
        }
    return -1;
}

inline int sudoku::firstcolofgrid(const int & g)
{
    for (int x = 0; x < SIZE; ++x)
        {
            for (int y = 0; y < SIZE; ++y)
                {
                    if (getgrid(x,y) == g)
                        return x;
                }
        }
    return -1;
}

bool sudoku:: rowselimination()
{
    bool didIdoanything = false;
    for (int grids = 1; grids <= SIZE; ++grids)
        {
            int firstrow = firstrowofgrid(grids); int firstcol = firstcolofgrid(grids);
            for (int nums = 1; nums <= SIZE; ++nums)
                {
                    int temp;
                    bool singlepossiblerowingrid = true;
                    int pr[size];
                    for (int a = 0; a < size; ++a)
                        {
                            pr[a] = -1;
                        }
                    for (int rows = firstrow, i = 0; rows < (firstrow + size); ++i, ++rows)
                        {
                            for (int cols = firstcol; cols < (firstcol + size); ++cols)
                                {
                                    if (possibilities[rows][cols].containsN(nums))
                                        {
                                            pr[i] = rows;
                                        }
                                }
                        }
                    for (int x = 0; x < size; ++x)
                        {
                            if (pr[x] != -1)
                                temp = pr[x];
                        }
                    for (int x = 0; x < size; ++x)
                        {
                            if (! ((pr[x] == -1) || (pr[x] == temp) ) )
                                singlepossiblerowingrid = false;
                        }
                    if (singlepossiblerowingrid == true)
                        {
                            for (int y = 0; y < SIZE; ++y)
                                {
                                    if (getgrid(temp, y) != grids)
                                        {
                                            if (possibilities[temp][y].containsN(nums))
                                                {
                                                    possibilities[temp][y].removeN(nums);
                                                    didIdoanything = true;
                                                    //debugging
                                                    //cout << "and fyi temp = " << temp << " y = " << y << " nums = " << nums << " " << endl;
                                                }

                                        }
                                }
                        }
                }
        }
    return didIdoanything;
}

bool sudoku::rowscompletion()
{
    bool didIdoanything = false;
    for (int rows = 0; rows < SIZE; ++rows)
        {
            for (int nums = 1; nums <= SIZE; ++nums)
                {
                    int temp;
                    int colspace;
                    bool singleton = false;
                    int grids[size];
                    for (int q = 0; q < size; ++q)
                        {
                            grids[q] = -1;
                        }
                    int spaces = 0;
                    bool ok = false;
                    for (int cols = 0; cols < SIZE; ++cols)
                        {
                            if (possibilities[rows][cols].containsN(nums))
                                {
                                    if (spaces == 0)
                                        {
                                            singleton = true;
                                            grids[spaces] = getgrid(rows, cols);
                                            colspace = cols;
                                        }
                                    else
                                        {
                                            singleton = false;
                                            if (spaces < size) { grids[spaces] = getgrid(rows, cols); }
                                        }
                                    ++spaces;
                                }
                        }
                    if (singleton == true)
                        {
                            for (int x = 1; x <= SIZE; ++x)
                                {
                                    if (x != nums)
                                        {
                                            if (possibilities[rows][colspace].containsN(x))
                                                {
                                                    possibilities[rows][colspace].removeN(x);
                                                    didIdoanything = true;
                                                }
                                        }
                                }
                        }
                    else if (spaces <= size)
                        {
                            temp = grids[0];
                            for (int y = 1; y < spaces; ++y)
                                {
                                    if (temp != grids[y])
                                        {
                                            ok = false;
                                        }
                                }
                        }
                    if (ok == true)
                        {
                            int frog = firstrowofgrid(temp);
                            int fcog = firstcolofgrid(temp);
                            for (int i = frog; i < (frog + size); ++i)
                                {
                                    for (int j=fcog; j < (fcog + size); ++j)
                                        {
                                            if (getgrid(i, j) == grids[0])
                                                {
                                                    if (i != rows)
                                                        {
                                                            if (possibilities[i][j].containsN(nums))
                                                                {
                                                                    possibilities[i][j].removeN(nums);
                                                                    didIdoanything = true;
                                                                }
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }
    return didIdoanything;
}
wtf (670)
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
 
bool sudoku::contradiction(const int & n, const int & r, const int & c)
{
    //cout << "debugging code 1:"<<endl;
    if (n == 0)
        {
        return false;
        cout << "error code 3:" <<endl;
        }
    for (int i = 0; i < SIZE; ++i)
        {
            if (SU[r][i] == n)
                {cout << "error code 4:"<< endl;
                    cout << "r = " << r << " i = " << i << " c = " << c << " n = " << n << " " <<endl;
                    return true;
                }
        }
    for (int i = 0; i < SIZE; ++i)
        {
            if (SU[i][c] == n)    //was SU[i][r]
                {cout << "error code 5:"<<endl;
                    cout << "oh no! " << endl;
                    return true;
                }
        }

    setgrid(getgrid(r,c));
    for (int i = 0; i < size; ++i)
        {
            for (int j = 0; j < size; ++j)
                {
                    if (grid[i][j] == n)
                        {cout << "error code 6:"<< endl;
                            cout << "what! " << endl;
                        return true;        //assumes that redunancy has been checked in the imput module
                        }
                }
        }
    //cout << "correction code 1:"<<endl;

    return false;

}



int sudoku::getgrid(const int & r, const int & c)
{
    int g;
    int tr = r / size;
    int tc = c / size;
    g = (size * tr) + tc;
    //g = (size *tc) + tr;
    ++g;
    return g;

}
jsmith (5804)
Wow, that is a lot of code to ask people to debug for you. You might start by functionizing
a bit more. Your gridcompletion function has eight levels of nesting, 5 of which are for()
loops.


blackcoder41 (1426)
I'd like to help but you should comment your code and explain what it does. Also I agree with jsmith, your nested loop is too deep.

Have you tried to implement it using brute force?
wtf (670)


well I was able to reduce the level # of levels of nesting, but only by 1, by instead of for (int rgrids) and for (int cgrids) changing it to for (int grids = 1) yadayadayada and then calling int firstcol = firstcolofgrid() etc etc etc...



well could you at least look at my display function and give me some pointers on how I could implement it correctly? I want the double thick bars to differentiage between the minigrids, so for every 3 rows of numbers (each single line seperated by a line of underscores "_"), I want there to be a single line of whatever this thing is: char block2 = -78;

so far it works great right now when I'm working with a standard 9x9 Sudoku, but when i try to display a 4x4 or a 16x16, the blocks are off in a couple of places, and it gives me a headache to debug. I know I could do it, but it could save me a bit of time and $ as I'm having to use computers at a cyber cafe to do all my coding for the mean time.

thanks again for your help.
Last edited on
blackcoder41 (1426)
It's really hard to check tweak you code since you did not add comments to describe you algorithn. and it uses too many global variables.

Maybe this would help about the printing.

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
 
#include <iostream>
using namespace std;

void print(int BOARD[9][9])
{
	cout << " +-----------------------+\n";
	for(int r=0; r<9; r++) {
		for(int c=0; c<9; c++) {
			if( !c ) cout << " |";
			cout << " " << BOARD[r][c];
			if( c%3==2 )
				cout << " |";
		}
		if(r==2 || r==5)
			cout << "\n |-------+-------+-------|";
		cout << endl;
	}
	cout << " +-----------------------+\n";
}


int main()
{
    int board[9][9] = {0};
    print( board );
    return 0;
}
wtf (670)
Here is an example of what I want it to look like in a 9 by 9 board. (and so far so good)

▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓ 2 |   |   ▓   |   | 8 ▓ 6 |   | 1 ▓
▓-----------▓-----------▓-----------▓
▓   | 6 | 5 ▓   |   |   ▓   |   |   ▓
▓-----------▓-----------▓-----------▓
▓   |   |   ▓   | 7 | 2 ▓   |   |   ▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓ 6 |   | 9 ▓   |   |   ▓   |   |   ▓
▓-----------▓-----------▓-----------▓
▓   | 3 |   ▓ 9 | 4 | 6 ▓   |   |   ▓
▓-----------▓-----------▓-----------▓
▓   | 5 | 1 ▓   |   |   ▓   | 2 |   ▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓   |   |   ▓ 7 |   | 1 ▓   |   |   ▓
▓-----------▓-----------▓-----------▓
▓ 5 |   |   ▓   | 8 |   ▓ 3 | 7 | 2 ▓
▓-----------▓-----------▓-----------▓
▓   | 2 |   ▓   |   |   ▓   | 8 | 4 ▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓


but here's what it looks like when i try displaying a 16 by 16 board:

▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓ 16 | 14 | 12 | 10 ▓ 9 | 1 |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓ 2 | 3 | 4 | 1 ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓ 15 | 13 | 8 | 11 ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓--------------▓--------------▓--------------▓--------------▓---▓
▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓   |   |   |   ▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓

rocess returned 32 (0x20)   execution time : 0.094 s


any suggestions?
Topic archived. No new replies allowed.