Play Sudoku ?
Play Sudoku ?Search Google "Sudoku" To know the rule.
Always 1 2 3 4 5 6 7 8 9 in line and column.
Have fun !
[[i] 本帖最后由 FreddyMusic 于 2007-8-7 15:09 编辑 [/i]] Puzzles for Programmers and Pros Dennis E. Shasha
[table=98%][tr][td][url=mk:@MSITStore:C:\Documents%20and%20Settings\wf\My%20Documents\Wrox.Puzzles.for.Programmers.and.Pros.May.2007.chm::/final/BBL0040.html][img=60,17]mk:@MSITStore:C:\Documents%20and%20Settings\wf\My%20Documents\Wrox.Puzzles.for.Programmers.and.Pros.May.2007.chm::/final/images/prev.gif[/img][/url]
[td][url=mk:@MSITStore:C:\Documents%20and%20Settings\wf\My%20Documents\Wrox.Puzzles.for.Programmers.and.Pros.May.2007.chm::/final/BBL0042.html][img=60,17]mk:@MSITStore:C:\Documents%20and%20Settings\wf\My%20Documents\Wrox.Puzzles.for.Programmers.and.Pros.May.2007.chm::/final/images/next.gif[/img][/url]
[/td][/tr][/table]
This routine works not only for easy Sudokus, but it is also the workhorse for the harder ones. Hard Sudokus require speculation and therefore the test for the inconsistent case when the speculation doesn’t work out. An inconsistency might arise, for example, when the row and the column of an entry together already include all numbers between 1 and 9.
How does speculation work? Let’s start with the intuition. Assume that we have a consistent state to begin with. We call basicsud. If this leads to a complete state (one with every blank/zero entry replaced by a number), then we are done. If we reach a point where every blank entry has two or more possible values, we systematically try the possible values for each entry. That is, for each current blank, we will save the current state, and then try one of its values. If that attempt (or speculation) leads to an inconsistent state, then restore the state before the speculation and try another value.
The pseudo-code (specsud) makes use of a stack in which we save states as we go. When we’re about to speculate, we push a state onto the stack. If the speculation doesn’t work, we pop the top state from the stack.
proc specsud(state s) s':= basicsud(s) if s' == "inconsistent state" then return "inconsistent state" end if if s' is complete then return s' else let R be the entries in s' having two or more possible values for each entry e in R let V be the possible values for e for each value v in V push s' on the stack of saved states s'':= s' with the assignment of v to e s''':= specsud(s'') if s''' is complete then return s''' end if pop s' end for end for end ifend proc specsud
This algorithm is easy to program in almost every language and the resulting code runs in less than a second. See if you can solve the following problem in three seconds or less on a late-model personal computer. The 103-character program I referred to above takes under 100 milliseconds, but this is not a race. Really. It’s not.
[list=1][*]Find the solution to this Sudoku.
[/list][table][tr][td]0
[/td][td]3
[/td][td]0
[/td][td]0
[/td][td]0
[/td][td]0
[/td][td]0
[/td][td]4
[/td][td]0
[/td][/tr][tr][td]0
[/td][td]1
[/td][td]0
[/td][td]0
[/td][td]9
[/td][td]7
[/td][td]0
[/td][td]5
[/td][td]0
[/td][/tr][tr][td]0
[/td][td]0
[/td][td]2
[/td][td]5
[/td][td]0
[/td][td]8
[/td][td]6
[/td][td]0
[/td][td]0
[/td][/tr][tr][td]0
[/td][td]0
[/td][td]3
[/td][td]0
[/td][td]0
[/td][td]0
[/td][td]8
[/td][td]0
[/td][td]0
[/td][/tr][tr][td]9
[/td][td]0
[/td][td]0
[/td][td]0
[/td][td]0
[/td][td]4
[/td][td]3
[/td][td]0
[/td][td]0
[/td][/tr][tr][td]0
[/td][td]0
[/td][td]7
[/td][td]6
[/td][td]0
[/td][td]0
[/td][td]0
[/td][td]0
[/td][td]4
[/td][/tr][tr][td]0
[/td][td]0
[/td][td]9
[/td][td]8
[/td][td]0
[/td][td]5
[/td][td]4
[/td][td]0
[/td][td]0
[/td][/tr][tr][td]0
[/td][td]7
[/td][td]0
[/td][td]0
[/td][td]0
[/td][td]0
[/td][td]0
[/td][td]2
[/td][td]0
[/td][/tr][tr][td]0
[/td][td]5
[/td][td]0
[/td][td]0
[/td][td]7
[/td][td]1
[/td][td]0
[/td][td]8
[/td][td]0
[/td][/tr][/table][url=][img=13,11]mk:@MSITStore:C:\Documents%20and%20Settings\wf\My%20Documents\Wrox.Puzzles.for.Programmers.and.Pros.May.2007.chm::/final/images/b24-bluearrow.gif[/img] Open table as spreadsheet[/url]
Solution to Sudoku[list=1][*][b]Find the solution to this Sudoku.[/b]
[/list]Here is the solution to the challenging Sudoku. I simply programmed the solver I outlined in pseudo-code. There are remarkably few backtracks - under 50.
[table][tr][td]8
[/td][td]3
[/td][td]5
[/td][td]1
[/td][td]2
[/td][td]6
[/td][td]7
[/td][td]4
[/td][td]9
[/td][/tr][tr][td]4
[/td][td]1
[/td][td]6
[/td][td]3
[/td][td]9
[/td][td]7
[/td][td]2
[/td][td]5
[/td][td]8
[/td][/tr][tr][td]7
[/td][td]9
[/td][td]2
[/td][td]5
[/td][td]4
[/td][td]8
[/td][td]6
[/td][td]3
[/td][td]1
[/td][/tr][tr][td]6
[/td][td]4
[/td][td]3
[/td][td]9
[/td][td]1
[/td][td]2
[/td][td]8
[/td][td]7
[/td][td]5
[/td][/tr][tr][td]9
[/td][td]8
[/td][td]1
[/td][td]7
[/td][td]5
[/td][td]4
[/td][td]3
[/td][td]6
[/td][td]2
[/td][/tr][tr][td]5
[/td][td]2
[/td][td]7
[/td][td]6
[/td][td]8
[/td][td]3
[/td][td]1
[/td][td]9
[/td][td]4
[/td][/tr][tr][td]2
[/td][td]6
[/td][td]9
[/td][td]8
[/td][td]3
[/td][td]5
[/td][td]4
[/td][td]1
[/td][td]7
[/td][/tr][tr][td]1
[/td][td]7
[/td][td]8
[/td][td]4
[/td][td]6
[/td][td]9
[/td][td]5
[/td][td]2
[/td][td]3
[/td][/tr][tr][td]3
[/td][td]5
[/td][td]4
[/td][td]2
[/td][td]7
[/td][td]1
[/td][td]9
[/td][td]8
[/td][td]6
[/td][/tr][/table][url=][img=13,11]mk:@MSITStore:C:\Documents%20and%20Settings\wf\My%20Documents\Wrox.Puzzles.for.Programmers.and.Pros.May.2007.chm::/final/images/b24-bluearrow.gif[/img] Open table as spreadsheet[/url]
Incidentally, the following Sudoku variant may exist, but I haven’t found it yet. I call it [i]Sudokill[/i]. It is a two-person game. Let’s say I’m playing against you. We alternate laying numbers down on a Sudoku board. I win if I leave you no number to lay down, either because the board is complete or because any number you put down is inconsistent with the constraints. Similarly, you win if you can prevent me from moving.
[table=98%][tr][td][url=mk:@MSITStore:C:\Documents%20and%20Settings\wf\My%20Documents\Wrox.Puzzles.for.Programmers.and.Pros.May.2007.chm::/final/BBL0040.html][img=60,17]mk:@MSITStore:C:\Documents%20and%20Settings\wf\My%20Documents\Wrox.Puzzles.for.Programmers.and.Pros.May.2007.chm::/final/images/prev.gif[/img][/url]
[td][url=mk:@MSITStore:C:\Documents%20and%20Settings\wf\My%20Documents\Wrox.Puzzles.for.Programmers.and.Pros.May.2007.chm::/final/BBL0042.html][img=60,17]mk:@MSITStore:C:\Documents%20and%20Settings\wf\My%20Documents\Wrox.Puzzles.for.Programmers.and.Pros.May.2007.chm::/final/images/next.gif[/img][/url]
[/td][/tr][/table]
页:
[1]