1/*
2 * Copyright 2007-2012, Axel D��rfler, axeld@pinc-software.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include "SudokuGenerator.h"
8
9#include <stdio.h>
10#include <stdlib.h>
11#include <string.h>
12
13#include <Catalog.h>
14
15#include "ProgressWindow.h"
16#include "SudokuField.h"
17#include "SudokuSolver.h"
18
19
20#undef B_TRANSLATION_CONTEXT
21#define B_TRANSLATION_CONTEXT "SudokuGenerator"
22
23
24SudokuGenerator::SudokuGenerator()
25{
26}
27
28
29SudokuGenerator::~SudokuGenerator()
30{
31}
32
33
34bool
35SudokuGenerator::_HasOnlyOneSolution(SudokuField& field)
36{
37	SudokuSolver solver(&field);
38	solver.ComputeSolutions();
39
40	return solver.CountSolutions() == 1;
41}
42
43
44void
45SudokuGenerator::_Progress(BMessenger progress, const char* text,
46	float percent)
47{
48	BMessage update(kMsgProgressStatusUpdate);
49	if (text)
50		update.AddString("message", text);
51	update.AddFloat("percent", percent);
52	progress.SendMessage(&update);
53}
54
55
56void
57SudokuGenerator::Generate(SudokuField* target, uint32 fieldsLeft,
58	BMessenger progress, volatile bool *quit)
59{
60	// first step: generate a solved field - random brute force style
61
62	SudokuField field(target->BlockSize());
63	uint32 inputCount = field.Size() * field.Size() / 3;
64	_Progress(progress, B_TRANSLATE("Creating solvable field"), 5.f);
65
66	while (!*quit) {
67		field.Reset();
68
69		// generate input field
70
71		uint32 validMask = 0;
72
73		for (uint32 i = 0; i < inputCount; i++) {
74			uint32 x;
75			uint32 y;
76			do {
77				x = rand() % field.Size();
78				y = rand() % field.Size();
79			} while (!*quit && field.ValueAt(x, y) != 0);
80
81			validMask = field.ValidMaskAt(x, y);
82			if (validMask == 0)
83				break;
84
85			uint32 value;
86			do {
87				value = rand() % field.Size();
88			} while (!*quit && (validMask & (1UL << value)) == 0);
89
90			field.SetValueAt(x, y, value + 1);
91		}
92
93		if (validMask == 0)
94			continue;
95
96		// try to solve it
97
98		SudokuSolver solver(&field);
99		solver.ComputeSolutions();
100		if (solver.CountSolutions() > 0) {
101			// choose a random solution
102			field.SetTo(solver.SolutionAt(rand() % solver.CountSolutions()));
103			break;
104		}
105	}
106
107	if (*quit)
108		return;
109
110	// next step: try to remove as many fields as possible (and wished)
111	// that still have only a single solution
112
113	int32 removeCount = field.Size() * field.Size() - fieldsLeft;
114	bool tried[field.Size() * field.Size()];
115	int32 tries = field.Size() * field.Size() * 3 / 4;
116	memset(tried, 0, sizeof(tried));
117	_Progress(progress, B_TRANSLATE("Searching for removable values"), 30.f);
118
119	while (!*quit && removeCount > 0 && tries-- > 0) {
120		SudokuField copy(field);
121		uint32 x;
122		uint32 y;
123		do {
124			x = rand() % field.Size();
125			y = rand() % field.Size();
126		} while (copy.ValueAt(x, y) == 0 || tried[x + y * field.Size()]);
127
128		tried[x + y * field.Size()] = true;
129		copy.SetValueAt(x, y, 0);
130
131		if (_HasOnlyOneSolution(copy)) {
132			_Progress(progress, NULL, 100.f - (70.f * removeCount / 70.f));
133			field.SetTo(&copy);
134			removeCount--;
135		}
136	}
137
138	if (*quit)
139		return;
140
141	if (tries <= 0) {
142		puts("check all remove");
143		for (uint32 y = 0; y < field.Size(); y++) {
144			for (uint32 x = 0; x < field.Size(); x++) {
145				if (tried[x + y * field.Size()])
146					continue;
147
148				SudokuField copy(field);
149				copy.SetValueAt(x, y, 0);
150
151				if (_HasOnlyOneSolution(copy)) {
152					_Progress(progress, NULL,
153						100.f - (70.f * removeCount / 70.f));
154					field.SetTo(&copy);
155
156					if (--removeCount <= 0 || *quit)
157						break;
158				}
159			}
160
161			if (removeCount <= 0 || *quit)
162				break;
163		}
164		printf("  remove count = %" B_PRId32 "\n", removeCount);
165	}
166
167	// set the remaining values to be initial values
168
169	for (uint32 y = 0; y < field.Size(); y++) {
170		for (uint32 x = 0; x < field.Size(); x++) {
171			if (field.ValueAt(x, y))
172				field.SetFlagsAt(x, y, kInitialValue);
173		}
174	}
175
176	if (*quit)
177		return;
178
179	target->SetTo(&field);
180}
181
182