1/*
2 * Copyright 2007, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include "SudokuSolver.h"
8
9#include "SudokuField.h"
10#include "Stack.h"
11
12
13struct SolutionStep {
14public:
15	SolutionStep(const SudokuField* field);
16	SolutionStep(const SolutionStep& other);
17	~SolutionStep();
18
19	void ToFirstUnset();
20	bool ToNextUnset();
21
22	void SetSolvedFields();
23
24	SudokuField* Field() { return fField; }
25	uint32 X() { return fX; }
26	uint32 Y() { return fY; }
27
28private:
29	SudokuField*	fField;
30	uint32			fX;
31	uint32			fY;
32};
33
34typedef std::vector<SolutionStep*> StepList;
35
36
37uint32
38bit_count(uint32 value)
39{
40	uint32 count = 0;
41	while (value > 0) {
42		if (value & 1)
43			count++;
44		value >>= 1;
45	}
46	return count;
47}
48
49
50//	#pragma mark -
51
52
53SolutionStep::SolutionStep(const SudokuField* _field)
54{
55	fField = new SudokuField(*_field);
56	fX = 0;
57	fY = 0;
58}
59
60
61SolutionStep::SolutionStep(const SolutionStep& other)
62{
63	fField = new SudokuField(*other.fField);
64	fX = other.fX;
65	fY = other.fY;
66}
67
68
69SolutionStep::~SolutionStep()
70{
71	delete fField;
72}
73
74
75void
76SolutionStep::ToFirstUnset()
77{
78	for (uint32 y = 0; y < fField->Size(); y++) {
79		for (uint32 x = 0; x < fField->Size(); x++) {
80			if (!fField->ValueAt(x, y)) {
81				uint32 validMask = fField->ValidMaskAt(x, y);
82				if (bit_count(validMask) == 1) {
83					// If the chosen value is already solved, we set its
84					// value here and go on - this makes sure the first
85					// unset we return has actually more than one possible
86					// value
87					uint32 value = 0;
88					while ((validMask & (1UL << value)) == 0) {
89						value++;
90					}
91					fField->SetValueAt(x, y, value + 1, true);
92					continue;
93				}
94
95				fX = x;
96				fY = y;
97				return;
98			}
99		}
100	}
101
102}
103
104
105bool
106SolutionStep::ToNextUnset()
107{
108	for (uint32 y = fY; y < fField->Size(); y++) {
109		for (uint32 x = 0; x < fField->Size(); x++) {
110			if (y == fY && x == 0) {
111				x = fX;
112				continue;
113			}
114
115			if (!fField->ValueAt(x, y)) {
116				fX = x;
117				fY = y;
118				return true;
119			}
120		}
121	}
122
123	return false;
124}
125
126
127//	#pragma mark -
128
129
130SudokuSolver::SudokuSolver(SudokuField* field)
131	:
132	fField(field)
133{
134}
135
136
137SudokuSolver::SudokuSolver()
138	:
139	fField(NULL)
140{
141}
142
143
144SudokuSolver::~SudokuSolver()
145{
146	// we don't own the field but the solutions
147	_MakeEmpty();
148}
149
150
151void
152SudokuSolver::_MakeEmpty()
153{
154	for (uint32 i = 0; i < fSolutions.size(); i++) {
155		delete fSolutions[i];
156	}
157}
158
159
160void
161SudokuSolver::SetTo(SudokuField* field)
162{
163	fField = field;
164}
165
166
167void
168SudokuSolver::ComputeSolutions()
169{
170	_MakeEmpty();
171
172	// We need to check if generating a solution is affordable with a
173	// brute force algorithm like this one
174	uint32 set = 0;
175	for (uint32 y = 0; y < fField->Size(); y++) {
176		for (uint32 x = 0; x < fField->Size(); x++) {
177			if (fField->ValueAt(x, y))
178				set++;
179		}
180	}
181	if (set < fField->Size() * fField->Size() / 6)
182		return;
183
184	Stack<SolutionStep*> stack;
185	SolutionStep* step = new SolutionStep(fField);
186	step->ToFirstUnset();
187
188	stack.Push(step);
189	uint32 count = 0;
190
191	// brute force version
192
193	while (stack.Pop(&step)) {
194		uint32 x = step->X();
195		uint32 y = step->Y();
196		uint32 validMask = step->Field()->ValidMaskAt(x, y);
197
198		count++;
199
200		if (step->ToNextUnset()) {
201			if (validMask != 0) {
202				// generate further steps
203				for (uint32 i = 0; i < fField->Size(); i++) {
204					if ((validMask & (1UL << i)) == 0)
205						continue;
206
207					SolutionStep* next = new SolutionStep(*step);
208					next->Field()->SetValueAt(x, y, i + 1, true);
209					stack.Push(next);
210				}
211			}
212		} else if (step->Field()->IsSolved())
213			fSolutions.push_back(new SudokuField(*step->Field()));
214
215		delete step;
216	}
217
218	//printf("evaluated %lu steps\n", count);
219}
220
221
222uint32
223SudokuSolver::CountSolutions()
224{
225	return fSolutions.size();
226}
227
228
229SudokuField*
230SudokuSolver::SolutionAt(uint32 index)
231{
232	return fSolutions[index];
233}
234
235