| dodo
| | Joined: 11 Jul 2005 | | Posts: 5 | | : | |
Items |
|
 Posted: Wed Jul 13, 2005 7:41 am Post subject: Polynomial complexity, instead of NP-hard? |
 |
|
In a neighboring thread within "Programming SuDoKu", I outlined (as of July 11) a VB computer program which used intersections of sets (represented as bitmap AND operations) to narrow down a backtracking search. While this is nothing more than a programming device, I believe it holds the seed for an analysis of the game of some interest.
I'm using as a case example (again) Nick70's "48-Unwind" problem (not being a SuDoKu player myself, I'm not fluent with the lingo, but I'm quoting it for your benefit). In any case, the puzzle is:
| Code: | . . . . . 3 . 6 .
. . . . . . . 1 .
. 9 7 5 . . . 8 .
. . . . 9 . 2 . .
. . 8 . 7 . 4 . .
. . 3 . 6 . . . .
. 1 . . . 2 8 9 .
. 4 . . . . . . .
. 5 . 1 . . . . . |
with starting position
| Code: | 12458 28 1245 24789 1248 -- 579 -- 24579
234568 2368 2456 246789 248 46789 3579 -- 234579
12346 -- -- -- 124 146 -- -- 234
14567 67 1456 348 -- 1458 -- 357 135678
12569 26 -- 23 -- 15 -- 35 13569
124579 27 -- 248 -- 1458 1579 57 15789
367 -- -- 3467 345 -- -- -- 34567
236789 -- 269 36789 358 56789 13567 2357 123567
236789 -- 269 -- 348 46789 367 2347 23467 |
where "--" represents already solved cells (initial givens plus initially forced moves), which won't play part in the analysis that follows.
Now, this is the point where a search procedure would begin to set backtrack points (or a novice human player, to settle her mood for trial & error). I'd like to call the attention towards the following kind of reduction.
The starting position above shows the set of candidates for each individual position. Now, if you begin to consider sets of candidates for ordered pairs (or n-tuples) of positions, you can progressively reduce further.
For instance, take cells [7,2] and [8,2] (0-based indexes), near the lower mid-left of the board, the ones with candidate sets 269 and 269. Call the cells A and B, and their respective candidate sets, S(A)=269 and S(B)=269.
And now consider the candidate set of the ordered pair (A,B), which is actually smaller than the cartesian product S(A) x S(B): in other words, a combined solution for the two cells yield the set of possible values for the (A,B) pair, S(A,B) = (2,6), (2,9), (6,2), (6,9), (9,2) and (9,6), but certainly not (2,2), (6,6) or (9,9), since they share column (and 3x3 square).
If you add the cell to the immediate right of A (call it cell C), the one with S(C)=36789, and enumerate the candidate set for the triplet (A,B,C), you get S(A,B,C) =
| Code: | (2,6,3), (2,6,6), (2,6,7), (2,6,8), (2,6,9)
(2,9,3), (2,9,6), (2,9,7), (2,9,8), (2,9,9)
(6,2,3), (6,2,7), (6,2,8), (6,2,9)
(6,9,3), (6,9,7), (6,9,8), (6,9,9)
(9,2,3), (9,2,6), (9,2,7), (9,2,8)
(9,6,3), (9,6,6), (9,6,7), (9,6,8) |
since cell C can't share values with A (though it doesn't constrain B).
While it seems this set is going huge by the minute, consider (a) that in the end it'll only have one member, when all cells have been added (since the puzzle has a single solution); and (b), that as cells are added, particular cells will gradually 'lock' themselves to a single value (same digit for a particular ordinate in all ordered pairs), being all of them locked in the final solution. As this proceeds, locked cells can simply be marked as "--" as on start, its redundant ordinate removed from all pairs, and forgotten.
This is hardly a base for a handy method to solve the puzzle; it'll be awkward even for a computer. However, the storage used, while big, can theoretically be bounded in size. What strikes me most is that the cost of the procedure is polynomial, I'd say O(n^3). Doesn't this contradict the idea of the puzzle being NP-hard?
---------
P.S., five minutes later: Oh well, while the storage size is bounded, it'll probably be bounded to a non-polynomial size. I've probably rushed. I suppose the whole beauty of the game is to find the sequence of grouping that keeps this set small. |
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
