~ubuntu-branches/ubuntu/dapper/sgt-puzzles/dapper : revision 1

1

/*

2

* loopy.c: An implementation of the Nikoli game 'Loop the loop'.

3

* (c) Mike Pinna, 2005

4

*

5

* vim: set shiftwidth=4 :set textwidth=80:

6

*/

7

8

/*

9

* TODO:

10

*

11

* - setting very high recursion depth seems to cause memory

12

* munching: are we recursing before checking completion, by any

13

* chance?

14

*

15

* - there's an interesting deductive technique which makes use of

16

* topology rather than just graph theory. Each _square_ in the

17

* grid is either inside or outside the loop; you can tell that

18

* two squares are on the same side of the loop if they're

19

* separated by an x (or, more generally, by a path crossing no

20

* LINE_UNKNOWNs and an even number of LINE_YESes), and on the

21

* opposite side of the loop if they're separated by a line (or

22

* an odd number of LINE_YESes and no LINE_UNKNOWNs). Oh, and

23

* any square separated from the outside of the grid by a

24

* LINE_YES or a LINE_NO is on the inside or outside

25

* respectively. So if you can track this for all squares, you

26

* can occasionally spot that two squares are separated by a

27

* LINE_UNKNOWN but their relative insideness is known, and

28

* therefore deduce the state of the edge between them.

29

* + An efficient way to track this would be by augmenting the

30

* disjoint set forest data structure. Each element, along

31

* with a pointer to a parent member of its equivalence

32

* class, would also carry a one-bit field indicating whether

33

* it was equal or opposite to its parent. Then you could

34

* keep flipping a bit as you ascended the tree during

35

* dsf_canonify(), and hence you'd be able to return the

36

* relationship of the input value to its ultimate parent

37

* (and also you could then get all those bits right when you

38

* went back up the tree rewriting). So you'd be able to

39

* query whether any two elements were known-equal,

40

* known-opposite, or not-known, and you could add new

41

* equalities or oppositenesses to increase your knowledge.

42

* (Of course the algorithm would have to fail an assertion

43

* if you tried to tell it two things it already knew to be

44

* opposite were equal, or vice versa!)

45

* This data structure would also be useful in the

46

* graph-theoretic part of the solver, where it could be used

47

* for storing information about which lines are known-identical

48

* or known-opposite. (For example if two lines bordering a 3

49

* are known-identical they must both be LINE_YES, and if they

50

* are known-opposite, the *other* two lines bordering that clue

51

* must be LINE_YES, etc). This may duplicate some

52

* functionality already present in the solver but it is more

53

* general and we could remove the old code, so that's no bad

54

* thing.

55

*/

56

57

#include <stdio.h>

58

#include <stdlib.h>

59

#include <string.h>

60

#include <assert.h>

61

#include <ctype.h>

62

#include <math.h>

63

64

#include "puzzles.h"

65

#include "tree234.h"

66

67

#define PREFERRED_TILE_SIZE 32

68

#define TILE_SIZE (ds->tilesize)

69

#define LINEWIDTH (ds->linewidth)

70

#define BORDER (TILE_SIZE / 2)

71

72

#define FLASH_TIME 0.5F

73

74

#define HL_COUNT(state) ((state)->w * ((state)->h + 1))

75

#define VL_COUNT(state) (((state)->w + 1) * (state)->h)

76

#define DOT_COUNT(state) (((state)->w + 1) * ((state)->h + 1))

77

#define SQUARE_COUNT(state) ((state)->w * (state)->h)

78

79

#define ABOVE_SQUARE(state, i, j) ((state)->hl[(i) + (state)->w * (j)])

80

#define BELOW_SQUARE(state, i, j) ABOVE_SQUARE(state, i, (j)+1)

81

82

#define LEFTOF_SQUARE(state, i, j) ((state)->vl[(i) + ((state)->w + 1) * (j)])

83

#define RIGHTOF_SQUARE(state, i, j) LEFTOF_SQUARE(state, (i)+1, j)

84

85

#define LEGAL_DOT(state, i, j) ((i) >= 0 && (j) >= 0 && \

86

(i) <= (state)->w && (j) <= (state)->h)

87

88

/*

89

* These macros return rvalues only, but can cope with being passed

90

* out-of-range coordinates.

91

*/

92

#define ABOVE_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || j <= 0) ? \

93

LINE_NO : LV_ABOVE_DOT(state, i, j))

94

#define BELOW_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || j >= (state)->h) ? \

95

LINE_NO : LV_BELOW_DOT(state, i, j))

96

97

#define LEFTOF_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || i <= 0) ? \

98

LINE_NO : LV_LEFTOF_DOT(state, i, j))

99

#define RIGHTOF_DOT(state, i, j) ((!LEGAL_DOT(state, i, j) || i >= (state)->w)?\

100

LINE_NO : LV_RIGHTOF_DOT(state, i, j))

101

102

/*

103

* These macros expect to be passed valid coordinates, and return

104

* lvalues.

105

*/

106

#define LV_BELOW_DOT(state, i, j) ((state)->vl[(i) + ((state)->w + 1) * (j)])

107

#define LV_ABOVE_DOT(state, i, j) LV_BELOW_DOT(state, i, (j)-1)

108

109

#define LV_RIGHTOF_DOT(state, i, j) ((state)->hl[(i) + (state)->w * (j)])

110

#define LV_LEFTOF_DOT(state, i, j) LV_RIGHTOF_DOT(state, (i)-1, j)

111

112

#define CLUE_AT(state, i, j) ((i < 0 || i >= (state)->w || \

113

j < 0 || j >= (state)->h) ? \

114

' ' : LV_CLUE_AT(state, i, j))

115

116

#define LV_CLUE_AT(state, i, j) ((state)->clues[(i) + (state)->w * (j)])

117

118

#define OPP(dir) (dir == LINE_UNKNOWN ? LINE_UNKNOWN : \

119

dir == LINE_YES ? LINE_NO : LINE_YES)

120

121

#define BIT_SET(field, bit) ((field) & (1<<(bit)))

122

123

#define SET_BIT(field, bit) (BIT_SET(field, bit) ? FALSE : \

124

((field) |= (1<<(bit)), TRUE))

125

126

#define CLEAR_BIT(field, bit) (BIT_SET(field, bit) ? \

127

((field) &= ~(1<<(bit)), TRUE) : FALSE)

128

129

static char *game_text_format(game_state *state);

130

131

enum {

132

COL_BACKGROUND,

133

COL_FOREGROUND,

134

COL_HIGHLIGHT,

135

COL_MISTAKE,

136

NCOLOURS

137

};

138

139

/*

140

* Difficulty levels. I do some macro ickery here to ensure that my

141

* enum and the various forms of my name list always match up.

142

*/

143

#define DIFFLIST(A) \

144

A(EASY,Easy,e) \

145

A(NORMAL,Normal,n)

146

#define ENUM(upper,title,lower) DIFF_ ## upper,

147

#define TITLE(upper,title,lower) #title,

148

#define ENCODE(upper,title,lower) #lower

149

#define CONFIG(upper,title,lower) ":" #title

150

enum { DIFFLIST(ENUM) DIFFCOUNT };

151

/* static char const *const loopy_diffnames[] = { DIFFLIST(TITLE) }; */

152

static char const loopy_diffchars[] = DIFFLIST(ENCODE);

153

#define DIFFCONFIG DIFFLIST(CONFIG)

154

155

/* LINE_YES_ERROR is only used in the drawing routine */

156

enum line_state { LINE_UNKNOWN, LINE_YES, LINE_NO /*, LINE_YES_ERROR*/ };

157

158

enum direction { UP, DOWN, LEFT, RIGHT };

159

160

struct game_params {

161

int w, h, diff, rec;

162

};

163

164

struct game_state {

165

int w, h;

166

167

/* Put ' ' in a square that doesn't get a clue */

168

char *clues;

169

170

/* Arrays of line states, stored left-to-right, top-to-bottom */

171

char *hl, *vl;

172

173

int solved;

174

int cheated;

175

176

int recursion_depth;

177

};

178

179

static game_state *dup_game(game_state *state)

180

{

181

game_state *ret = snew(game_state);

182

183

ret->h = state->h;

184

ret->w = state->w;

185

ret->solved = state->solved;

186

ret->cheated = state->cheated;

187

188

ret->clues = snewn(SQUARE_COUNT(state), char);

189

memcpy(ret->clues, state->clues, SQUARE_COUNT(state));

190

191

ret->hl = snewn(HL_COUNT(state), char);

192

memcpy(ret->hl, state->hl, HL_COUNT(state));

193

194

ret->vl = snewn(VL_COUNT(state), char);

195

memcpy(ret->vl, state->vl, VL_COUNT(state));

196

197

ret->recursion_depth = state->recursion_depth;

198

199

return ret;

200

}

201

202

static void free_game(game_state *state)

203

{

204

if (state) {

205

sfree(state->clues);

206

sfree(state->hl);

207

sfree(state->vl);

208

sfree(state);

209

}

210

}

211

212

enum solver_status {

213

SOLVER_SOLVED, /* This is the only solution the solver could find */

214

SOLVER_MISTAKE, /* This is definitely not a solution */

215

SOLVER_AMBIGUOUS, /* This _might_ be an ambiguous solution */

216

SOLVER_INCOMPLETE /* This may be a partial solution */

217

};

218

219

typedef struct solver_state {

220

game_state *state;

221

char *dot_atleastone;

222

char *dot_atmostone;

223

/* char *dline_identical; */

224

int recursion_remaining;

225

enum solver_status solver_status;

226

/* NB looplen is the number of dots that are joined together at a point, ie a

227

* looplen of 1 means there are no lines to a particular dot */

228

int *dotdsf, *looplen;

229

} solver_state;

230

231

static solver_state *new_solver_state(game_state *state) {

232

solver_state *ret = snew(solver_state);

233

int i;

234

235

ret->state = dup_game(state);

236

237

ret->dot_atmostone = snewn(DOT_COUNT(state), char);

238

memset(ret->dot_atmostone, 0, DOT_COUNT(state));

239

ret->dot_atleastone = snewn(DOT_COUNT(state), char);

240

memset(ret->dot_atleastone, 0, DOT_COUNT(state));

241

242

#if 0

243

dline_identical = snewn(DOT_COUNT(state), char);

244

memset(dline_identical, 0, DOT_COUNT(state));

245

#endif

246

247

ret->recursion_remaining = state->recursion_depth;

248

ret->solver_status = SOLVER_INCOMPLETE;

249

250

ret->dotdsf = snewn(DOT_COUNT(state), int);

251

ret->looplen = snewn(DOT_COUNT(state), int);

252

for (i = 0; i < DOT_COUNT(state); i++) {

253

ret->dotdsf[i] = i;

254

ret->looplen[i] = 1;

255

}

256

257

return ret;

258

}

259

260

static void free_solver_state(solver_state *sstate) {

261

if (sstate) {

262

free_game(sstate->state);

263

sfree(sstate->dot_atleastone);

264

sfree(sstate->dot_atmostone);

265

/* sfree(sstate->dline_identical); */

266

sfree(sstate->dotdsf);

267

sfree(sstate->looplen);

268

sfree(sstate);

269

}

270

}

271

272

static solver_state *dup_solver_state(solver_state *sstate) {

273

game_state *state;

274

275

solver_state *ret = snew(solver_state);

276

277

ret->state = state = dup_game(sstate->state);

278

279

ret->dot_atmostone = snewn(DOT_COUNT(state), char);

280

memcpy(ret->dot_atmostone, sstate->dot_atmostone, DOT_COUNT(state));

281

282

ret->dot_atleastone = snewn(DOT_COUNT(state), char);

283

memcpy(ret->dot_atleastone, sstate->dot_atleastone, DOT_COUNT(state));

284

285

#if 0

286

ret->dline_identical = snewn((state->w + 1) * (state->h + 1), char);

287

memcpy(ret->dline_identical, state->dot_atmostone,

288

(state->w + 1) * (state->h + 1));

289

#endif

290

291

ret->recursion_remaining = sstate->recursion_remaining;

292

ret->solver_status = sstate->solver_status;

293

294

ret->dotdsf = snewn(DOT_COUNT(state), int);

295

ret->looplen = snewn(DOT_COUNT(state), int);

296

memcpy(ret->dotdsf, sstate->dotdsf, DOT_COUNT(state) * sizeof(int));

297

memcpy(ret->looplen, sstate->looplen, DOT_COUNT(state) * sizeof(int));

298

299

return ret;

300

}

301

302

/*

303

* Merge two dots due to the existence of an edge between them.

304

* Updates the dsf tracking equivalence classes, and keeps track of

305

* the length of path each dot is currently a part of.

306

* Returns TRUE if the dots were already linked, ie if they are part of a

307

* closed loop, and false otherwise.

308

*/

309

static int merge_dots(solver_state *sstate, int x1, int y1, int x2, int y2)

310

{

311

int i, j, len;

312

313

i = y1 * (sstate->state->w + 1) + x1;

314

j = y2 * (sstate->state->w + 1) + x2;

315

316

i = dsf_canonify(sstate->dotdsf, i);

317

j = dsf_canonify(sstate->dotdsf, j);

318

319

if (i == j) {

320

return TRUE;

321

} else {

322

len = sstate->looplen[i] + sstate->looplen[j];

323

dsf_merge(sstate->dotdsf, i, j);

324

i = dsf_canonify(sstate->dotdsf, i);

325

sstate->looplen[i] = len;

326

return FALSE;

327

}

328

}

329

330

/* Count the number of lines of a particular type currently going into the

331

* given dot. Lines going off the edge of the board are assumed fixed no. */

332

static int dot_order(const game_state* state, int i, int j, char line_type)

333

{

334

int n = 0;

335

336

if (i > 0) {

337

if (LEFTOF_DOT(state, i, j) == line_type)

338

++n;

339

} else {

340

if (line_type == LINE_NO)

341

++n;

342

}

343

if (i < state->w) {

344

if (RIGHTOF_DOT(state, i, j) == line_type)

345

++n;

346

} else {

347

if (line_type == LINE_NO)

348

++n;

349

}

350

if (j > 0) {

351

if (ABOVE_DOT(state, i, j) == line_type)

352

++n;

353

} else {

354

if (line_type == LINE_NO)

355

++n;

356

}

357

if (j < state->h) {

358

if (BELOW_DOT(state, i, j) == line_type)

359

++n;

360

} else {

361

if (line_type == LINE_NO)

362

++n;

363

}

364

365

return n;

366

}

367

/* Count the number of lines of a particular type currently surrounding the

368

* given square */

369

static int square_order(const game_state* state, int i, int j, char line_type)

370

{

371

int n = 0;

372

373

if (ABOVE_SQUARE(state, i, j) == line_type)

374

++n;

375

if (BELOW_SQUARE(state, i, j) == line_type)

376

++n;

377

if (LEFTOF_SQUARE(state, i, j) == line_type)

378

++n;

379

if (RIGHTOF_SQUARE(state, i, j) == line_type)

380

++n;

381

382

return n;

383

}

384

385

/* Set all lines bordering a dot of type old_type to type new_type

386

* Return value tells caller whether this function actually did anything */

387

static int dot_setall(game_state *state, int i, int j,

388

char old_type, char new_type)

389

{

390

int retval = FALSE;

391

if (old_type == new_type)

392

return FALSE;

393

394

if (i > 0 && LEFTOF_DOT(state, i, j) == old_type) {

395

LV_LEFTOF_DOT(state, i, j) = new_type;

396

retval = TRUE;

397

}

398

399

if (i < state->w && RIGHTOF_DOT(state, i, j) == old_type) {

400

LV_RIGHTOF_DOT(state, i, j) = new_type;

401

retval = TRUE;

402

}

403

404

if (j > 0 && ABOVE_DOT(state, i, j) == old_type) {

405

LV_ABOVE_DOT(state, i, j) = new_type;

406

retval = TRUE;

407

}

408

409

if (j < state->h && BELOW_DOT(state, i, j) == old_type) {

410

LV_BELOW_DOT(state, i, j) = new_type;

411

retval = TRUE;

412

}

413

414

return retval;

415

}

416

/* Set all lines bordering a square of type old_type to type new_type */

417

static void square_setall(game_state *state, int i, int j,

418

char old_type, char new_type)

419

{

420

if (ABOVE_SQUARE(state, i, j) == old_type)

421

ABOVE_SQUARE(state, i, j) = new_type;

422

if (BELOW_SQUARE(state, i, j) == old_type)

423

BELOW_SQUARE(state, i, j) = new_type;

424

if (LEFTOF_SQUARE(state, i, j) == old_type)

425

LEFTOF_SQUARE(state, i, j) = new_type;

426

if (RIGHTOF_SQUARE(state, i, j) == old_type)

427

RIGHTOF_SQUARE(state, i, j) = new_type;

428

}

429

430

static game_params *default_params(void)

431

{

432

game_params *ret = snew(game_params);

433

434

#ifdef SLOW_SYSTEM

435

ret->h = 4;

436

ret->w = 4;

437

#else

438

ret->h = 10;

439

ret->w = 10;

440

#endif

441

ret->diff = DIFF_EASY;

442

ret->rec = 0;

443

444

return ret;

445

}

446

447

static game_params *dup_params(game_params *params)

448

{

449

game_params *ret = snew(game_params);

450

*ret = *params; /* structure copy */

451

return ret;

452

}

453

454

static const struct {

455

char *desc;

456

game_params params;

457

} loopy_presets[] = {

458

{ "4x4 Easy", { 4, 4, DIFF_EASY, 0 } },

459

{ "4x4 Normal", { 4, 4, DIFF_NORMAL, 0 } },

460

{ "7x7 Easy", { 7, 7, DIFF_EASY, 0 } },

461

{ "7x7 Normal", { 7, 7, DIFF_NORMAL, 0 } },

462

{ "10x10 Easy", { 10, 10, DIFF_EASY, 0 } },

463

{ "10x10 Normal", { 10, 10, DIFF_NORMAL, 0 } },

464

#ifndef SLOW_SYSTEM

465

{ "15x15 Easy", { 15, 15, DIFF_EASY, 0 } },

466

{ "15x15 Normal", { 15, 15, DIFF_NORMAL, 0 } },

467

{ "30x20 Easy", { 30, 20, DIFF_EASY, 0 } },

468

{ "30x20 Normal", { 30, 20, DIFF_NORMAL, 0 } }

469

#endif

470

};

471

472

static int game_fetch_preset(int i, char **name, game_params **params)

473

{

474

game_params tmppar;

475

476

if (i < 0 || i >= lenof(loopy_presets))

477

return FALSE;

478

479

tmppar = loopy_presets[i].params;

480

*params = dup_params(&tmppar);

481

*name = dupstr(loopy_presets[i].desc);

482

483

return TRUE;

484

}

485

486

static void free_params(game_params *params)

487

{

488

sfree(params);

489

}

490

491

static void decode_params(game_params *params, char const *string)

492

{

493

params->h = params->w = atoi(string);

494

params->rec = 0;

495

params->diff = DIFF_EASY;

496

while (*string && isdigit((unsigned char)*string)) string++;

497

if (*string == 'x') {

498

string++;

499

params->h = atoi(string);

500

while (*string && isdigit((unsigned char)*string)) string++;

501

}

502

if (*string == 'r') {

503

string++;

504

params->rec = atoi(string);

505

while (*string && isdigit((unsigned char)*string)) string++;

506

}

507

if (*string == 'd') {

508

int i;

509

510

string++;

511

for (i = 0; i < DIFFCOUNT; i++)

512

if (*string == loopy_diffchars[i])

513

params->diff = i;

514

if (*string) string++;

515

}

516

}

517

518

static char *encode_params(game_params *params, int full)

519

{

520

char str[80];

521

sprintf(str, "%dx%d", params->w, params->h);

522

if (full)

523

sprintf(str + strlen(str), "r%dd%c", params->rec,

524

loopy_diffchars[params->diff]);

525

return dupstr(str);

526

}

527

528

static config_item *game_configure(game_params *params)

529

{

530

config_item *ret;

531

char buf[80];

532

533

ret = snewn(4, config_item);

534

535

ret[0].name = "Width";

536

ret[0].type = C_STRING;

537

sprintf(buf, "%d", params->w);

538

ret[0].sval = dupstr(buf);

539

ret[0].ival = 0;

540

541

ret[1].name = "Height";

542

ret[1].type = C_STRING;

543

sprintf(buf, "%d", params->h);

544

ret[1].sval = dupstr(buf);

545

ret[1].ival = 0;

546

547

ret[2].name = "Difficulty";

548

ret[2].type = C_CHOICES;

549

ret[2].sval = DIFFCONFIG;

550

ret[2].ival = params->diff;

551

552

ret[3].name = NULL;

553

ret[3].type = C_END;

554

ret[3].sval = NULL;

555

ret[3].ival = 0;

556

557

return ret;

558

}

559

560

static game_params *custom_params(config_item *cfg)

561

{

562

game_params *ret = snew(game_params);

563

564

ret->w = atoi(cfg[0].sval);

565

ret->h = atoi(cfg[1].sval);

566

ret->rec = 0;

567

ret->diff = cfg[2].ival;

568

569

return ret;

570

}

571

572

static char *validate_params(game_params *params, int full)

573

{

574

if (params->w < 4 || params->h < 4)

575

return "Width and height must both be at least 4";

576

if (params->rec < 0)

577

return "Recursion depth can't be negative";

578

579

/*

580

* This shouldn't be able to happen at all, since decode_params

581

* and custom_params will never generate anything that isn't

582

* within range.

583

*/

584

assert(params->diff >= 0 && params->diff < DIFFCOUNT);

585

586

return NULL;

587

}

588

589

/* We're going to store a list of current candidate squares for lighting.

590

* Each square gets a 'score', which tells us how adding that square right

591

* now would affect the length of the solution loop. We're trying to

592

* maximise that quantity so will bias our random selection of squares to

593

* light towards those with high scores */

594

struct square {

595

int score;

596

unsigned long random;

597

int x, y;

598

};

599

600

static int get_square_cmpfn(void *v1, void *v2)

601

{

602

struct square *s1 = (struct square *)v1;

603

struct square *s2 = (struct square *)v2;

604

int r;

605

606

r = s1->x - s2->x;

607

if (r)

608

return r;

609

610

r = s1->y - s2->y;

611

if (r)

612

return r;

613

614

return 0;

615

}

616

617

static int square_sort_cmpfn(void *v1, void *v2)

618

{

619

struct square *s1 = (struct square *)v1;

620

struct square *s2 = (struct square *)v2;

621

int r;

622

623

r = s2->score - s1->score;

624

if (r) {

625

return r;

626

}

627

628

if (s1->random < s2->random)

629

return -1;

630

else if (s1->random > s2->random)

631

return 1;

632

633

/*

634

* It's _just_ possible that two squares might have been given

635

* the same random value. In that situation, fall back to

636

* comparing based on the coordinates. This introduces a tiny

637

* directional bias, but not a significant one.

638

*/

639

return get_square_cmpfn(v1, v2);

640

}

641

642

static void print_tree(tree234 *tree)

643

{

644

#if 0

645

int i = 0;

646

struct square *s;

647

printf("Print tree:\n");

648

while (i < count234(tree)) {

649

s = (struct square *)index234(tree, i);

650

assert(s);

651

printf(" [%d,%d], %d, %d\n", s->x, s->y, s->score, s->random);

652

++i;

653

}

654

#endif

655

}

656

657

enum { SQUARE_LIT, SQUARE_UNLIT };

658

659

#define SQUARE_STATE(i, j) \

660

(((i) < 0 || (i) >= params->w || \

661

(j) < 0 || (j) >= params->h) ? \

662

SQUARE_UNLIT : LV_SQUARE_STATE(i,j))

663

664

#define LV_SQUARE_STATE(i, j) board[(i) + params->w * (j)]

665

666

static void print_board(const game_params *params, const char *board)

667

{

668

#if 0

669

int i,j;

670

671

printf(" ");

672

for (i = 0; i < params->w; i++) {

673

printf("%d", i%10);

674

}

675

printf("\n");

676

for (j = 0; j < params->h; j++) {

677

printf("%d", j%10);

678

for (i = 0; i < params->w; i++) {

679

printf("%c", SQUARE_STATE(i, j) ? ' ' : 'O');

680

}

681

printf("\n");

682

}

683

#endif

684

}

685

686

static char *new_fullyclued_board(game_params *params, random_state *rs)

687

{

688

char *clues;

689

char *board;

690

int i, j, a, b, c;

691

game_state s;

692

game_state *state = &s;

693

int board_area = SQUARE_COUNT(params);

694

int t;

695

696

struct square *square, *tmpsquare, *sq;

697

struct square square_pos;

698

699

/* These will contain exactly the same information, sorted into different

700

* orders */

701

tree234 *lightable_squares_sorted, *lightable_squares_gettable;

702

703

#define SQUARE_REACHABLE(i,j) \

704

(t = (SQUARE_STATE(i-1, j) == SQUARE_LIT || \

705

SQUARE_STATE(i+1, j) == SQUARE_LIT || \

706

SQUARE_STATE(i, j-1) == SQUARE_LIT || \

707

SQUARE_STATE(i, j+1) == SQUARE_LIT), \

708

/* printf("SQUARE_REACHABLE(%d,%d) = %d\n", i, j, t), */ \

709

t)

710

711

712

/* One situation in which we may not light a square is if that'll leave one

713

* square above/below and one left/right of us unlit, separated by a lit

714

* square diagnonal from us */

715

#define SQUARE_DIAGONAL_VIOLATION(i, j, h, v) \

716

(t = (SQUARE_STATE((i)+(h), (j)) == SQUARE_UNLIT && \

717

SQUARE_STATE((i), (j)+(v)) == SQUARE_UNLIT && \

718

SQUARE_STATE((i)+(h), (j)+(v)) == SQUARE_LIT), \

719

/* t ? printf("SQUARE_DIAGONAL_VIOLATION(%d, %d, %d, %d)\n",

720

i, j, h, v) : 0,*/ \

721

t)

722

723

/* We also may not light a square if it will form a loop of lit squares

724

* around some unlit squares, as then the game soln won't have a single

725

* loop */

726

#define SQUARE_LOOP_VIOLATION(i, j, lit1, lit2) \

727

(SQUARE_STATE((i)+1, (j)) == lit1 && \

728

SQUARE_STATE((i)-1, (j)) == lit1 && \

729

SQUARE_STATE((i), (j)+1) == lit2 && \

730

SQUARE_STATE((i), (j)-1) == lit2)

731

732

#define CAN_LIGHT_SQUARE(i, j) \

733

(SQUARE_REACHABLE(i, j) && \

734

!SQUARE_DIAGONAL_VIOLATION(i, j, -1, -1) && \

735

!SQUARE_DIAGONAL_VIOLATION(i, j, +1, -1) && \

736

!SQUARE_DIAGONAL_VIOLATION(i, j, -1, +1) && \

737

!SQUARE_DIAGONAL_VIOLATION(i, j, +1, +1) && \

738

!SQUARE_LOOP_VIOLATION(i, j, SQUARE_LIT, SQUARE_UNLIT) && \

739

!SQUARE_LOOP_VIOLATION(i, j, SQUARE_UNLIT, SQUARE_LIT))

740

741

#define IS_LIGHTING_CANDIDATE(i, j) \

742

(SQUARE_STATE(i, j) == SQUARE_UNLIT && \

743

CAN_LIGHT_SQUARE(i,j))

744

745

/* The 'score' of a square reflects its current desirability for selection

746

* as the next square to light. We want to encourage moving into uncharted

747

* areas so we give scores according to how many of the square's neighbours

748

* are currently unlit. */

749

750

/* UNLIT SCORE

751

* 3 2

752

* 2 0

753

* 1 -2

754

*/

755

#define SQUARE_SCORE(i,j) \

756

(2*((SQUARE_STATE(i-1, j) == SQUARE_UNLIT) + \

757

(SQUARE_STATE(i+1, j) == SQUARE_UNLIT) + \

758

(SQUARE_STATE(i, j-1) == SQUARE_UNLIT) + \

759

(SQUARE_STATE(i, j+1) == SQUARE_UNLIT)) - 4)

760

761

/* When a square gets lit, this defines how far away from that square we

762

* need to go recomputing scores */

763

#define SCORE_DISTANCE 1

764

765

board = snewn(board_area, char);

766

clues = snewn(board_area, char);

767

768

state->h = params->h;

769

state->w = params->w;

770

state->clues = clues;

771

772

/* Make a board */

773

memset(board, SQUARE_UNLIT, board_area);

774

775

/* Seed the board with a single lit square near the middle */

776

i = params->w / 2;

777

j = params->h / 2;

778

if (params->w & 1 && random_bits(rs, 1))

779

++i;

780

if (params->h & 1 && random_bits(rs, 1))

781

++j;

782

783

LV_SQUARE_STATE(i, j) = SQUARE_LIT;

784

785

/* We need a way of favouring squares that will increase our loopiness.

786

* We do this by maintaining a list of all candidate squares sorted by

787

* their score and choose randomly from that with appropriate skew.

788

* In order to avoid consistently biasing towards particular squares, we

789

* need the sort order _within_ each group of scores to be completely

790

* random. But it would be abusing the hospitality of the tree234 data

791

* structure if our comparison function were nondeterministic :-). So with

792

* each square we associate a random number that does not change during a

793

* particular run of the generator, and use that as a secondary sort key.

794

* Yes, this means we will be biased towards particular random squares in

795

* any one run but that doesn't actually matter. */

796

797

lightable_squares_sorted = newtree234(square_sort_cmpfn);

798

lightable_squares_gettable = newtree234(get_square_cmpfn);

799

#define ADD_SQUARE(s) \

800

do { \

801

/* printf("ADD SQUARE: [%d,%d], %d, %d\n",

802

s->x, s->y, s->score, s->random);*/ \

803

sq = add234(lightable_squares_sorted, s); \

804

assert(sq == s); \

805

sq = add234(lightable_squares_gettable, s); \

806

assert(sq == s); \

807

} while (0)

808

809

#define REMOVE_SQUARE(s) \

810

do { \

811

/* printf("DELETE SQUARE: [%d,%d], %d, %d\n",

812

s->x, s->y, s->score, s->random);*/ \

813

sq = del234(lightable_squares_sorted, s); \

814

assert(sq); \

815

sq = del234(lightable_squares_gettable, s); \

816

assert(sq); \

817

} while (0)

818

819

#define HANDLE_DIR(a, b) \

820

square = snew(struct square); \

821

square->x = (i)+(a); \

822

square->y = (j)+(b); \

823

square->score = 2; \

824

square->random = random_bits(rs, 31); \

825

ADD_SQUARE(square);

826

HANDLE_DIR(-1, 0);

827

HANDLE_DIR( 1, 0);

828

HANDLE_DIR( 0,-1);

829

HANDLE_DIR( 0, 1);

830

#undef HANDLE_DIR

831

832

/* Light squares one at a time until the board is interesting enough */

833

while (TRUE)

834

{

835

/* We have count234(lightable_squares) possibilities, and in

836

* lightable_squares_sorted they are sorted with the most desirable

837

* first. */

838

c = count234(lightable_squares_sorted);

839

if (c == 0)

840

break;

841

assert(c == count234(lightable_squares_gettable));

842

843

/* Check that the best square available is any good */

844

square = (struct square *)index234(lightable_squares_sorted, 0);

845

assert(square);

846

847

/*

848

* We never want to _decrease_ the loop's perimeter. Making

849

* moves that leave the perimeter the same is occasionally

850

* useful: if it were _never_ done then the user would be

851

* able to deduce illicitly that any degree-zero vertex was

852

* on the outside of the loop. So we do it sometimes but

853

* not always.

854

*/

855

if (square->score < 0 || (square->score == 0 &&

856

random_upto(rs, 2) == 0))

857

break;

858

859

print_tree(lightable_squares_sorted);

860

assert(square->score == SQUARE_SCORE(square->x, square->y));

861

assert(SQUARE_STATE(square->x, square->y) == SQUARE_UNLIT);

862

assert(square->x >= 0 && square->x < params->w);

863

assert(square->y >= 0 && square->y < params->h);

864

/* printf("LIGHT SQUARE: [%d,%d], score = %d\n", square->x, square->y, square->score); */

865

866

/* Update data structures */

867

LV_SQUARE_STATE(square->x, square->y) = SQUARE_LIT;

868

REMOVE_SQUARE(square);

869

870

print_board(params, board);

871

872

/* We might have changed the score of any squares up to 2 units away in

873

* any direction */

874

for (b = -SCORE_DISTANCE; b <= SCORE_DISTANCE; b++) {

875

for (a = -SCORE_DISTANCE; a <= SCORE_DISTANCE; a++) {

876

if (!a && !b)

877

continue;

878

square_pos.x = square->x + a;

879

square_pos.y = square->y + b;

880

/* printf("Refreshing score for [%d,%d]:\n", square_pos.x, square_pos.y); */

881

if (square_pos.x < 0 || square_pos.x >= params->w ||

882

square_pos.y < 0 || square_pos.y >= params->h) {

883

/* printf(" Out of bounds\n"); */

884

continue;

885

}

886

tmpsquare = find234(lightable_squares_gettable, &square_pos,

887

NULL);

888

if (tmpsquare) {

889

/* printf(" Removing\n"); */

890

assert(tmpsquare->x == square_pos.x);

891

assert(tmpsquare->y == square_pos.y);

892

assert(SQUARE_STATE(tmpsquare->x, tmpsquare->y) ==

893

SQUARE_UNLIT);

894

REMOVE_SQUARE(tmpsquare);

895

} else {

896

/* printf(" Creating\n"); */

897

tmpsquare = snew(struct square);

898

tmpsquare->x = square_pos.x;

899

tmpsquare->y = square_pos.y;

900

tmpsquare->random = random_bits(rs, 31);

901

}

902

tmpsquare->score = SQUARE_SCORE(tmpsquare->x, tmpsquare->y);

903

904

if (IS_LIGHTING_CANDIDATE(tmpsquare->x, tmpsquare->y)) {

905

/* printf(" Adding\n"); */

906

ADD_SQUARE(tmpsquare);

907

} else {

908

/* printf(" Destroying\n"); */

909

sfree(tmpsquare);

910

}

911

}

912

}

913

sfree(square);

914

/* printf("\n\n"); */

915

}

916

917

while ((square = delpos234(lightable_squares_gettable, 0)) != NULL)

918

sfree(square);

919

freetree234(lightable_squares_gettable);

920

freetree234(lightable_squares_sorted);

921

922

/* Copy out all the clues */

923

for (j = 0; j < params->h; ++j) {

924

for (i = 0; i < params->w; ++i) {

925

c = SQUARE_STATE(i, j);

926

LV_CLUE_AT(state, i, j) = '0';

927

if (SQUARE_STATE(i-1, j) != c) ++LV_CLUE_AT(state, i, j);

928

if (SQUARE_STATE(i+1, j) != c) ++LV_CLUE_AT(state, i, j);

929

if (SQUARE_STATE(i, j-1) != c) ++LV_CLUE_AT(state, i, j);

930

if (SQUARE_STATE(i, j+1) != c) ++LV_CLUE_AT(state, i, j);

931

}

932

}

933

934

sfree(board);

935

return clues;

936

}

937

938

static solver_state *solve_game_rec(const solver_state *sstate, int diff);

939

940

static int game_has_unique_soln(const game_state *state, int diff)

941

{

942

int ret;

943

solver_state *sstate_new;

944

solver_state *sstate = new_solver_state((game_state *)state);

945

946

sstate_new = solve_game_rec(sstate, diff);

947

948

ret = (sstate_new->solver_status == SOLVER_SOLVED);

949

950

free_solver_state(sstate_new);

951

free_solver_state(sstate);

952

953

return ret;

954

}

955

956

/* Remove clues one at a time at random. */

957

static game_state *remove_clues(game_state *state, random_state *rs, int diff)

958

{

959

int *square_list, squares;

960

game_state *ret = dup_game(state), *saved_ret;

961

int n;

962

963

/* We need to remove some clues. We'll do this by forming a list of all

964

* available equivalence classes, shuffling it, then going along one at a

965

* time clearing every member of each equivalence class, where removing a

966

* class doesn't render the board unsolvable. */

967

squares = state->w * state->h;

968

square_list = snewn(squares, int);

969

for (n = 0; n < squares; ++n) {

970

square_list[n] = n;

971

}

972

973

shuffle(square_list, squares, sizeof(int), rs);

974

975

for (n = 0; n < squares; ++n) {

976

saved_ret = dup_game(ret);

977

LV_CLUE_AT(ret, square_list[n] % state->w,

978

square_list[n] / state->w) = ' ';

979

if (game_has_unique_soln(ret, diff)) {

980

free_game(saved_ret);

981

} else {

982

free_game(ret);

983

ret = saved_ret;

984

}

985

}

986

sfree(square_list);

987

988

return ret;

989

}

990

991

static char *validate_desc(game_params *params, char *desc);

992

993

static char *new_game_desc(game_params *params, random_state *rs,

994

char **aux, int interactive)

995

{

996

/* solution and description both use run-length encoding in obvious ways */

997

char *retval;

998

char *description = snewn(SQUARE_COUNT(params) + 1, char);

999

char *dp = description;

1000

int i, j;

1001

int empty_count;

1002

game_state *state = snew(game_state), *state_new;

1003

1004

state->h = params->h;

1005

state->w = params->w;

1006

1007

state->hl = snewn(HL_COUNT(params), char);

1008

state->vl = snewn(VL_COUNT(params), char);

1009

1010

newboard_please:

1011

memset(state->hl, LINE_UNKNOWN, HL_COUNT(params));

1012

memset(state->vl, LINE_UNKNOWN, VL_COUNT(params));

1013

1014

state->solved = state->cheated = FALSE;

1015

state->recursion_depth = params->rec;

1016

1017

/* Get a new random solvable board with all its clues filled in. Yes, this

1018

* can loop for ever if the params are suitably unfavourable, but

1019

* preventing games smaller than 4x4 seems to stop this happening */

1020

1021

do {

1022

state->clues = new_fullyclued_board(params, rs);

1023

} while (!game_has_unique_soln(state, params->diff));

1024

1025

state_new = remove_clues(state, rs, params->diff);

1026

free_game(state);

1027

state = state_new;

1028

1029

if (params->diff > 0 && game_has_unique_soln(state, params->diff-1)) {

1030

/* Board is too easy */

1031

goto newboard_please;

1032

}

1033

1034

empty_count = 0;

1035

for (j = 0; j < params->h; ++j) {

1036

for (i = 0; i < params->w; ++i) {

1037

if (CLUE_AT(state, i, j) == ' ') {

1038

if (empty_count > 25) {

1039

dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));

1040

empty_count = 0;

1041

}

1042

empty_count++;

1043

} else {

1044

if (empty_count) {

1045

dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));

1046

empty_count = 0;

1047

}

1048

dp += sprintf(dp, "%c", (int)(CLUE_AT(state, i, j)));

1049

}

1050

}

1051

}

1052

if (empty_count)

1053

dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));

1054

1055

free_game(state);

1056

retval = dupstr(description);

1057

sfree(description);

1058

1059

assert(!validate_desc(params, retval));

1060

1061

return retval;

1062

}

1063

1064

/* We require that the params pass the test in validate_params and that the

1065

* description fills the entire game area */

1066

static char *validate_desc(game_params *params, char *desc)

1067

{

1068

int count = 0;

1069

1070

for (; *desc; ++desc) {

1071

if (*desc >= '0' && *desc <= '9') {

1072

count++;

1073

continue;

1074

}

1075

if (*desc >= 'a') {

1076

count += *desc - 'a' + 1;

1077

continue;

1078

}

1079

return "Unknown character in description";

1080

}

1081

1082

if (count < SQUARE_COUNT(params))

1083

return "Description too short for board size";

1084

if (count > SQUARE_COUNT(params))

1085

return "Description too long for board size";

1086

1087

return NULL;

1088

}

1089

1090

static game_state *new_game(midend *me, game_params *params, char *desc)

1091

{

1092

int i,j;

1093

game_state *state = snew(game_state);

1094

int empties_to_make = 0;

1095

int n;

1096

const char *dp = desc;

1097

1098

state->recursion_depth = 0; /* XXX pending removal, probably */

1099

1100

state->h = params->h;

1101

state->w = params->w;

1102

1103

state->clues = snewn(SQUARE_COUNT(params), char);

1104

state->hl = snewn(HL_COUNT(params), char);

1105

state->vl = snewn(VL_COUNT(params), char);

1106

1107

state->solved = state->cheated = FALSE;

1108

1109

for (j = 0 ; j < params->h; ++j) {

1110

for (i = 0 ; i < params->w; ++i) {

1111

if (empties_to_make) {

1112

empties_to_make--;

1113

LV_CLUE_AT(state, i, j) = ' ';

1114

continue;

1115

}

1116

1117

assert(*dp);

1118

n = *dp - '0';

1119

if (n >=0 && n < 10) {

1120

LV_CLUE_AT(state, i, j) = *dp;

1121

} else {

1122

n = *dp - 'a' + 1;

1123

assert(n > 0);

1124

LV_CLUE_AT(state, i, j) = ' ';

1125

empties_to_make = n - 1;

1126

}

1127

++dp;

1128

}

1129

}

1130

1131

memset(state->hl, LINE_UNKNOWN, HL_COUNT(params));

1132

memset(state->vl, LINE_UNKNOWN, VL_COUNT(params));

1133

1134

return state;

1135

}

1136

1137

enum { LOOP_NONE=0, LOOP_SOLN, LOOP_NOT_SOLN };

1138

1139

/* Sums the lengths of the numbers in range [0,n) */

1140

/* See equivalent function in solo.c for justification of this. */

1141

static int len_0_to_n(int n)

1142

{

1143

int len = 1; /* Counting 0 as a bit of a special case */

1144

int i;

1145

1146

for (i = 1; i < n; i *= 10) {

1147

len += max(n - i, 0);

1148

}

1149

1150

return len;

1151

}

1152

1153

static char *encode_solve_move(const game_state *state)

1154

{

1155

int len, i, j;

1156

char *ret, *p;

1157

/* This is going to return a string representing the moves needed to set

1158

* every line in a grid to be the same as the ones in 'state'. The exact

1159

* length of this string is predictable. */

1160

1161

len = 1; /* Count the 'S' prefix */

1162

/* Numbers in horizontal lines */

1163

/* Horizontal lines, x position */

1164

len += len_0_to_n(state->w) * (state->h + 1);

1165

/* Horizontal lines, y position */

1166

len += len_0_to_n(state->h + 1) * (state->w);

1167

/* Vertical lines, y position */

1168

len += len_0_to_n(state->h) * (state->w + 1);

1169

/* Vertical lines, x position */

1170

len += len_0_to_n(state->w + 1) * (state->h);

1171

/* For each line we also have two letters and a comma */

1172

len += 3 * (HL_COUNT(state) + VL_COUNT(state));

1173

1174

ret = snewn(len + 1, char);

1175

p = ret;

1176

1177

p += sprintf(p, "S");

1178

1179

for (j = 0; j < state->h + 1; ++j) {

1180

for (i = 0; i < state->w; ++i) {

1181

switch (RIGHTOF_DOT(state, i, j)) {

1182

case LINE_YES:

1183

p += sprintf(p, "%d,%dhy", i, j);

1184

break;

1185

case LINE_NO:

1186

p += sprintf(p, "%d,%dhn", i, j);

1187

break;

1188

/* default: */

1189

/* I'm going to forgive this because I think the results

1190

* are cute. */

1191

/* assert(!"Solver produced incomplete solution!"); */

1192

}

1193

}

1194

}

1195

1196

for (j = 0; j < state->h; ++j) {

1197

for (i = 0; i < state->w + 1; ++i) {

1198

switch (BELOW_DOT(state, i, j)) {

1199

case LINE_YES:

1200

p += sprintf(p, "%d,%dvy", i, j);

1201

break;

1202

case LINE_NO:

1203

p += sprintf(p, "%d,%dvn", i, j);

1204

break;

1205

/* default: */

1206

/* I'm going to forgive this because I think the results

1207

* are cute. */

1208

/* assert(!"Solver produced incomplete solution!"); */

1209

}

1210

}

1211

}

1212

1213

/* No point in doing sums like that if they're going to be wrong */

1214

assert(strlen(ret) == (size_t)len);

1215

return ret;

1216

}

1217

1218

/* BEGIN SOLVER IMPLEMENTATION */

1219

1220

/* For each pair of lines through each dot we store a bit for whether

1221

* exactly one of those lines is ON, and in separate arrays we store whether

1222

* at least one is on and whether at most 1 is on. (If we know both or

1223

* neither is on that's already stored more directly.) That's six bits per

1224

* dot. Bit number n represents the lines shown in dot_type_dirs[n]. */

1225

1226

enum dline {

1227

DLINE_VERT = 0,

1228

DLINE_HORIZ = 1,

1229

DLINE_UL = 2,

1230

DLINE_DR = 3,

1231

DLINE_UR = 4,

1232

DLINE_DL = 5

1233

};

1234

1235

#define OPP_DLINE(dline) (dline ^ 1)

1236

1237

1238

#define SQUARE_DLINES \

1239

HANDLE_DLINE(DLINE_UL, RIGHTOF_SQUARE, BELOW_SQUARE, 1, 1); \

1240

HANDLE_DLINE(DLINE_UR, LEFTOF_SQUARE, BELOW_SQUARE, 0, 1); \

1241

HANDLE_DLINE(DLINE_DL, RIGHTOF_SQUARE, ABOVE_SQUARE, 1, 0); \

1242

HANDLE_DLINE(DLINE_DR, LEFTOF_SQUARE, ABOVE_SQUARE, 0, 0);

1243

1244

#define DOT_DLINES \

1245

HANDLE_DLINE(DLINE_VERT, ABOVE_DOT, BELOW_DOT); \

1246

HANDLE_DLINE(DLINE_HORIZ, LEFTOF_DOT, RIGHTOF_DOT); \

1247

HANDLE_DLINE(DLINE_UL, ABOVE_DOT, LEFTOF_DOT); \

1248

HANDLE_DLINE(DLINE_UR, ABOVE_DOT, RIGHTOF_DOT); \

1249

HANDLE_DLINE(DLINE_DL, BELOW_DOT, LEFTOF_DOT); \

1250

HANDLE_DLINE(DLINE_DR, BELOW_DOT, RIGHTOF_DOT);

1251

1252

static void array_setall(char *array, char from, char to, int len)

1253

{

1254

char *p = array, *p_old = p;

1255

int len_remaining = len;

1256

1257

while ((p = memchr(p, from, len_remaining))) {

1258

*p = to;

1259

len_remaining -= p - p_old;

1260

p_old = p;

1261

}

1262

}

1263

1264

static int dot_setall_dlines(solver_state *sstate, enum dline dl, int i, int j,

1265

enum line_state line_old, enum line_state line_new)

1266

{

1267

game_state *state = sstate->state;

1268

int retval = FALSE;

1269

1270

if (line_old == line_new)

1271

return FALSE;

1272

1273

/* First line in dline */

1274

switch (dl) {

1275

case DLINE_UL:

1276

case DLINE_UR:

1277

case DLINE_VERT:

1278

if (j > 0 && ABOVE_DOT(state, i, j) == line_old) {

1279

LV_ABOVE_DOT(state, i, j) = line_new;

1280

retval = TRUE;

1281

}

1282

break;

1283

case DLINE_DL:

1284

case DLINE_DR:

1285

if (j <= (state)->h && BELOW_DOT(state, i, j) == line_old) {

1286

LV_BELOW_DOT(state, i, j) = line_new;

1287

retval = TRUE;

1288

}

1289

break;

1290

case DLINE_HORIZ:

1291

if (i > 0 && LEFTOF_DOT(state, i, j) == line_old) {

1292

LV_LEFTOF_DOT(state, i, j) = line_new;

1293

retval = TRUE;

1294

}

1295

break;

1296

}

1297

1298

/* Second line in dline */

1299

switch (dl) {

1300

case DLINE_UL:

1301

case DLINE_DL:

1302

if (i > 0 && LEFTOF_DOT(state, i, j) == line_old) {

1303

LV_LEFTOF_DOT(state, i, j) = line_new;

1304

retval = TRUE;

1305

}

1306

break;

1307

case DLINE_UR:

1308

case DLINE_DR:

1309

case DLINE_HORIZ:

1310

if (i <= (state)->w && RIGHTOF_DOT(state, i, j) == line_old) {

1311

LV_RIGHTOF_DOT(state, i, j) = line_new;

1312

retval = TRUE;

1313

}

1314

break;

1315

case DLINE_VERT:

1316

if (j <= (state)->h && BELOW_DOT(state, i, j) == line_old) {

1317

LV_BELOW_DOT(state, i, j) = line_new;

1318

retval = TRUE;

1319

}

1320

break;

1321

}

1322

1323

return retval;

1324

}

1325

1326

#if 0

1327

/* This will fail an assertion if {dx,dy} are anything other than {-1,0}, {1,0}

1328

* {0,-1} or {0,1} */

1329

static int line_status_from_point(const game_state *state,

1330

int x, int y, int dx, int dy)

1331

{

1332

if (dx == -1 && dy == 0)

1333

return LEFTOF_DOT(state, x, y);

1334

if (dx == 1 && dy == 0)

1335

return RIGHTOF_DOT(state, x, y);

1336

if (dx == 0 && dy == -1)

1337

return ABOVE_DOT(state, x, y);

1338

if (dx == 0 && dy == 1)

1339

return BELOW_DOT(state, x, y);

1340

1341

assert(!"Illegal dx or dy in line_status_from_point");

1342

return 0;

1343

}

1344

#endif

1345

1346

/* This will return a dynamically allocated solver_state containing the (more)

1347

* solved grid */

1348

static solver_state *solve_game_rec(const solver_state *sstate_start, int diff)

1349

{

1350

int i, j, w, h;

1351

int current_yes, current_no, desired;

1352

solver_state *sstate, *sstate_saved, *sstate_tmp;

1353

int t;

1354

solver_state *sstate_rec_solved;

1355

int recursive_soln_count;

1356

char *square_solved;

1357

char *dot_solved;

1358

int solver_progress;

1359

1360

h = sstate_start->state->h;

1361

w = sstate_start->state->w;

1362

1363

dot_solved = snewn(DOT_COUNT(sstate_start->state), char);

1364

square_solved = snewn(SQUARE_COUNT(sstate_start->state), char);

1365

memset(dot_solved, FALSE, DOT_COUNT(sstate_start->state));

1366

memset(square_solved, FALSE, SQUARE_COUNT(sstate_start->state));

1367

1368

#if 0

1369

printf("solve_game_rec: recursion_remaining = %d\n",

1370

sstate_start->recursion_remaining);

1371

#endif

1372

1373

sstate = dup_solver_state((solver_state *)sstate_start);

1374

1375

#define FOUND_MISTAKE \

1376

do { \

1377

sstate->solver_status = SOLVER_MISTAKE; \

1378

sfree(dot_solved); sfree(square_solved); \

1379

free_solver_state(sstate_saved); \

1380

return sstate; \

1381

} while (0)

1382

1383

sstate_saved = NULL;

1384

1385

nonrecursive_solver:

1386

1387

while (1) {

1388

solver_progress = FALSE;

1389

1390

/* First we do the 'easy' work, that might cause concrete results */

1391

1392

/* Per-square deductions */

1393

for (j = 0; j < h; ++j) {

1394

for (i = 0; i < w; ++i) {

1395

/* Begin rules that look at the clue (if there is one) */

1396

if (square_solved[i + j*w])

1397

continue;

1398

1399

desired = CLUE_AT(sstate->state, i, j);

1400

if (desired == ' ')

1401

continue;

1402

1403

desired = desired - '0';

1404

current_yes = square_order(sstate->state, i, j, LINE_YES);

1405

current_no = square_order(sstate->state, i, j, LINE_NO);

1406

1407

if (current_yes + current_no == 4) {

1408

square_solved[i + j*w] = TRUE;

1409

continue;

1410

}

1411

1412

if (desired < current_yes)

1413

FOUND_MISTAKE;

1414

if (desired == current_yes) {

1415

square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO);

1416

square_solved[i + j*w] = TRUE;

1417

solver_progress = TRUE;

1418

continue;

1419

}

1420

1421

if (4 - desired < current_no)

1422

FOUND_MISTAKE;

1423

if (4 - desired == current_no) {

1424

square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_YES);

1425

square_solved[i + j*w] = TRUE;

1426

solver_progress = TRUE;

1427

}

1428

}

1429

}

1430

1431

/* Per-dot deductions */

1432

for (j = 0; j < h + 1; ++j) {

1433

for (i = 0; i < w + 1; ++i) {

1434

if (dot_solved[i + j*(w+1)])

1435

continue;

1436

1437

switch (dot_order(sstate->state, i, j, LINE_YES)) {

1438

case 0:

1439

switch (dot_order(sstate->state, i, j, LINE_NO)) {

1440

case 3:

1441

dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO);

1442

solver_progress = TRUE;

1443

/* fall through */

1444

case 4:

1445

dot_solved[i + j*(w+1)] = TRUE;

1446

break;

1447

}

1448

break;

1449

case 1:

1450

switch (dot_order(sstate->state, i, j, LINE_NO)) {

1451

#define H1(dline, dir1_dot, dir2_dot, dot_howmany) \

1452

if (dir1_dot(sstate->state, i, j) == LINE_UNKNOWN) { \

1453

if (dir2_dot(sstate->state, i, j) == LINE_UNKNOWN){ \

1454

solver_progress |= \

1455

SET_BIT(sstate->dot_howmany[i + (w + 1) * j], \

1456

dline); \

1457

} \

1458

}

1459

case 1:

1460

if (diff > DIFF_EASY) {

1461

#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \

1462

H1(dline, dir1_dot, dir2_dot, dot_atleastone)

1463

/* 1 yes, 1 no, so exactly one of unknowns is

1464

* yes */

1465

DOT_DLINES;

1466

#undef HANDLE_DLINE

1467

}

1468

/* fall through */

1469

case 0:

1470

if (diff > DIFF_EASY) {

1471

#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \

1472

H1(dline, dir1_dot, dir2_dot, dot_atmostone)

1473

/* 1 yes, fewer than 2 no, so at most one of

1474

* unknowns is yes */

1475

DOT_DLINES;

1476

#undef HANDLE_DLINE

1477

}

1478

#undef H1

1479

break;

1480

case 2: /* 1 yes, 2 no */

1481

dot_setall(sstate->state, i, j,

1482

LINE_UNKNOWN, LINE_YES);

1483

dot_solved[i + j*(w+1)] = TRUE;

1484

solver_progress = TRUE;

1485

break;

1486

case 3: /* 1 yes, 3 no */

1487

FOUND_MISTAKE;

1488

break;

1489

}

1490

break;

1491

case 2:

1492

if (dot_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_NO)) {

1493

solver_progress = TRUE;

1494

}

1495

dot_solved[i + j*(w+1)] = TRUE;

1496

break;

1497

case 3:

1498

case 4:

1499

FOUND_MISTAKE;

1500

break;

1501

}

1502

if (diff > DIFF_EASY) {

1503

#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \

1504

if (BIT_SET(sstate->dot_atleastone[i + (w + 1) * j], dline)) { \

1505

solver_progress |= \

1506

SET_BIT(sstate->dot_atmostone[i + (w + 1) * j], \

1507

OPP_DLINE(dline)); \

1508

}

1509

/* If at least one of a dline in a dot is YES, at most one

1510

* of the opposite dline to that dot must be YES. */

1511

DOT_DLINES;

1512

}

1513

#undef HANDLE_DLINE

1514

1515

#define H1(dline, dir1_sq, dir2_sq, dot_howmany, line_query, line_set) \

1516

if (BIT_SET(sstate->dot_howmany[i + (w+1) * j], dline)) { \

1517

t = dir1_sq(sstate->state, i, j); \

1518

if (t == line_query) { \

1519

if (dir2_sq(sstate->state, i, j) != line_set) { \

1520

LV_##dir2_sq(sstate->state, i, j) = line_set; \

1521

solver_progress = TRUE; \

1522

} \

1523

} else { \

1524

t = dir2_sq(sstate->state, i, j); \

1525

if (t == line_query) { \

1526

if (dir1_sq(sstate->state, i, j) != line_set) { \

1527

LV_##dir1_sq(sstate->state, i, j) = line_set; \

1528

solver_progress = TRUE; \

1529

} \

1530

} \

1531

} \

1532

}

1533

if (diff > DIFF_EASY) {

1534

#define HANDLE_DLINE(dline, dir1_sq, dir2_sq) \

1535

H1(dline, dir1_sq, dir2_sq, dot_atmostone, LINE_YES, LINE_NO)

1536

/* If at most one of the DLINE is on, and one is definitely

1537

* on, set the other to definitely off */

1538

DOT_DLINES;

1539

#undef HANDLE_DLINE

1540

}

1541

1542

if (diff > DIFF_EASY) {

1543

#define HANDLE_DLINE(dline, dir1_sq, dir2_sq) \

1544

H1(dline, dir1_sq, dir2_sq, dot_atleastone, LINE_NO, LINE_YES)

1545

/* If at least one of the DLINE is on, and one is definitely

1546

* off, set the other to definitely on */

1547

DOT_DLINES;

1548

#undef HANDLE_DLINE

1549

}

1550

#undef H1

1551

1552

}

1553

}

1554

1555

/* More obscure per-square operations */

1556

for (j = 0; j < h; ++j) {

1557

for (i = 0; i < w; ++i) {

1558

if (square_solved[i + j*w])

1559

continue;

1560

1561

switch (CLUE_AT(sstate->state, i, j)) {

1562

case '1':

1563

if (diff > DIFF_EASY) {

1564

#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \

1565

/* At most one of any DLINE can be set */ \

1566

SET_BIT(sstate->dot_atmostone[i+a + (w + 1) * (j+b)], \

1567

dline); \

1568

/* This DLINE provides enough YESes to solve the clue */\

1569

if (BIT_SET(sstate->dot_atleastone \

1570

[i+a + (w + 1) * (j+b)], \

1571

dline)) { \

1572

solver_progress |= \

1573

dot_setall_dlines(sstate, OPP_DLINE(dline), \

1574

i+(1-a), j+(1-b), \

1575

LINE_UNKNOWN, LINE_NO); \

1576

}

1577

SQUARE_DLINES;

1578

#undef HANDLE_DLINE

1579

}

1580

break;

1581

case '2':

1582

if (diff > DIFF_EASY) {

1583

#define H1(dline, dot_at1one, dot_at2one, a, b) \

1584

if (BIT_SET(sstate->dot_at1one \

1585

[i+a + (w+1) * (j+b)], dline)) { \

1586

solver_progress |= \

1587

SET_BIT(sstate->dot_at2one \

1588

[i+(1-a) + (w+1) * (j+(1-b))], \

1589

OPP_DLINE(dline)); \

1590

}

1591

#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \

1592

H1(dline, dot_atleastone, dot_atmostone, a, b); \

1593

H1(dline, dot_atmostone, dot_atleastone, a, b);

1594

/* If at least one of one DLINE is set, at most one

1595

* of the opposing one is and vice versa */

1596

SQUARE_DLINES;

1597

}

1598

#undef HANDLE_DLINE

1599

#undef H1

1600

break;

1601

case '3':

1602

if (diff > DIFF_EASY) {

1603

#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \

1604

/* At least one of any DLINE can be set */ \

1605

solver_progress |= \

1606

SET_BIT(sstate->dot_atleastone \

1607

[i+a + (w + 1) * (j+b)], \

1608

dline); \

1609

/* This DLINE provides enough NOs to solve the clue */ \

1610

if (BIT_SET(sstate->dot_atmostone \

1611

[i+a + (w + 1) * (j+b)], \

1612

dline)) { \

1613

solver_progress |= \

1614

dot_setall_dlines(sstate, OPP_DLINE(dline), \

1615

i+(1-a), j+(1-b), \

1616

LINE_UNKNOWN, LINE_YES); \

1617

}

1618

SQUARE_DLINES;

1619

#undef HANDLE_DLINE

1620

}

1621

break;

1622

}

1623

}

1624

}

1625

1626

if (!solver_progress) {

1627

int edgecount = 0, clues = 0, satclues = 0, sm1clues = 0;

1628

int shortest_chainlen = DOT_COUNT(sstate->state);

1629

int loop_found = FALSE;

1630

int d;

1631

int dots_connected;

1632

1633

/*

1634

* Go through the grid and update for all the new edges.

1635

* Since merge_dots() is idempotent, the simplest way to

1636

* do this is just to update for _all_ the edges.

1637

*

1638

* Also, while we're here, we count the edges, count the

1639

* clues, count the satisfied clues, and count the

1640

* satisfied-minus-one clues.

1641

*/

1642

for (j = 0; j < h+1; ++j) {

1643

for (i = 0; i < w+1; ++i) {

1644

if (RIGHTOF_DOT(sstate->state, i, j) == LINE_YES) {

1645

loop_found |= merge_dots(sstate, i, j, i+1, j);

1646

edgecount++;

1647

}

1648

if (BELOW_DOT(sstate->state, i, j) == LINE_YES) {

1649

loop_found |= merge_dots(sstate, i, j, i, j+1);

1650

edgecount++;

1651

}

1652

1653

if (CLUE_AT(sstate->state, i, j) != ' ') {

1654

int c = CLUE_AT(sstate->state, i, j) - '0';

1655

int o = square_order(sstate->state, i, j, LINE_YES);

1656

if (o == c)

1657

satclues++;

1658

else if (o == c-1)

1659

sm1clues++;

1660

clues++;

1661

}

1662

}

1663

}

1664

1665

for (i = 0; i < DOT_COUNT(sstate->state); ++i) {

1666

dots_connected = sstate->looplen[dsf_canonify(sstate->dotdsf,i)];

1667

if (dots_connected > 1)

1668

shortest_chainlen = min(shortest_chainlen, dots_connected);

1669

}

1670

1671

assert(sstate->solver_status == SOLVER_INCOMPLETE);

1672

1673

if (satclues == clues && shortest_chainlen == edgecount) {

1674

sstate->solver_status = SOLVER_SOLVED;

1675

/* This discovery clearly counts as progress, even if we haven't

1676

* just added any lines or anything */

1677

solver_progress = TRUE;

1678

goto finished_loop_checking;

1679

}

1680

1681

/*

1682

* Now go through looking for LINE_UNKNOWN edges which

1683

* connect two dots that are already in the same

1684

* equivalence class. If we find one, test to see if the

1685

* loop it would create is a solution.

1686

*/

1687

for (j = 0; j <= h; ++j) {

1688

for (i = 0; i <= w; ++i) {

1689

for (d = 0; d < 2; d++) {

1690

int i2, j2, eqclass, val;

1691

1692

if (d == 0) {

1693

if (RIGHTOF_DOT(sstate->state, i, j) !=

1694

LINE_UNKNOWN)

1695

continue;

1696

i2 = i+1;

1697

j2 = j;

1698

} else {

1699

if (BELOW_DOT(sstate->state, i, j) !=

1700

LINE_UNKNOWN)

1701

continue;

1702

i2 = i;

1703

j2 = j+1;

1704

}

1705

1706

eqclass = dsf_canonify(sstate->dotdsf, j * (w+1) + i);

1707

if (eqclass != dsf_canonify(sstate->dotdsf,

1708

j2 * (w+1) + i2))

1709

continue;

1710

1711

val = LINE_NO; /* loop is bad until proven otherwise */

1712

1713

/*

1714

* This edge would form a loop. Next

1715

* question: how long would the loop be?

1716

* Would it equal the total number of edges

1717

* (plus the one we'd be adding if we added

1718

* it)?

1719

*/

1720

if (sstate->looplen[eqclass] == edgecount + 1) {

1721

int sm1_nearby;

1722

int cx, cy;

1723

1724

/*

1725

* This edge would form a loop which

1726

* took in all the edges in the entire

1727

* grid. So now we need to work out

1728

* whether it would be a valid solution

1729

* to the puzzle, which means we have to

1730

* check if it satisfies all the clues.

1731

* This means that every clue must be

1732

* either satisfied or satisfied-minus-

1733

* 1, and also that the number of

1734

* satisfied-minus-1 clues must be at

1735

* most two and they must lie on either

1736

* side of this edge.

1737

*/

1738

sm1_nearby = 0;

1739

cx = i - (j2-j);

1740

cy = j - (i2-i);

1741

if (CLUE_AT(sstate->state, cx,cy) != ' ' &&

1742

square_order(sstate->state, cx,cy, LINE_YES) ==

1743

CLUE_AT(sstate->state, cx,cy) - '0' - 1)

1744

sm1_nearby++;

1745

if (CLUE_AT(sstate->state, i, j) != ' ' &&

1746

square_order(sstate->state, i, j, LINE_YES) ==

1747

CLUE_AT(sstate->state, i, j) - '0' - 1)

1748

sm1_nearby++;

1749

if (sm1clues == sm1_nearby &&

1750

sm1clues + satclues == clues)

1751

val = LINE_YES; /* loop is good! */

1752

}

1753

1754

/*

1755

* Right. Now we know that adding this edge

1756

* would form a loop, and we know whether

1757

* that loop would be a viable solution or

1758

* not.

1759

*

1760

* If adding this edge produces a solution,

1761

* then we know we've found _a_ solution but

1762

* we don't know that it's _the_ solution -

1763

* if it were provably the solution then

1764

* we'd have deduced this edge some time ago

1765

* without the need to do loop detection. So

1766

* in this state we return SOLVER_AMBIGUOUS,

1767

* which has the effect that hitting Solve

1768

* on a user-provided puzzle will fill in a

1769

* solution but using the solver to

1770

* construct new puzzles won't consider this

1771

* a reasonable deduction for the user to

1772

* make.

1773

*/

1774

if (d == 0) {

1775

LV_RIGHTOF_DOT(sstate->state, i, j) = val;

1776

solver_progress = TRUE;

1777

} else {

1778

LV_BELOW_DOT(sstate->state, i, j) = val;

1779

solver_progress = TRUE;

1780

}

1781

if (val == LINE_YES) {

1782

sstate->solver_status = SOLVER_AMBIGUOUS;

1783

goto finished_loop_checking;

1784

}

1785

}

1786

}

1787

}

1788

1789

finished_loop_checking:

1790

1791

if (!solver_progress ||

1792

sstate->solver_status == SOLVER_SOLVED ||

1793

sstate->solver_status == SOLVER_AMBIGUOUS) {

1794

break;

1795

}

1796

}

1797

}

1798

1799

sfree(dot_solved); sfree(square_solved);

1800

1801

if (sstate->solver_status == SOLVER_SOLVED ||

1802

sstate->solver_status == SOLVER_AMBIGUOUS) {

1803

/* s/LINE_UNKNOWN/LINE_NO/g */

1804

array_setall(sstate->state->hl, LINE_UNKNOWN, LINE_NO,

1805

HL_COUNT(sstate->state));

1806

array_setall(sstate->state->vl, LINE_UNKNOWN, LINE_NO,

1807

VL_COUNT(sstate->state));

1808

return sstate;

1809

}

1810

1811

/* Perform recursive calls */

1812

if (sstate->recursion_remaining) {

1813

sstate_saved = dup_solver_state(sstate);

1814

1815

sstate->recursion_remaining--;

1816

1817

recursive_soln_count = 0;

1818

sstate_rec_solved = NULL;

1819

1820

/* Memory management:

1821

* sstate_saved won't be modified but needs to be freed when we have

1822

* finished with it.

1823

* sstate is expected to contain our 'best' solution by the time we

1824

* finish this section of code. It's the thing we'll try adding lines

1825

* to, seeing if they make it more solvable.

1826

* If sstate_rec_solved is non-NULL, it will supersede sstate

1827

* eventually. sstate_tmp should not hold a value persistently.

1828

*/

1829

1830

/* NB SOLVER_AMBIGUOUS is like SOLVER_SOLVED except the solver is aware

1831

* of the possibility of additional solutions. So as soon as we have a

1832

* SOLVER_AMBIGUOUS we can safely propagate it back to our caller, but

1833

* if we get a SOLVER_SOLVED we want to keep trying in case we find

1834

* further solutions and have to mark it ambiguous.

1835

*/

1836

1837

#define DO_RECURSIVE_CALL(dir_dot) \

1838

if (dir_dot(sstate->state, i, j) == LINE_UNKNOWN) { \

1839

debug(("Trying " #dir_dot " at [%d,%d]\n", i, j)); \

1840

LV_##dir_dot(sstate->state, i, j) = LINE_YES; \

1841

sstate_tmp = solve_game_rec(sstate, diff); \

1842

switch (sstate_tmp->solver_status) { \

1843

case SOLVER_AMBIGUOUS: \

1844

debug(("Solver ambiguous, returning\n")); \

1845

sstate_rec_solved = sstate_tmp; \

1846

goto finished_recursion; \

1847

case SOLVER_SOLVED: \

1848

switch (++recursive_soln_count) { \

1849

case 1: \

1850

debug(("One solution found\n")); \

1851

sstate_rec_solved = sstate_tmp; \

1852

break; \

1853

case 2: \

1854

debug(("Ambiguous solutions found\n")); \

1855

free_solver_state(sstate_tmp); \

1856

sstate_rec_solved->solver_status = SOLVER_AMBIGUOUS;\

1857

goto finished_recursion; \

1858

default: \

1859

assert(!"recursive_soln_count out of range"); \

1860

break; \

1861

} \

1862

break; \

1863

case SOLVER_MISTAKE: \

1864

debug(("Non-solution found\n")); \

1865

free_solver_state(sstate_tmp); \

1866

free_solver_state(sstate_saved); \

1867

LV_##dir_dot(sstate->state, i, j) = LINE_NO; \

1868

goto nonrecursive_solver; \

1869

case SOLVER_INCOMPLETE: \

1870

debug(("Recursive step inconclusive\n")); \

1871

free_solver_state(sstate_tmp); \

1872

break; \

1873

} \

1874

free_solver_state(sstate); \

1875

sstate = dup_solver_state(sstate_saved); \

1876

}

1877

1878

for (j = 0; j < h + 1; ++j) {

1879

for (i = 0; i < w + 1; ++i) {

1880

/* Only perform recursive calls on 'loose ends' */

1881

if (dot_order(sstate->state, i, j, LINE_YES) == 1) {

1882

DO_RECURSIVE_CALL(LEFTOF_DOT);

1883

DO_RECURSIVE_CALL(RIGHTOF_DOT);

1884

DO_RECURSIVE_CALL(ABOVE_DOT);

1885

DO_RECURSIVE_CALL(BELOW_DOT);

1886

}

1887

}

1888

}

1889

1890

finished_recursion:

1891

1892

if (sstate_rec_solved) {

1893

free_solver_state(sstate);

1894

sstate = sstate_rec_solved;

1895

}

1896

}

1897

1898

return sstate;

1899

}

1900

1901

/* XXX bits of solver that may come in handy one day */

1902

#if 0

1903

#define HANDLE_DLINE(dline, dir1_dot, dir2_dot) \

1904

/* dline from this dot that's entirely unknown must have

1905

* both lines identical */ \

1906

if (dir1_dot(sstate->state, i, j) == LINE_UNKNOWN && \

1907

dir2_dot(sstate->state, i, j) == LINE_UNKNOWN) { \

1908

sstate->dline_identical[i + (sstate->state->w + 1) * j] |= \

1909

1<<dline; \

1910

} else if (sstate->dline_identical[i +

1911

(sstate->state->w + 1) * j] &\

1912

1<<dline) { \

1913

/* If they're identical and one is known do the obvious

1914

* thing */ \

1915

t = dir1_dot(sstate->state, i, j); \

1916

if (t != LINE_UNKNOWN) \

1917

dir2_dot(sstate->state, i, j) = t; \

1918

else { \

1919

t = dir2_dot(sstate->state, i, j); \

1920

if (t != LINE_UNKNOWN) \

1921

dir1_dot(sstate->state, i, j) = t; \

1922

} \

1923

} \

1924

DOT_DLINES;

1925

#undef HANDLE_DLINE

1926

#endif

1927

1928

#if 0

1929

#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \

1930

if (sstate->dline_identical[i+a + \

1931

(sstate->state->w + 1) * (j+b)] &\

1932

1<<dline) { \

1933

dir1_sq(sstate->state, i, j) = LINE_YES; \

1934

dir2_sq(sstate->state, i, j) = LINE_YES; \

1935

}

1936

/* If two lines are the same they must be on */

1937

SQUARE_DLINES;

1938

#undef HANDLE_DLINE

1939

#endif

1940

1941

1942

#if 0

1943

#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \

1944

if (sstate->dot_atmostone[i+a + (sstate->state->w + 1) * (j+b)] & \

1945

1<<dline) { \

1946

if (square_order(sstate->state, i, j, LINE_UNKNOWN) - 1 == \

1947

CLUE_AT(sstate->state, i, j) - '0') { \

1948

square_setall(sstate->state, i, j, LINE_UNKNOWN, LINE_YES); \

1949

/* XXX the following may overwrite known data! */ \

1950

dir1_sq(sstate->state, i, j) = LINE_UNKNOWN; \

1951

dir2_sq(sstate->state, i, j) = LINE_UNKNOWN; \

1952

} \

1953

}

1954

SQUARE_DLINES;

1955

#undef HANDLE_DLINE

1956

#endif

1957

1958

#if 0

1959

#define HANDLE_DLINE(dline, dir1_sq, dir2_sq, a, b) \

1960

if (sstate->dline_identical[i+a +

1961

(sstate->state->w + 1) * (j+b)] &\

1962

1<<dline) { \

1963

dir1_sq(sstate->state, i, j) = LINE_NO; \

1964

dir2_sq(sstate->state, i, j) = LINE_NO; \

1965

}

1966

/* If two lines are the same they must be off */

1967

SQUARE_DLINES;

1968

#undef HANDLE_DLINE

1969

#endif

1970

1971

static char *solve_game(game_state *state, game_state *currstate,

1972

char *aux, char **error)

1973

{

1974

char *soln = NULL;

1975

solver_state *sstate, *new_sstate;

1976

1977

sstate = new_solver_state(state);

1978

new_sstate = solve_game_rec(sstate, DIFFCOUNT);

1979

1980

if (new_sstate->solver_status == SOLVER_SOLVED) {

1981

soln = encode_solve_move(new_sstate->state);

1982

} else if (new_sstate->solver_status == SOLVER_AMBIGUOUS) {

1983

soln = encode_solve_move(new_sstate->state);

1984

/**error = "Solver found ambiguous solutions"; */

1985

} else {

1986

soln = encode_solve_move(new_sstate->state);

1987

/**error = "Solver failed"; */

1988

}

1989

1990

free_solver_state(new_sstate);

1991

free_solver_state(sstate);

1992

1993

return soln;

1994

}

1995

1996

static char *game_text_format(game_state *state)

1997

{

1998

int i, j;

1999

int len;

2000

char *ret, *rp;

2001

2002

len = (2 * state->w + 2) * (2 * state->h + 1);

2003

rp = ret = snewn(len + 1, char);

2004

2005

#define DRAW_HL \

2006

switch (ABOVE_SQUARE(state, i, j)) { \

2007

case LINE_YES: \

2008

rp += sprintf(rp, " -"); \

2009

break; \

2010

case LINE_NO: \

2011

rp += sprintf(rp, " x"); \

2012

break; \

2013

case LINE_UNKNOWN: \

2014

rp += sprintf(rp, " "); \

2015

break; \

2016

default: \

2017

assert(!"Illegal line state for HL");\

2018

}

2019

2020

#define DRAW_VL \

2021

switch (LEFTOF_SQUARE(state, i, j)) {\

2022

case LINE_YES: \

2023

rp += sprintf(rp, "|"); \

2024

break; \

2025

case LINE_NO: \

2026

rp += sprintf(rp, "x"); \

2027

break; \

2028

case LINE_UNKNOWN: \

2029

rp += sprintf(rp, " "); \

2030

break; \

2031

default: \

2032

assert(!"Illegal line state for VL");\

2033

}

2034

2035

for (j = 0; j < state->h; ++j) {

2036

for (i = 0; i < state->w; ++i) {

2037

DRAW_HL;

2038

}

2039

rp += sprintf(rp, " \n");

2040

for (i = 0; i < state->w; ++i) {

2041

DRAW_VL;

2042

rp += sprintf(rp, "%c", (int)(CLUE_AT(state, i, j)));

2043

}

2044

DRAW_VL;

2045

rp += sprintf(rp, "\n");

2046

}

2047

for (i = 0; i < state->w; ++i) {

2048

DRAW_HL;

2049

}

2050

rp += sprintf(rp, " \n");

2051

2052

assert(strlen(ret) == len);

2053

return ret;

2054

}

2055

2056

static game_ui *new_ui(game_state *state)

2057

{

2058

return NULL;

2059

}

2060

2061

static void free_ui(game_ui *ui)

2062

{

2063

}

2064

2065

static char *encode_ui(game_ui *ui)

2066

{

2067

return NULL;

2068

}

2069

2070

static void decode_ui(game_ui *ui, char *encoding)

2071

{

2072

}

2073

2074

static void game_changed_state(game_ui *ui, game_state *oldstate,

2075

game_state *newstate)

2076

{

2077

}

2078

2079

struct game_drawstate {

2080

int started;

2081

int tilesize, linewidth;

2082

int flashing;

2083

char *hl, *vl;

2084

char *clue_error;

2085

};

2086

2087

static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,

2088

int x, int y, int button)

2089

{

2090

int hl_selected;

2091

int i, j, p, q;

2092

char *ret, buf[80];

2093

char button_char = ' ';

2094

enum line_state old_state;

2095

2096

button &= ~MOD_MASK;

2097

2098

/* Around each line is a diamond-shaped region where points within that

2099

* region are closer to this line than any other. We assume any click

2100

* within a line's diamond was meant for that line. It would all be a lot

2101

* simpler if the / and % operators respected modulo arithmetic properly

2102

* for negative numbers. */

2103

2104

x -= BORDER;

2105

y -= BORDER;

2106

2107

/* Get the coordinates of the square the click was in */

2108

i = (x + TILE_SIZE) / TILE_SIZE - 1;

2109

j = (y + TILE_SIZE) / TILE_SIZE - 1;

2110

2111

/* Get the precise position inside square [i,j] */

2112

p = (x + TILE_SIZE) % TILE_SIZE;

2113

q = (y + TILE_SIZE) % TILE_SIZE;

2114

2115

/* After this bit of magic [i,j] will correspond to the point either above

2116

* or to the left of the line selected */

2117

if (p > q) {

2118

if (TILE_SIZE - p > q) {

2119

hl_selected = TRUE;

2120

} else {

2121

hl_selected = FALSE;

2122

++i;

2123

}

2124

} else {

2125

if (TILE_SIZE - q > p) {

2126

hl_selected = FALSE;

2127

} else {

2128

hl_selected = TRUE;

2129

++j;

2130

}

2131

}

2132

2133

if (i < 0 || j < 0)

2134

return NULL;

2135

2136

if (hl_selected) {

2137

if (i >= state->w || j >= state->h + 1)

2138

return NULL;

2139

} else {

2140

if (i >= state->w + 1 || j >= state->h)

2141

return NULL;

2142

}

2143

2144

/* I think it's only possible to play this game with mouse clicks, sorry */

2145

/* Maybe will add mouse drag support some time */

2146

if (hl_selected)

2147

old_state = RIGHTOF_DOT(state, i, j);

2148

else

2149

old_state = BELOW_DOT(state, i, j);

2150

2151

switch (button) {

2152

case LEFT_BUTTON:

2153

switch (old_state) {

2154

case LINE_UNKNOWN:

2155

button_char = 'y';

2156

break;

2157

case LINE_YES:

2158

case LINE_NO:

2159

button_char = 'u';

2160

break;

2161

}

2162

break;

2163

case MIDDLE_BUTTON:

2164

button_char = 'u';

2165

break;

2166

case RIGHT_BUTTON:

2167

switch (old_state) {

2168

case LINE_UNKNOWN:

2169

button_char = 'n';

2170

break;

2171

case LINE_NO:

2172

case LINE_YES:

2173

button_char = 'u';

2174

break;

2175

}

2176

break;

2177

default:

2178

return NULL;

2179

}

2180

2181

2182

sprintf(buf, "%d,%d%c%c", i, j, (int)(hl_selected ? 'h' : 'v'), (int)button_char);

2183

ret = dupstr(buf);

2184

2185

return ret;

2186

}

2187

2188

static game_state *execute_move(game_state *state, char *move)

2189

{

2190

int i, j;

2191

game_state *newstate = dup_game(state);

2192

2193

if (move[0] == 'S') {

2194

move++;

2195

newstate->cheated = TRUE;

2196

}

2197

2198

while (*move) {

2199

i = atoi(move);

2200

move = strchr(move, ',');

2201

if (!move)

2202

goto fail;

2203

j = atoi(++move);

2204

move += strspn(move, "1234567890");

2205

switch (*(move++)) {

2206

case 'h':

2207

if (i >= newstate->w || j > newstate->h)

2208

goto fail;

2209

switch (*(move++)) {

2210

case 'y':

2211

LV_RIGHTOF_DOT(newstate, i, j) = LINE_YES;

2212

break;

2213

case 'n':

2214

LV_RIGHTOF_DOT(newstate, i, j) = LINE_NO;

2215

break;

2216

case 'u':

2217

LV_RIGHTOF_DOT(newstate, i, j) = LINE_UNKNOWN;

2218

break;

2219

default:

2220

goto fail;

2221

}

2222

break;

2223

case 'v':

2224

if (i > newstate->w || j >= newstate->h)

2225

goto fail;

2226

switch (*(move++)) {

2227

case 'y':

2228

LV_BELOW_DOT(newstate, i, j) = LINE_YES;

2229

break;

2230

case 'n':

2231

LV_BELOW_DOT(newstate, i, j) = LINE_NO;

2232

break;

2233

case 'u':

2234

LV_BELOW_DOT(newstate, i, j) = LINE_UNKNOWN;

2235

break;

2236

default:

2237

goto fail;

2238

}

2239

break;

2240

default:

2241

goto fail;

2242

}

2243

}

2244

2245

/*

2246

* Check for completion.

2247

*/

2248

i = 0; /* placate optimiser */

2249

for (j = 0; j <= newstate->h; j++) {

2250

for (i = 0; i < newstate->w; i++)

2251

if (LV_RIGHTOF_DOT(newstate, i, j) == LINE_YES)

2252

break;

2253

if (i < newstate->w)

2254

break;

2255

}

2256

if (j <= newstate->h) {

2257

int prevdir = 'R';

2258

int x = i, y = j;

2259

int looplen, count;

2260

2261

/*

2262

* We've found a horizontal edge at (i,j). Follow it round

2263

* to see if it's part of a loop.

2264

*/

2265

looplen = 0;

2266

while (1) {

2267

int order = dot_order(newstate, x, y, LINE_YES);

2268

if (order != 2)

2269

goto completion_check_done;

2270

2271

if (LEFTOF_DOT(newstate, x, y) == LINE_YES && prevdir != 'L') {

2272

x--;

2273

prevdir = 'R';

2274

} else if (RIGHTOF_DOT(newstate, x, y) == LINE_YES &&

2275

prevdir != 'R') {

2276

x++;

2277

prevdir = 'L';

2278

} else if (ABOVE_DOT(newstate, x, y) == LINE_YES &&

2279

prevdir != 'U') {

2280

y--;

2281

prevdir = 'D';

2282

} else if (BELOW_DOT(newstate, x, y) == LINE_YES &&

2283

prevdir != 'D') {

2284

y++;

2285

prevdir = 'U';

2286

} else {

2287

assert(!"Can't happen"); /* dot_order guarantees success */

2288

}

2289

2290

looplen++;

2291

2292

if (x == i && y == j)

2293

break;

2294

}

2295

2296

if (x != i || y != j || looplen == 0)

2297

goto completion_check_done;

2298

2299

/*

2300

* We've traced our way round a loop, and we know how many

2301

* line segments were involved. Count _all_ the line

2302

* segments in the grid, to see if the loop includes them

2303

* all.

2304

*/

2305

count = 0;

2306

for (j = 0; j <= newstate->h; j++)

2307

for (i = 0; i <= newstate->w; i++)

2308

count += ((RIGHTOF_DOT(newstate, i, j) == LINE_YES) +

2309

(BELOW_DOT(newstate, i, j) == LINE_YES));

2310

assert(count >= looplen);

2311

if (count != looplen)

2312

goto completion_check_done;

2313

2314

/*

2315

* The grid contains one closed loop and nothing else.

2316

* Check that all the clues are satisfied.

2317

*/

2318

for (j = 0; j < newstate->h; ++j) {

2319

for (i = 0; i < newstate->w; ++i) {

2320

int n = CLUE_AT(newstate, i, j);

2321

if (n != ' ') {

2322

if (square_order(newstate, i, j, LINE_YES) != n - '0') {

2323

goto completion_check_done;

2324

}

2325

}

2326

}

2327

}

2328

2329

/*

2330

* Completed!

2331

*/

2332

newstate->solved = TRUE;

2333

}

2334

2335

completion_check_done:

2336

return newstate;

2337

2338

fail:

2339

free_game(newstate);

2340

return NULL;

2341

}

2342

2343

/* ----------------------------------------------------------------------

2344

* Drawing routines.

2345

*/

2346

2347

#define SIZE(d) ((d) * TILE_SIZE + 2 * BORDER + 1)

2348

2349

static void game_compute_size(game_params *params, int tilesize,

2350

int *x, int *y)

2351

{

2352

struct { int tilesize; } ads, *ds = &ads;

2353

ads.tilesize = tilesize;

2354

2355

*x = SIZE(params->w);

2356

*y = SIZE(params->h);

2357

}

2358

2359

static void game_set_size(drawing *dr, game_drawstate *ds,

2360

game_params *params, int tilesize)

2361

{

2362

ds->tilesize = tilesize;

2363

ds->linewidth = max(1,tilesize/16);

2364

}

2365

2366

static float *game_colours(frontend *fe, int *ncolours)

2367

{

2368

float *ret = snewn(4 * NCOLOURS, float);

2369

2370

frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);

2371

2372

ret[COL_FOREGROUND * 3 + 0] = 0.0F;

2373

ret[COL_FOREGROUND * 3 + 1] = 0.0F;

2374

ret[COL_FOREGROUND * 3 + 2] = 0.0F;

2375

2376

ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;

2377

ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;

2378

ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;

2379

2380

ret[COL_MISTAKE * 3 + 0] = 1.0F;

2381

ret[COL_MISTAKE * 3 + 1] = 0.0F;

2382

ret[COL_MISTAKE * 3 + 2] = 0.0F;

2383

2384

*ncolours = NCOLOURS;

2385

return ret;

2386

}

2387

2388

static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)

2389

{

2390

struct game_drawstate *ds = snew(struct game_drawstate);

2391

2392

ds->tilesize = ds->linewidth = 0;

2393

ds->started = 0;

2394

ds->hl = snewn(HL_COUNT(state), char);

2395

ds->vl = snewn(VL_COUNT(state), char);

2396

ds->clue_error = snewn(SQUARE_COUNT(state), char);

2397

ds->flashing = 0;

2398

2399

memset(ds->hl, LINE_UNKNOWN, HL_COUNT(state));

2400

memset(ds->vl, LINE_UNKNOWN, VL_COUNT(state));

2401

memset(ds->clue_error, 0, SQUARE_COUNT(state));

2402

2403

return ds;

2404

}

2405

2406

static void game_free_drawstate(drawing *dr, game_drawstate *ds)

2407

{

2408

sfree(ds->clue_error);

2409

sfree(ds->hl);

2410

sfree(ds->vl);

2411

sfree(ds);

2412

}

2413

2414

static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,

2415

game_state *state, int dir, game_ui *ui,

2416

float animtime, float flashtime)

2417

{

2418

int i, j, n;

2419

int w = state->w, h = state->h;

2420

char c[2];

2421

int line_colour, flash_changed;

2422

int clue_mistake;

2423

2424

if (!ds->started) {

2425

/*

2426

* The initial contents of the window are not guaranteed and

2427

* can vary with front ends. To be on the safe side, all games

2428

* should start by drawing a big background-colour rectangle

2429

* covering the whole window.

2430

*/

2431

draw_rect(dr, 0, 0, SIZE(state->w), SIZE(state->h), COL_BACKGROUND);

2432

2433

/* Draw dots */

2434

for (j = 0; j < h + 1; ++j) {

2435

for (i = 0; i < w + 1; ++i) {

2436

draw_rect(dr,

2437

BORDER + i * TILE_SIZE - LINEWIDTH/2,

2438

BORDER + j * TILE_SIZE - LINEWIDTH/2,

2439

LINEWIDTH, LINEWIDTH, COL_FOREGROUND);

2440

}

2441

}

2442

2443

/* Draw clues */

2444

for (j = 0; j < h; ++j) {

2445

for (i = 0; i < w; ++i) {

2446

c[0] = CLUE_AT(state, i, j);

2447

c[1] = '\0';

2448

draw_text(dr,

2449

BORDER + i * TILE_SIZE + TILE_SIZE/2,

2450

BORDER + j * TILE_SIZE + TILE_SIZE/2,

2451

FONT_VARIABLE, TILE_SIZE/2,

2452

ALIGN_VCENTRE | ALIGN_HCENTRE, COL_FOREGROUND, c);

2453

}

2454

}

2455

draw_update(dr, 0, 0,

2456

state->w * TILE_SIZE + 2*BORDER + 1,

2457

state->h * TILE_SIZE + 2*BORDER + 1);

2458

ds->started = TRUE;

2459

}

2460

2461

if (flashtime > 0 &&

2462

(flashtime <= FLASH_TIME/3 ||

2463

flashtime >= FLASH_TIME*2/3)) {

2464

flash_changed = !ds->flashing;

2465

ds->flashing = TRUE;

2466

line_colour = COL_HIGHLIGHT;

2467

} else {

2468

flash_changed = ds->flashing;

2469

ds->flashing = FALSE;

2470

line_colour = COL_FOREGROUND;

2471

}

2472

2473

#define CROSS_SIZE (3 * LINEWIDTH / 2)

2474

2475

/* Redraw clue colours if necessary */

2476

for (j = 0; j < h; ++j) {

2477

for (i = 0; i < w; ++i) {

2478

c[0] = CLUE_AT(state, i, j);

2479

c[1] = '\0';

2480

if (c[0] == ' ')

2481

continue;

2482

2483

n = c[0] - '0';

2484

assert(n >= 0 && n <= 4);

2485

2486

clue_mistake = (square_order(state, i, j, LINE_YES) > n ||

2487

square_order(state, i, j, LINE_NO ) > (4-n));

2488

2489

if (clue_mistake != ds->clue_error[j * w + i]) {

2490

draw_rect(dr,

2491

BORDER + i * TILE_SIZE + CROSS_SIZE,

2492

BORDER + j * TILE_SIZE + CROSS_SIZE,

2493

TILE_SIZE - CROSS_SIZE * 2, TILE_SIZE - CROSS_SIZE * 2,

2494

COL_BACKGROUND);

2495

draw_text(dr,

2496

BORDER + i * TILE_SIZE + TILE_SIZE/2,

2497

BORDER + j * TILE_SIZE + TILE_SIZE/2,

2498

FONT_VARIABLE, TILE_SIZE/2,

2499

ALIGN_VCENTRE | ALIGN_HCENTRE,

2500

clue_mistake ? COL_MISTAKE : COL_FOREGROUND, c);

2501

draw_update(dr, i * TILE_SIZE + BORDER, j * TILE_SIZE + BORDER,

2502

TILE_SIZE, TILE_SIZE);

2503

2504

ds->clue_error[j * w + i] = clue_mistake;

2505

}

2506

}

2507

}

2508

2509

/* I've also had a request to colour lines red if they make a non-solution

2510

* loop, or if more than two lines go into any point. I think that would

2511

* be good some time. */

2512

2513

#define CLEAR_VL(i, j) do { \

2514

draw_rect(dr, \

2515

BORDER + i * TILE_SIZE - CROSS_SIZE, \

2516

BORDER + j * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, \

2517

CROSS_SIZE * 2, \

2518

TILE_SIZE - LINEWIDTH, \

2519

COL_BACKGROUND); \

2520

draw_update(dr, \

2521

BORDER + i * TILE_SIZE - CROSS_SIZE, \

2522

BORDER + j * TILE_SIZE - CROSS_SIZE, \

2523

CROSS_SIZE*2, \

2524

TILE_SIZE + CROSS_SIZE*2); \

2525

} while (0)

2526

2527

#define CLEAR_HL(i, j) do { \

2528

draw_rect(dr, \

2529

BORDER + i * TILE_SIZE + LINEWIDTH - LINEWIDTH/2, \

2530

BORDER + j * TILE_SIZE - CROSS_SIZE, \

2531

TILE_SIZE - LINEWIDTH, \

2532

CROSS_SIZE * 2, \

2533

COL_BACKGROUND); \

2534

draw_update(dr, \

2535

BORDER + i * TILE_SIZE - CROSS_SIZE, \

2536

BORDER + j * TILE_SIZE - CROSS_SIZE, \

2537

TILE_SIZE + CROSS_SIZE*2, \

2538

CROSS_SIZE*2); \

2539

} while (0)

2540

2541

/* Vertical lines */

2542

for (j = 0; j < h; ++j) {

2543

for (i = 0; i < w + 1; ++i) {

2544

switch (BELOW_DOT(state, i, j)) {

2545

case LINE_UNKNOWN:

2546

if (ds->vl[i + (w + 1) * j] != BELOW_DOT(state, i, j)) {

2547

CLEAR_VL(i, j);

2548

}

2549

break;

2550

case LINE_YES:

2551

if (ds->vl[i + (w + 1) * j] != BELOW_DOT(state, i, j) ||

2552

flash_changed) {

2553

CLEAR_VL(i, j);

2554

draw_rect(dr,

2555

BORDER + i * TILE_SIZE - LINEWIDTH/2,

2556

BORDER + j * TILE_SIZE + LINEWIDTH - LINEWIDTH/2,

2557

LINEWIDTH, TILE_SIZE - LINEWIDTH,

2558

line_colour);

2559

}

2560

break;

2561

case LINE_NO:

2562

if (ds->vl[i + (w + 1) * j] != BELOW_DOT(state, i, j)) {

2563

CLEAR_VL(i, j);

2564

draw_line(dr,

2565

BORDER + i * TILE_SIZE - CROSS_SIZE,

2566

BORDER + j * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE,

2567

BORDER + i * TILE_SIZE + CROSS_SIZE - 1,

2568

BORDER + j * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1,

2569

COL_FOREGROUND);

2570

draw_line(dr,

2571

BORDER + i * TILE_SIZE + CROSS_SIZE - 1,

2572

BORDER + j * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE,

2573

BORDER + i * TILE_SIZE - CROSS_SIZE,

2574

BORDER + j * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1,

2575

COL_FOREGROUND);

2576

}

2577

break;

2578

}

2579

ds->vl[i + (w + 1) * j] = BELOW_DOT(state, i, j);

2580

}

2581

}

2582

2583

/* Horizontal lines */

2584

for (j = 0; j < h + 1; ++j) {

2585

for (i = 0; i < w; ++i) {

2586

switch (RIGHTOF_DOT(state, i, j)) {

2587

case LINE_UNKNOWN:

2588

if (ds->hl[i + w * j] != RIGHTOF_DOT(state, i, j)) {

2589

CLEAR_HL(i, j);

2590

}

2591

break;

2592

case LINE_YES:

2593

if (ds->hl[i + w * j] != RIGHTOF_DOT(state, i, j) ||

2594

flash_changed) {

2595

CLEAR_HL(i, j);

2596

draw_rect(dr,

2597

BORDER + i * TILE_SIZE + LINEWIDTH - LINEWIDTH/2,

2598

BORDER + j * TILE_SIZE - LINEWIDTH/2,

2599

TILE_SIZE - LINEWIDTH, LINEWIDTH,

2600

line_colour);

2601

break;

2602

}

2603

case LINE_NO:

2604

if (ds->hl[i + w * j] != RIGHTOF_DOT(state, i, j)) {

2605

CLEAR_HL(i, j);

2606

draw_line(dr,

2607

BORDER + i * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE,

2608

BORDER + j * TILE_SIZE + CROSS_SIZE - 1,

2609

BORDER + i * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1,

2610

BORDER + j * TILE_SIZE - CROSS_SIZE,

2611

COL_FOREGROUND);

2612

draw_line(dr,

2613

BORDER + i * TILE_SIZE + TILE_SIZE/2 - CROSS_SIZE,

2614

BORDER + j * TILE_SIZE - CROSS_SIZE,

2615

BORDER + i * TILE_SIZE + TILE_SIZE/2 + CROSS_SIZE - 1,

2616

BORDER + j * TILE_SIZE + CROSS_SIZE - 1,

2617

COL_FOREGROUND);

2618

break;

2619

}

2620

}

2621

ds->hl[i + w * j] = RIGHTOF_DOT(state, i, j);

2622

}

2623

}

2624

}

2625

2626

static float game_anim_length(game_state *oldstate, game_state *newstate,

2627

int dir, game_ui *ui)

2628

{

2629

return 0.0F;

2630

}

2631

2632

static float game_flash_length(game_state *oldstate, game_state *newstate,

2633

int dir, game_ui *ui)

2634

{

2635

if (!oldstate->solved && newstate->solved &&

2636

!oldstate->cheated && !newstate->cheated) {

2637

return FLASH_TIME;

2638

}

2639

2640

return 0.0F;

2641

}

2642

2643

static int game_timing_state(game_state *state, game_ui *ui)

2644

{

2645

return TRUE;

2646

}

2647

2648

static void game_print_size(game_params *params, float *x, float *y)

2649

{

2650

int pw, ph;

2651

2652

/*

2653

* I'll use 7mm squares by default.

2654

*/

2655

game_compute_size(params, 700, &pw, &ph);

2656

*x = pw / 100.0F;

2657

*y = ph / 100.0F;

2658

}

2659

2660

static void game_print(drawing *dr, game_state *state, int tilesize)

2661

{

2662

int w = state->w, h = state->h;

2663

int ink = print_mono_colour(dr, 0);

2664

int x, y;

2665

game_drawstate ads, *ds = &ads;

2666

2667

game_set_size(dr, ds, NULL, tilesize);

2668

2669

/*

2670

* Dots. I'll deliberately make the dots a bit wider than the

2671

* lines, so you can still see them. (And also because it's

2672

* annoyingly tricky to make them _exactly_ the same size...)

2673

*/

2674

for (y = 0; y <= h; y++)

2675

for (x = 0; x <= w; x++)

2676

draw_circle(dr, BORDER + x * TILE_SIZE, BORDER + y * TILE_SIZE,

2677

LINEWIDTH, ink, ink);

2678

2679

/*

2680

* Clues.

2681

*/

2682

for (y = 0; y < h; y++)

2683

for (x = 0; x < w; x++)

2684

if (CLUE_AT(state, x, y) != ' ') {

2685

char c[2];

2686

2687

c[0] = CLUE_AT(state, x, y);

2688

c[1] = '\0';

2689

draw_text(dr,

2690

BORDER + x * TILE_SIZE + TILE_SIZE/2,

2691

BORDER + y * TILE_SIZE + TILE_SIZE/2,

2692

FONT_VARIABLE, TILE_SIZE/2,

2693

ALIGN_VCENTRE | ALIGN_HCENTRE, ink, c);

2694

}

2695

2696

/*

2697

* Lines. (At the moment, I'm not bothering with crosses.)

2698

*/

2699

for (y = 0; y <= h; y++)

2700

for (x = 0; x < w; x++)

2701

if (RIGHTOF_DOT(state, x, y) == LINE_YES)

2702

draw_rect(dr, BORDER + x * TILE_SIZE,

2703

BORDER + y * TILE_SIZE - LINEWIDTH/2,

2704

TILE_SIZE, (LINEWIDTH/2) * 2 + 1, ink);

2705

for (y = 0; y < h; y++)

2706

for (x = 0; x <= w; x++)

2707

if (BELOW_DOT(state, x, y) == LINE_YES)

2708

draw_rect(dr, BORDER + x * TILE_SIZE - LINEWIDTH/2,

2709

BORDER + y * TILE_SIZE,

2710

(LINEWIDTH/2) * 2 + 1, TILE_SIZE, ink);

2711

}

2712

2713

#ifdef COMBINED

2714

#define thegame loopy

2715

#endif

2716

2717

const struct game thegame = {

2718

"Loopy", "games.loopy",

2719

default_params,

2720

game_fetch_preset,

2721

decode_params,

2722

encode_params,

2723

free_params,

2724

dup_params,

2725

TRUE, game_configure, custom_params,

2726

validate_params,

2727

new_game_desc,

2728

validate_desc,

2729

new_game,

2730

dup_game,

2731

free_game,

2732

1, solve_game,

2733

TRUE, game_text_format,

2734

new_ui,

2735

free_ui,

2736

encode_ui,

2737

decode_ui,

2738

game_changed_state,

2739

interpret_move,

2740

execute_move,

2741

PREFERRED_TILE_SIZE, game_compute_size, game_set_size,

2742

game_colours,

2743

game_new_drawstate,

2744

game_free_drawstate,

2745

game_redraw,

2746

game_anim_length,

2747

game_flash_length,

2748

TRUE, FALSE, game_print_size, game_print,

2749

FALSE, /* wants_statusbar */

2750

FALSE, game_timing_state,

2751

0, /* flags */

2752

};