So I did. And it's messy. But it works!
It's messy, it's not a release, and the comments suck... but it works! (now, someone give me a puzzle that breaks it!
ToDo:
1: Better Input System
2: Better Debug Logging
3: Suggestions?
http://www.mediafire.com/?mg9elrhbwkb63om
1: #include <iostream>
2: #include "math.h"
3: #include <string>
4: using namespace std;
5: bool Debug = 0;
6: char abs(char x) //GCC is missing a char abs(char) function... wrote this as an after thought.
7: {
8: if( x < 0)
9: {
10: return (0-x);
11: }
12: else return x;
13: }
14: class puzzle
15: {
16: char PuzzleValues[9][9];
17: unsigned short sets[3][9];
18: public:
19: int updateSets() //returns number of changes. return system could be faster if integrated into
20: {
21: puzzle temp = *this;
22: //horizontal sets
23: for(int y = 0; y < 9 ; y++)
24: {
25: sets[0][y] = 0;
26: for(int x = 0; x < 9 ; x++)
27: {
28: if( GetValue(y,x) != 0 )
29: {
30: sets[0][y] += ((1 << (abs(GetValue(y,x))-1)) );
31: }
32: }
33: }
34: //vertical sets
35: for(int x = 0; x < 9 ; x++)
36: {
37: sets[1][x] = 0;
38: for(int y = 0; y < 9 ; y++)
39: {
40: if( GetValue(y,x) != 0 )
41: {
42: sets[1][x] += ( (1 << (abs(GetValue(y,x))-1)) );
43: }
44: }
45: }
46: //box sets
47: for(int group = 0; group < 9 ; group++)
48: {
49: sets[2][group] = 0;
50: for(int cell = 0; cell < 9; cell++)
51: {
52: int x = (3*(group%3)+cell%3);
53: int y = (3*(group/3)+cell/3);
54: if( GetValue(y,x) != 0 )
55: {
56: sets[2][group] += ( (1 << (abs(GetValue(y,x))-1)) );
57: }
58: }
59: }
60: int changes = 0;
61: for(int loop = 0; loop < 27 ; loop++ )
62: {
63: if( sets[loop/9][loop%9] != temp.sets[loop/9][loop%9] )
64: {
65: changes++;
66: }
67: }
68: return changes;
69: }
70: /*Objects of pointers are set to CELL Sets and Ranks, returns 0 for success, 1 or 3 for failed Set Pointer, 2 or 3 for failed RankPointer*/
71: short cellSet( int y , int x , short* Rank )
72: {
73: if( !PuzzleValues[y][x] )
74: {
75: short Set = 0;
76: short Temp;
77: Temp = ( (short)
78: 0x1ff - //4: then take 1 1111 1111 and subtract the row ORs from that
79: (
80: sets[0][y] | //1: check first row
81: sets[1][x] | //2: OR that with 2nd row
82: sets[2][(x/3)+(y - (y % 3 ))] //3: OR that with 3rd row to for the list of numbers that are close to a number
83: )
84: );
85: Set = Temp;
86: if(Rank != NULL )
87: {
88: short count = 0 ;
89: while (Temp) //count the number of 1s in Temp
90: {
91: count++;
92: Temp &= (Temp - 1) ;
93: }
94: *Rank = count;
95: }
96: return Set;
97: }
98: else
99: {
100: if(Rank != NULL)
101: {
102: *Rank = 0;
103: }
104: return 0;
105: }
106: }
107: //returns value at point, negitive for orignal puzzle
108: char GetValue( int y, int x )
109: {
110: return PuzzleValues[y][x];
111: }
112: //pass negitive VALUE for orignal puzzle
113: int SetValue( int y, int x, char VALUE /*-9 to 9*/ )
114: {
115: if( -9 <= VALUE && VALUE <= 9 )
116: {
117: PuzzleValues[y][x] = VALUE;
118: return 1;
119: }
120: else return 0;
121: }
122: //display the table. build a better table with ascii lines
123: string Display()
124: {
125: string OUTPUT;
126: for( int y = 0 ; y < 9 ; y++)
127: {
128: if( !(y%3))
129: {
130: OUTPUT += "+---------+---------+---------+\n";
131: }
132: for( int x = 0 ; x < 9 ; x++)
133: {
134: if( !(x%3) )
135: {
136: OUTPUT += "|";
137: }
138: if( 1 <= GetValue(y,x) && GetValue(y,x) <= 9 )
139: {
140: OUTPUT += ' ';
141: OUTPUT += (GetValue(y,x) + 48);
142: OUTPUT += ' ';
143: }
144: else if( -9 <= GetValue(y,x) && GetValue(y,x) <= -1 )
145: {
146: OUTPUT += '{';
147: OUTPUT += (( 0 - GetValue(y,x) ) + 48 );
148: OUTPUT += '}';
149: }
150: else
151: {
152: OUTPUT += " ";
153: }
154: }
155: OUTPUT += "|\n";
156: }
157: OUTPUT += "+---------+---------+---------+\n";
158: return OUTPUT;
159: }
160: //fills cells currently at rank1 that aren't full. returns number of changes
161: int fillCells()
162: {
163: int changes = 0;
164: //int CellInfluance[9][9];
165: for ( int x = 0; x < 9 ; x++ )
166: {
167: for ( int y = 0; y < 9 ; y++ )
168: {
169: //////should be replaced with the new fuction that does this for you.
170: //finds the binary list of 1 to 9 that are there.
171: int q = 0x1ff - ( //4: then take 1 1111 1111 and subtract the row ORs from that
172: sets[0][y] | //1: check first row
173: sets[1][x] | //2: OR that with 2nd row
174: sets[2][(x/3)+(y - (y % 3 ))] //3: OR that with 3rd row to for the list of numbers that are close to a number
175: );
176: //if power of 2, then return
177: for ( int p = 0 ; p < 9 ; p++ )
178: {
179: //reworked with previusly mentioned relacement
180: if(q == (1 << p) && GetValue( y , x ) == 0)
181: {
182: SetValue( y , x , (p+1) );
183: changes++;
184: }
185: }
186: }
187: }
188: return changes;
189: }
190: int Solved()
191: {
192: for(int x = 0 ; x < 81 ; x++)
193: {
194: if( !GetValue( x/9 , x%9 ) )
195: return 0;
196: }
197: return 1;
198: }
199: int unSolveable() //returns 0 if puzzle is unsolveable, 1 if it might be solveable
200: {
201: for(int x = 0 ; x < 81 ; x++)
202: {
203: if( !GetValue( x/9 , x%9 ) && !cellSet( x/9 , x%9 , NULL ) )
204: {
205: return 1;
206: }
207: }
208: return 0;
209: }
210: };
211: int Solve(puzzle *inPuzzle)
212: {
213: puzzle WCopy = *inPuzzle;
214: do
215: {
216: if( Debug == 1){
217: cout << WCopy.Display();
218: }
219: WCopy.updateSets();
220: } while( WCopy.fillCells() );
221: if( Debug == 1){
222: cout << WCopy.Display();
223: }
224: if( !WCopy.Solved() )
225: {
226: if( !WCopy.unSolveable() )
227: {
228: if( Debug == 1){
229: cout << WCopy.Display();
230: }
231: short LowestRank = 10;
232: short LowestSet;
233: char LowestRankX;
234: char LowestRankY;
235: //for loop that finds first lowest rank
236: for(char y = 0 ; y < 9 ; y++ )
237: {
238: for (char x = 0; x < 9 ; x++ )
239: {
240: short RANK = 0;
241: short SET = WCopy.cellSet( y , x , &RANK );
242: if( RANK != 0 && RANK < LowestRank && !WCopy.GetValue(y, x))
243: {
244: LowestRank = RANK;
245: LowestSet = SET;
246: LowestRankX = x;
247: LowestRankY = y;
248: }
249: }
250: }
251: //loop that guesses values out of that xy rank
252: for( short Guess = 0 ; Guess < 9 ; Guess++ )
253: {
254: if( (1 << Guess) & LowestSet )
255: {
256: puzzle GuessCopy = WCopy; //make a copy
257: GuessCopy.SetValue( LowestRankY , LowestRankX , Guess + 1 ); //dump guess into the copy
258: if( Debug == 1){
259: cout << WCopy.Display();
260: }
261: if( Solve( &GuessCopy ) )
262: {
263: if( Debug == 1){
264: cout << WCopy.Display();
265: }
266: *inPuzzle = WCopy = GuessCopy;
267: return 1;
268: }
269: }
270: }
271: return 0;
272: //if one guess wins, "*inPuzzle = WCopy;" and return 1
273: //if a guess fails, try next
274: //if all guesses fail, return 0;
275: }
276: else
277: return 0;
278: }
279: else
280: {
281: if( inPuzzle != NULL )
282: *inPuzzle = WCopy;
283: return 1;
284: }
285: }
286: int main(int argc, char *argv[])
287: {
288: string Input;
289: if(argc <= 1)
290: {
291: cout << "ERROR!, you're doing it wrong... Imma put more detal here later... \n" <<
292: "OR I could just solve a puzzle for you! How's that sound!?\n" <<
293: "how about this hard one! =D\n";
294: Input = "86..2.......7...59.............6.8...4.........53....7..........2....6....75.9..."; //hard puzzle
295: Debug = 0;
296: }
297: if(argc > 1)
298: {
299: Input = argv[1];
300: }
301: if(argc > 2)
302: {
303: // char test =
304: Debug = ( *argv[2] - '0');
305: }
306: //system("mode con cols=82");
307: puzzle MainPuzzle;
308: // Input = "86..2.......7...59.............6.8...4.........53....7..........2....6....75.9..."; //hard puzzle
309: // Input = ".931.564.7.......55.12.93.72.......3.369.752.9.......13.24.81.96.......4.473.285."; //easy puzzle
310: // Input = ".3..........28.1.7.78.6.4.....8.2.7..82...54..9.5.4.....1.7.25.8.6.21..........8."; //mid puzzle
311: cout << "starting input:\n" << Input << "\nstarting puzzle:\n";
312: for(int y = 0; y < 9 ; y++ )
313: {
314: for(int x = 0; x < 9 ; x++ )
315: {
316: cout << Input[y*9 + x];
317: char q = Input[ 9 * y + x ];
318: if( q != '.' )
319: {
320: MainPuzzle.SetValue( y , x , 0 - (q - 48) );
321: }
322: else
323: {
324: MainPuzzle.SetValue( y , x , 0 );
325: }
326: }
327: cout << '\n';
328: }
329: cout << MainPuzzle.Display();
330: Solve( &MainPuzzle );
331: cout << "\n\nDERP!\n\n";
332: cout << MainPuzzle.Display();
333: //MainPuzzle.updateSets();
334: //short CellSets[2][9][9];
335: //bool run = true;
336: //while( run )
337: //{
338: // MainPuzzle.updateSets();
339: // while(MainPuzzle.fillCells() )
340: // {
341: // MainPuzzle.updateSets();
342: // cout << '\n' << MainPuzzle.Display();
343: // }
344: // for( int x = 0; x < 81 ; x++)
345: // {
346: // short q; //rack
347: // short p; //sets
348: // p = MainPuzzle.cellSet( x%9 , x/9 , &q );
349: // CellSets[0][x/9][x%9] = q;
350: // CellSets[1][x/9][x%9] = p;
351: // }
352: // run = true;
353: //
354: //}
355: // system( "pause" ); //works only Visual Studio compiler.
356: }
