Sudoku Solver; would appreciate some input

wtf (670)
I'm working on a sudoku solver because I am bored with solving them with hand. I have a few questions at the moment, and may from time to time seek advice in debugging, but to keep the project fun and a learning experience I want to do as much of it as I can by myself.

I'm using an class sudoku with an apmatrix of ints for the main board, and an apmatrix of lists of ints for the possible candidates for each possible square. int size; //is the size of the minigrid.
int SIZE; //is the size of the gameboard and the number of digits

Here is a couple of my questions:

The inference rules in my current aresenall are: row, column and grid completion; row and column elimination, (what I like to call) crowding out the column, grid, and row; reductio ad absurdum, and (what I really don't know what else to call it) hypothetical syllogism. I have not bothered to research other algorithms because I want to test my ability to finish this program by myself. But, although I think that these rules alone will be sufficient to solve any solveable sudoku, I am not certain. so I wanted some feedback on these inference rules, (not necessarily others!!!)


Row completion(), Column Completion(), and Grid completion()
e.g. Row completion () checks to see in each row if there is only one possible place for a number to go, it eliminates all other numbers from the possible candidates for that individual square. it also will check if there are less than or equal to size possible places for a number in that row to go, and each one of those possible places is in the same grid, then it will eliminate that number from the list of possible candidates in each of the other rows in that particular grid.

column elimination(), row elimination()
e.g. colun elimination() will check to see if in any grid, there is only one possible column for a particular number to go, then it will eliminate that number from the possible candidates of each square in that column in the other grids in the same sizeXsize rectange of grids.

crowding out the grid, crowding out the row, crowding out the colum()
e.g. crowding out the grid, will check each grid to see if there are only 2 or 3 places for a number to go in that grid, and if there are other numbers, such that can only occupy the same spaces that the first number can occupy, such that 2 numbers can only occupy the exact same 2 squares, or 3 numbers can only occupy the exact same 3 squares, then no other numbers may occupy those said 2 or 3 squares, and those numbers will thusly be eliminated from the list of possible candidates for those squares. (in theory you could extend this to check for 4 or 5 numbers at once, but I doubt it will be necessary, i rarely rely on this rule alone, but do find it neccessary sometimes)

reductio ad absurdum()
this should be self explanitory, if not just google reductio ad absurdum. it should be noted that since this rule is recursive, i am intending to call it only after the previous inference rules return false; i.e. by nesting the previous rules in a while loop and only calling reductio after the program can no longer make any deductions etc etc etc.

hypothetical syllogism()
I don't know what else to call this, in my program I call it ACE(), short for assumptions for comprehensive exhaustion. Since it is also recursive I am doing it similar to reductio ad absurdum. I do not know if either of these last 2 rules are technically ever necessary to solve a truly solveable sudoku, but there have been instances, when trying by hand, I have had to rely on 1 or both of these last two rules. my version of hypothetical syllogism does this:
if in any row, column or grid, there are only 2 or 3 (extendable as in crowding out above) possible places for a number to go, and if you were to assume each consecutive possibility, and the corresponding results were identical for any given square in the gameboard, you may safely deduct those results obtained in that square to the final solution, but you may not necessarily deduct those assumptions that yielded those results. similarily if there are only 2 or 3 possible numbers for any given square, and making consecutive assumptions (exhausting each possible number), were to yield identical results in any given square, you may also safely deduct those results. but be careful not to deduct any results that are not identical to each of the solved assumptions. i.e. the program will make 2 or 3 assumptions by declaring a sudoku temp1, temp2. temp1 = gameboard; temp2 = gameboard; temp1.solve(); temp2.solve(); then check each square of both temp1 and temp2 and if they are identical then your main gameboard = the entry in that square.

so what do you think of this set of inference rules? will this likely to lead to a program that can solve every solvable sudoku? without giving me ideas of different algorithms, can you suggest improvements to my current algorithms?

Thanks, also could you help debuggng in my .display() function.... thanks a lot


wtf (670)
so the display function works fine if its a 3 by 3, but its all f***** with 2by2 or 4by4, but i think i'm on the right track. in addition when I fix the dlist.h to include digits beyond just 9, its going to further screw up the formatting of the display function.

so far the only inference rule that I've debugged is gridcompletion, and thats the only rule that is being applied as is. I havent started debugging the other rules, but I know they all have bugs, but I would appreciate giving me a chance to walk through them first to try and figure it out on my own. Thanks in advance for your help.

wtf (670)
here is sudoku.h


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
 
#ifndef _SUDOKU_H
#define _SUDOKU_H

#include "dlist.h"
#include <string>
//#include <cctype>

using namespace std;
//#include "apqueue.h"
//c++ sudoku solver

//4-13-2010

class sudoku
{

    public:


  // constructors/destructor
    sudoku( );                                      // default size 0 x 0

    sudoku( int rows, int cols );                   // size rows x cols

    sudoku( int rows, int cols,
            const int & fillValue );           // all entries == fillValue

    sudoku( const sudoku & doku );                   // copy constructor

    ~sudoku( );                                     // destructor

  // assignment
    const sudoku & operator = ( const sudoku & rhs );
    const sudoku & operator == (const sudoku & rhs);
    int getsize();

  // indexing
    const void display();

  // modifiers
    void resize( int newRows, int newCols );   // resizes sudoku grid to newRows x newCols
                                               // (can result in losing values)

  // accessors
    int size;
    private:
    int SIZE;
    public:
    void create();
//    void display();



    private:

    public:
    void setgrid(const int & x);
    void cleargrid();

	private:

	void rowcompletion(const int & r);
	void rowcompletion();
	void rc();

	bool checkentry();
	bool contradiction(const int & n, const int & r, const int & c);
	bool isdone();

	bool isgoodentry(const int & n, const int & r, const int & c);


	//apmatrix<apqueue<int> > grid[size][size];  // or matrix<stack<int>> grid[size][size];
	//apmatrix<apqueue<int> > SU[SIZE][SIZE];
	apmatrix<int> grid;
	apmatrix<int> SU;

    private:

   //inference rules
    void eliminate();
    void fillintheblanks();
    void columnelimination();
    void rowelimination();
    void deductions();
    void gridcompletion();
    void crowdingoutthecolumn(const int & col);
    void crowdout();
    bool reductioadabsurdum();
    bool ace();
    bool rowace();
    void complete();


    bool contradictory();


    //void crowdout();



   //helper functions
    void searchrowingrid(const int & n, int & r);
    void searchcolumningrid(const int & n, int & c);
    void eliminatepossiblerowingrid(const int & n, const int & r);
    void eliminatepossiblecolumningrid(const int & n, const int & r);

    void eliminatepossibilities(const int & r, const int & c, const int & n);



    //apmatrix<apqueue<int> > possibilities, impossibilities;
    public:
    apmatrix<dlist> possibilities, impossibilities;
	int getgrid(const int & r, const int & c);  //



	public:
	void solve(); void solve(int steps);

	void load(const string & s);
	void save(const string & s);

	void everythingpossible();



void deduce(const int & n, const int & r, const int & c);
};

#include "sudoku.cpp"
#endif
wtf (670)
here is dlist.h, a class i wrote to act as a list of possibilities

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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
 

const short int max = 25;
short int length = 9;

#ifndef _DLIST_H
#define _DLIST_H




class dlist
{
    public:
    void everythingispossible();

    bool digits[max];

    dlist();                        //constructor
    dlist(const bool & b);          //assignment constructor
    dlist(const dlist & d);         //copy constructor
    ~dlist();                       //deconstructor

    void resize();

    bool containsN(const int & x);
    void toggleN(const int & x);
    void addN(const int & x);
    void removeN(const int & x);

    void display();

    bool solo(const int & s);

    int xuple();

    int ftrue();
    int strue();

    dlist & operator=(const dlist &rhs);
    //dlist & operator==(const dlist &rhs);
    bool operator == (const dlist & rhs);


    //const dlist & operator = ( const dlist & rhs );
    //bool & operator == (const dlist & rhs);

};

//#include "dlist.cpp"
#endif


dlist::dlist()
{}

dlist::dlist(const bool & b)
{
    for (int i = 0; i < length; ++i)
        {
            digits[i] = b;
        }
}


dlist::dlist(const dlist & d)
{
    for (int i = 0; i < length; ++i)
        {
            digits[i] = d.digits[i];
        }
}

dlist::~dlist()
{}

bool dlist:: containsN(const int & x)
{
    if (digits[x-1] == true)
        return true;
    else return false;
}

void dlist:: toggleN(const int & x)
{
    if (digits[x-1] == true)
        digits[x-1] = false;
        else digits[x-1] = true;
        return;
}

void dlist::addN(const int & x)
{
    digits[x-1] = true;
    return;
}

void dlist::removeN(const int & x)
{
    digits[x-1] = false;
    return;
}

void dlist::display()
{
    cout << endl;
    for (int i = 1; i <= 9; ++i)
     {
         if (digits[i-1] == true)
            cout << " " << i << ", ";
     }
     cout << endl;
}

bool dlist::solo(const int & s)
{
    //debugging
    //if (s !=9)
    //    return false;

    dlist temp = *this;

    if (!temp.containsN(s))
        {
            //cout << "likely";
            return false;
        }

    for (int i = 1; i < s; ++i)
        {
            if (temp.containsN(i) )
                {
                    //cout << "not";
                    return false;
                }
        }

    for (int i = s+1; i <= length; ++i)
        {

            if  (temp.containsN(i) )
                {
                    //cout << "what" << endl;
                    return false;
                }
        }
    //cout <<"!!!!!!!!!!!"<<endl;
    return true;

}

int dlist::xuple()
{
    int temp = 0;
    for (int i = 0; i < length; ++i)
        {
            if (digits[i] == true)
                {
                    ++temp;
                }
        }
    return temp;
    /*




    int temp = 0;
    for (int i = 0; i < SIZE; ++i)
        {
            if (digits[i] == true)
                {
                    ++temp;
                }
        }
    return temp;
    */
}

int dlist::ftrue()
{
    for (int f = 0; f < length; ++f)
        {
            if (digits[f] == true)
                return (f + 1);
        }
    return 0;
}

int dlist::strue()
{
    bool first = false;
    for (int s = 0; s < length; ++s)
        {
            if ( (digits[s] == true) && (first == true))
                return true;
            if (digits[s] == true)
                {
                    first = true;
                    //continue;
                }
        }
    return 0;
}

/*
const dlist &
dlist::operator = (const dlist & rhs)
{}




bool dlist::operator == (const dlist & rhs)
{
    dlist temp = *this;
    for (int i = 0; i < length; ++i)
        {
            if (temp[i] != rhs[i])
                return false;
        }
    return true;
}
*/

dlist& dlist::operator=(const dlist &rhs)
{
    //if (*this != rhs)
    //dlist temp = rhs;
        {
            for (int i = 0; i < length; ++i)
                {
                    digits[i] = rhs.digits[i];
                }
        }
}



/*dlist& dlist::operator==(const dlist &rhs)
{
    for (int i = 0; i < length; ++i)
        {
            if (digits[i] != rhs.digits[i])
                return false;
        }
    return true;
}
*/

bool dlist::operator == (const dlist & rhs)
{
        for (int i = 0; i < length; ++i)
        {
            if (digits[i] != rhs.digits[i])
                return false;
        }
    return true;
}

void dlist::everythingispossible()
{
    //cout << "lengh = " << length << "  " << endl;
    for (int i = 1; i <= length; ++i)
        {
            digits[i-1] = true;
        }
    return;
}

void resize(const int & n)
{
    if (n <= max)
        length = n;
    else cout << "error.  not doing anything here.  " << endl;
    return;
}
wtf (670)
here is sudoku.cpp

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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
 

#include "sudoku.h"
#include <iostream>
//#include <fstream>


sudoku::sudoku()
/*        : myRows(0),
          myCols(0),
          myMatrix(0)*/
          {
              //size = getsize();
              SIZE = (size * (size = getsize()));
              cout << "SIZE = " << SIZE << " and size = " << size << " " << endl;

          }


sudoku::sudoku(int rows,int cols)
/*        : myRows(rows),
          myCols(cols),
          myMatrix(rows)
          {
              {
                  int k;
                  for(k=0; k < rows; k++)
                    {
                        myMatrix[k].resize(cols);
                    }
              }
          }*/
          {

              if (rows != cols)
                {
                    cout << "\nDimension mismatch error.  Aborting... " << endl;
                    exit(1);
                }

              else
                {
                    SIZE = (size * (size = rows));
                    cout << "SIZE = " << SIZE << " and size = " << size << " " << endl;
                    possibilities.resize(SIZE, SIZE);
                }
          }

sudoku::sudoku(int rows, int cols, const int & fillValue)

        {
            if (rows != cols)
                {
                    cout << "\nDimension mismatch error.  Aborting... " << endl;
                    exit(1);
                }
            SIZE = (size * (size = rows));
            SU.resize(SIZE, SIZE);
            for (int i = 0; i < SIZE; ++i)
                {
                    for (int j = 0; j < SIZE; ++j)
                        {
                            SU[i][j] = fillValue;
                        }
                }
            possibilities.resize(SIZE,SIZE);
        }

sudoku::sudoku(const sudoku & doku)
    {}



sudoku::~sudoku ()
{

}

int sudoku::getsize()
{
    cout << "what size? " << endl;
    short n;
    cin >> n;
    //size = n;
    return n;
}

void sudoku::fillintheblanks()
{
    int tc[SIZE], tr[SIZE];
    for (int i = 0; i < SIZE; ++i)
        {
            tc[i] = -1;
            tr[i] = -1;
        }

    for (int i = 1; i <= 9; ++i)                 //checks for #'s 1- 9
        {
            for (int j = 0; j < size; ++j)
                {
                    for (int k = 0; k < size; ++k)
                        {
                            setgrid(j + k + 1);
                            searchrowingrid(i, tr[k]);
                            searchcolumningrid(i, tc[j]);
                        }
                    for (int l = 0; l < size; ++l)
                        {

                            //cout << "tr[l] = " << tr[l] << " and tc[l] = " << tc[l] << endl;
                            if (tr[l] != -1)
                                eliminatepossiblerowingrid(i, tr[l]);

                            if (tc[l] != -1)
                                eliminatepossiblecolumningrid(i, tc[l]);
                                ;



                        }
                }
        }
}



void sudoku::searchrowingrid(const int & n, int & r)
{
    r = -1;
    for (int x = 0; x < size; ++x)
        {
            for (int y = 0; y < size; ++y)
                {
                    if (grid[x][y] == n)
                        {  r = x; return; }
                }
        }
}

void sudoku::searchcolumningrid(const int & n, int & c)
{
    c = -1;
    for (int x = 0; x < size; ++x)
        {
            for (int y = 0; y < size; ++y)
                {
                    if (grid[x][y] == n)
                        { c = y;  return;  }
                }
        }
}

void sudoku::setgrid(const int & x)
{
    apmatrix<int> temp(size,size);

    int r = ((x - 1) / size ) * size;
    int c = ((x - 1) % size ) * size;

    for (int i = 0; i < size; ++i)
        {
            for (int j = 0; j < size; ++j)
                {
                    temp[i][j] = SU[i+r][j+c];
                }
        }
    grid = temp;
    return;
}


void sudoku::eliminatepossiblerowingrid(const int & n, const int & r)
{

    for (int i = 0; i < SIZE; ++i)
        {
            if (possibilities[r][i].containsN(n) )
                {
                    possibilities[r][i].removeN(n);
                }
        }
}
void sudoku::eliminatepossiblecolumningrid(const int & n, const int & c)
{

    for (int i = 0; i < SIZE; ++i)
        {
            if (possibilities[i][c].containsN(n) )
                {
                    possibilities[i][c].removeN(n);
                }
        }
}


void sudoku::create()
{
    int temp;
    for (int i = 0; i < SIZE; ++i)
        {
            for (int j = 0; j < SIZE; ++j)
                {
                    for (int k = 1; k < 10; ++k)
                        {
                            possibilities[i][j].addN(k);
                        }
                }
        }
    cout << endl << endl;
    cout << "Enter 0 for blank.  " << endl;
    for (int i = 0; i < SIZE; ++i)
        {
            for (int j = 0; j < SIZE; ++j)
                {
                    do
                    {
                        cout << "Enter " << i+1 << "th row " << j+1 << "th column: ";
                        cin >> temp;
                    }while(!isgoodentry(temp, i, j) && (temp != 99) && (temp != 999));
                    if (temp == 99)
                        {
                            cout << "go back to what row? " << endl;
                            int num;
                            cin >> num;
                            i = num -1;
                            break;
                        }

                    SU[i][j] = temp;
                    if (temp != 0)
                        {
                            for (int k = 1; k < 10; ++k)
                                {
                                    possibilities[i][j].removeN(k);
                                }
                            possibilities[i][j].addN(temp);
                        }
                }

        }
    cout << endl << endl;


    return;
}


void sudoku::solve()
{
    //crowdout();
    //gridcompletion();     //this is a good and a bad one. //
    complete();
    //eliminate();

    //ace();

    deductions();
}


void sudoku::solve(int steps)
{}

//void


bool sudoku::isgoodentry(const int & n, const int & r, const int & c)
{
    if (SU[r][c] != 0)
        return false;
    if ( (n >= 0) && (n < 10) )
        {
            if (!contradiction(n, r, c))
                {

                    return true;
                }
        }

    return false;
}

bool sudoku::contradiction(const int & n, const int & r, const int & c)
{
    if (n == 0)
        return false;
    for (int i = 0; i < SIZE; ++i)
        {
            if (SU[r][i] == n)
                {
                    return true;
                }
        }
    for (int i = 0; i < SIZE; ++i)
        {
            if (SU[i][c] == n)    //was SU[i][r]
                {
                    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 << "what! " << endl;
                        return true;        //assumes that redunancy has been checked in the imput module
                        }
                }
        }

    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;

}

void sudoku::cleargrid()
{
    for (int i = 0; i < SIZE; ++i)
        {
            for (int j = 0; j < SIZE; ++j)
                SU[i][j] = 0;
        }

}
wtf (670)
more of sudoku.cpp

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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
 

void sudoku::rowcompletion(const int & r)
{
    int rows = r;
    for (int nums = 1; nums <= SIZE; ++nums)
        {
            int pcols[size];
            bool solo = false; bool second = false;
            int soloc; int times;
            for (int cols = 0; cols < SIZE; ++cols)
                {
                    if (possibilities[rows][cols].containsN(nums))
                        {
                            if (times < size)
                                {
                                    pcols[times] = cols;
                                    ++times;
                                }

                            if (solo == true)
                                {
                                    second = true;
                                    solo = false;
                                }
                            else
                                {
                                    solo = true; second = false;
                                    soloc = cols;
                                }

                        }
                    /*else
                        {
                            solo = true; second = false;
                            soloc = cols;
                        }*/
                }

            if ( ( solo == true) && (second == false) )
                {
                    //deduce[rows][soloc]
                    deduce(nums, rows, soloc);
                }
            bool samegrid = true;
            for (int x = 1; x < size; ++x)
                {
                    if ( (pcols[x] / size ) != (pcols[0] / size) )
                        {
                            samegrid = false;
                        }
                }
            if (samegrid == true)
                {
                    int pivotr = (SIZE - (rows + 1)) % size;
                    //int pivotc = (SIZE - (cols + 1)) % size;
                    for (int j = 0; j < size; ++j)
                        {
                            int temp = rows + 1 - (size - pivotr) + j;
                            if (temp != rows)
                                {
                                    ; //debugging
                                }
                        }
                }
        }
}

void sudoku::rowcompletion()
{
    for (int r = 0; r < SIZE; ++r)
        {
            rowcompletion(r);
        }
}


void sudoku::columnelimination()
{
    for (int numbers = 1; numbers <=SIZE; ++numbers)
        {
            for (int columns = 0; columns < SIZE; ++columns)
                {
                    int negatives = 0; int g;
                    for (int grids = 0; grids < size; ++grids)
                        {
                            bool set = true;
                            for (int rows = 0; rows < size; ++rows)
                                {
                                    if (possibilities[(size*grids) + rows][columns].containsN(numbers))
                                        {
                                            set = false;
                                        }
                                }
                            if (set == true)
                                {   ++negatives;    }
                            else g = grids;
                            if (negatives == (size - 1))
                                {
                                    int pivotc = ( SIZE - (columns + 1) % size);
                                    grids = g;
                                    for (int i = 0; i < size; ++i)
                                        {
                                            for (int j = 0; j < size; ++j)
                                                {
                                                    //int temp = columns + 1 - (size - pivotc) + i;
                                                    int temp = 0 - (size - pivotc) + i;
                                                    //int temp = columns - pivotc;
                                                    if (temp != columns)
                                                        {//cout << "temp = " << temp << " " << endl;
                                                            //cout << "i = " << i << " j = " << j << " columns = " << columns << " grids = " << grids << " numbers = " << numbers << " pivotc =" << pivotc << " " << endl;
                                                            possibilities[size * grids + i][temp].removeN(numbers);
                                                            //if (numbers == 9)
                                                //{
                                                    //cout << "WWW" << endl;
                                                //}
                                                        }
                                                }
                                        }
                                }
                        }

                }
        }
}

void sudoku::deductions()
{

    //cout << "r0c0.solo(9) = " << possibilities[0][0].solo(9) << " " << endl;
    for (int r = 0; r < SIZE; ++r)
        {
            for (int c = 0; c < SIZE; ++c)
                {
                    if (possibilities[r][c].xuple() !=1)
                        break;
                    for (int n = 1; n <= SIZE; ++n)
                        {
                            if (possibilities[r][c].solo(n))
                                {
                                    //SU[r][c] = n;

                                    deduce(n,r,c);
                                }
                        }
                }
        }
    //listcheck();
}

void sudoku::rowelimination()
{
    //debugging cout << "rowelimination() " << endl; //debugging
    for (int numbers = 1; numbers <= SIZE; ++numbers)
        {
            for (int rows = 0; rows < SIZE; ++rows)
                {
                    int negatives = 0; int g;
                    for (int grids = 0; grids < size; ++grids)
                        {
                            bool set = true;
                            for (int columns = 0; columns < size; ++columns)
                                {
                                    if (possibilities[rows][size*grids+columns].containsN(numbers))
                                        {
                                            set = false;
                                        }
                                }
                            if (set == true)
                                {
                                    ++ negatives;
                                }
                            else g = grids;
                        }
                    if (negatives == (size - 1) )
                        {
                            int pivotr = (SIZE - (rows + 1)) % size;
                            //grids = g;
                            for (int i = 0; i < size; ++i)
                                {
                                    for (int j = 0; j < size; ++j)
                                        {
                                            int temp = rows + 1 - (size - pivotr) + j; // maybe ++j instead??  //was i
                                            if (temp != rows)
                                                {
                                                    possibilities[temp][size*g+j].removeN(numbers); //was size*grids+j
                                                    //if (numbers == 9)
                                                //{
                                                    //cout << "ccc" << endl;
                                                //}

                                                }
                                        }
                                }
                        }
                }
        }
}
wtf (670)
sudoku.cpp continued. 
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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
 
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;
                                    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);
                                        }
                                    possibilities[size*rgrids + solor][size *cgrids + soloc].addN(nums);
                                }



                        }
                }
        }
}

void sudoku::crowdingoutthecolumn(const int & col)
{
    dlist crowd[SIZE];      //I'm supposed to initialize this somehow.
    for (int i = 0; i < SIZE; ++i)
        {
            for (int n = 0; n > SIZE; ++n)
                {
                    crowd[i].removeN(n);
                }
        }

    for (int num = 1; num <= SIZE; ++num)
        {
            for (int row = 0; row < SIZE; ++row)
                {
                    if (possibilities[row][col].containsN(num))
                        {
                            crowd[num - 1].addN(row);
                        }
                }
        }
    DOUBLETON:
    int d1, d2, quantity;
    for (int in = 1; in <= SIZE; ++in)
        {
            quantity = crowd[in - 1].xuple();
            if (quantity == 2)
                {
                    for (int jn =in +1; jn <=SIZE; ++jn)
                        {
                            int q2 = crowd[jn-1].xuple();
                            if ( (q2 == 2) && (crowd[jn - 1] == crowd[in - 1]) )
                                {
                                    d1 = in; d2 = jn;
                                    for (int k = 0; k <= SIZE; ++k)
                                        {
                                            if ( (k != d1) && (k != d2) )
                                                {
                                                    possibilities[crowd[d1-1].ftrue()][col].removeN(k);
                                                    possibilities[crowd[d1-1].strue()][col].removeN(k);

                                                }
                                        }
                                    jn = SIZE;
                                }
                        }
                }
        }



}

void sudoku::crowdout()
{
    for (int i = 0; i < SIZE; ++i)
        {
            crowdingoutthecolumn(i);
            //
            //
        }
}
void sudoku::load(const string & s)
{

    #include <fstream>
    #include <cctype>
    using namespace std;
    ifstream infile;
    ofstream testfile, outfile;
    //testfile.open(s.c_str());
    infile.open(s.c_str() );
    if (infile.is_open())
        {
            //char number;
            int number;
            for (int row = 0; row < SIZE; ++row)
                {
                    for (int column = 0; column < SIZE; ++column)
                        {


                            number = infile.get();
                            number -= 48;
                            char x = number;

                            if ( ( number < 0) || (number > 10) )
                            { cout << "x = " << x << " " << endl;
                                cout << "number = " << number << endl;
                                exit(8192);
                                cout <<"notadigit!"<<endl;}
                            //else

                            SU[row][column] =  number;

                            if (number !=0)
                                {
                                    eliminatepossibilities(row, column, number);
                                }
                        }
                }
        }

}
void sudoku::everythingpossible()
{
    for (int i = 0; i < SIZE; ++i)
        {
            for (int j = 0; j < SIZE; ++j)
                {
                    possibilities[i][j].everythingispossible();
                }
        }
    return;
}
wtf (670)
sorry for the long posts, wanted to make it easier for you to help you by providing you with the entire source code.
sudoku.cpp continued...
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
170
 
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 (!contradiction(n, r, c) )
        {
            SU[r][c] = n;
            //listcheck();
            eliminatepossibilities(r, c, n);
        }
}

bool sudoku::reductioadabsurdum()
{
    cout << "a" << endl; //debugging
    //sudoku temp = SU;
    sudoku temp(*this);
    cout << "b1" << endl; //debugging
    if (temp.contradictory())
        return false;
        cout << "b2" << endl; //debugging
    for (int rows = 0; rows < SIZE; ++rows)
        {
            cout << "b" << endl; //debugging
            for (int cols = 0; cols < SIZE; ++cols)
                {cout << "c" << endl; //debugging
                    if (SU[rows][cols] == 0)
                        {cout << "d" << endl; //debugging
                            for (int nums = 1; nums <= SIZE; ++nums)
                                {cout << "e" << endl; //debugging
                                    if (possibilities[rows][cols].containsN(nums))
                                        { //does not get here // debugging
                                            //temp = SU;
                                            temp = *this;
                                            temp.SU[rows][cols] = nums;
                                            temp.solve();
                                            if (temp.contradictory())
                                                {
                                                    possibilities[rows][cols].removeN(nums);
                                                    return true;
                                                }
                                        }
                                }
                        }
                }
        }
    return false;
}

bool sudoku::contradictory()
{
    //debugging
    return false;
    int temp = -1;
    for (int n = 1; n <= SIZE; ++n)
        {
            for (int i = 0; i < SIZE; ++i)
                {
                    for (int j = 0; j < SIZE; ++j)
                        {
                            if (SU[i][j] != 0)
                                {
                                    if (i < SIZE - 2)
                                        for (int I = i + 1; I < SIZE; ++I)
                                            {
                                                if (SU[I][j] == SU[i][j])
                                                    {
                                                        return true;
                                                    }
                                                if (SU[i][I] == SU[i][j])
                                                    {
                                                        return true;
                                                    }
                                            }
                                }
                        }
                }
            temp = -1;
            for (int rgrids = 0; rgrids < size; ++rgrids)
                {
                    for (int cgrids = 0; cgrids < size; ++cgrids)
                        {
                            for (int rows = 0; rows < size; ++rows)
                                {
                                    for (int cols = 0; cols < size; ++cols)
                                        {
                                            if ( (SU[size*rgrids+rows][size*cgrids+cols] == n) && temp == n)
                                                {
                                                    return true;
                                                }
                                            if ( (SU[size*rgrids+rows][size*cgrids+cols] == n) && temp !=n)
                                                {
                                                    temp = n;
                                                }
                                        }
                                }
                        }
                }
        }
}
const sudoku& sudoku::operator=(const sudoku& rhs)
//void sudoku::operator = (const sudoku & rhs)
{
    sudoku t(rhs);

    for (int i = 0; i < SIZE; ++i)
        {
            for (int j = 0; j < SIZE; ++j)
                {
                    ;
                }
                ;
        }
    return t;
}

bool sudoku::ace()
{
    //return rowace();
}
wtf (670)
more of sudoku.cpp
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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
 
bool sudoku::rowace()
{
    int space1, space2, space3;
    sudoku t1(*this), t2(*this), t3(t2);
    //if (t1.possibilities == t2.possibilities)
    //    cout <<"true "<< endl;
    for (int num = 1; num <=SIZE; ++num)
        {
            int dot;
            for (int row = 0; row < SIZE; ++row)
                {
                    for (int col = 0; col <=SIZE; ++col)
                        {
                            int spaces = 0;
                            if ( (SU[row][col] == 0) && (possibilities[row][col].containsN(num) ) )
                                {
                                    ++spaces, space1 = col;
                                    for (int t = col + 1; t <= SIZE; ++t)
                                        {
                                            if ( ( SU[row][t] == 0) && (possibilities[row][t].containsN(num)) )
                                                {
                                                    ++spaces; space2 = t;
                                                    for (int z = t +1; z <= SIZE; ++z)
                                                        {
                                                            if ( (SU[row][z] == 0) && (possibilities[row][z].containsN(num) ) )
                                                                {
                                                                    ++spaces;
                                                                    space3 = z;
                                                                    for (int last = z+1; last <= SIZE; ++last)
                                                                        {
                                                                            if ( (SU[row][last] == 0) && (possibilities[row][last].containsN(num) ) )
                                                                                {
                                                                                    dot = 0;
                                                                                }
                                                                            else dot = 3;
                                                                        }
                                                                }
                                                            else dot = 2;
                                                        }
                                                }
                                        }
                                }
                        }
                    if (dot == 3)
                        {
                            t1.SU[row][space1] = num; t2.SU[row][space2] = num; t3.SU[row][space3] = num;
                            t1.solve(); t2.solve(); t3.solve();
                            for (int i = 0; i < SIZE; ++i)
                                {
                                    for (int j = 0; j < SIZE; ++j)
                                        {
                                            if ( (t1.SU[i][j] == t2.SU[i][j]) && (t2.SU[i][j] == t3.SU[i][j]) )
                                                {
                                                    //deduce(
                                                    SU[i][j] = t1.SU[i][j];
                                                    //eliminate possibilities

                                                }
                                        }
                                }
                        }
                    if (dot == 2)
                        {
                        }
                }
        }
    return true;
}
const sudoku& sudoku::operator==(const sudoku& rhs)
{
    sudoku temp(*this);
    //not finished yet!!

}

void sudoku::complete()
{
    //columncompletion();
    gridcompletion();
    //rowcompletion();
    //columncompletion();
    //gridcompletion();
    //rc();
}
void sudoku::rc()
{
    for (int rows = 0; rows < size; ++rows)
        {
            for (int nums = 1; nums <=SIZE; ++nums)
                {
                    int soloc;
                    bool solo = false; bool second = false;
                    for (int cols = 0; cols < size; ++cols)
                        {
                            if (possibilities[rows][cols].containsN(nums))
                                {
                                    if (solo == true)
                                        {
                                            second = true;
                                        }
                                    else
                                        {
                                            solo = true; second = false;
                                            soloc = cols;
                                        }
                                }
                        }


                    if ( (solo == true) && (second == false) )
                        {
                            SU[rows][soloc] = nums;
                            eliminatepossibilities(rows,soloc, nums);



                    //deduce(nums,size*rgrids + solor,size *cgrids + soloc);
                    //eliminate possibilities;
                    //for (int k = 1; k < 10; ++k)
                      //  {
                        //    possibilities[rows][size *cgrids + soloc].removeN(k);
                        //}
                    //possibilities[size*rgrids + solor][size *cgrids + soloc].addN(nums);
                        }       //maybe if (( solo == true )) yada yada goes here
                }



        }
}

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;
}
void sudoku::eliminate()
{
    columnelimination();


    return;
}
wtf (670)
lastly: last of sudoku.cpp //as of yet... 
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
 
void sudoku::save(const string & s)
{
    #include <fstream>
    #include <cctype>
    using namespace std;
    ifstream infile;
    ofstream testfile, outfile;
    outfile.open(s.c_str());
    if (outfile.is_open())
        {
            int number;
            for (int n = 0; n < SIZE; ++n)
                {
                    for (int m = 0; m < SIZE; ++m)
                    {
                        number = SU[n][m];
                        outfile << number;
                    }
                }
            outfile.close();
            return;
        }
    else cout << "Unforseen human error.  " << endl;
    return;
}
Topic archived. No new replies allowed.