Sudoku
Solve a partially filled-in normal 9x9 Sudoku grid and display the result in a human-readable format. Algorithmics of sudoku may help implement this.
You are encouraged to solve this task according to the task description, using any language you may know.
AutoHotkey
by infogulch. More info (and similarly formatted puzzles) <lang AutoHotkey>puzzleEasy = ( LTrim 394 @@2 67@ @@@ 3@@ 4@@ 5@@ 69@ @2@
@45 @@@ 9@@ 6@@ @@@ @@7 @@7 @@@ 58@
@1@ @67 @@8 @@9 @@8 @@@ @26 4@@ 735 ) s := A_TickCount MsgBox % "Easy:`n" Sudoku( puzzleEasy ) "`nIterations: " ErrorLevel "`n`nSeconds: " (A_TickCount-s)/1000
- Functions Start here
Sudoku( p ) { ;ErrorLevel contains the number of iterations p := RegExReplace(p, "[^1-9@]"), ErrorLevel := 0 ;format puzzle as single line string return Sudoku_Display(Sudoku_Solve(p)) }
Sudoku_Solve( p, d = 0 ) { ;d is 0-based
- p
- 81 character puzzle string
- (concat all 9 rows of 9 chars each)
- givens represented as chars 1-9
- fill-ins as any non-null, non 1-9 char
- d
- used internally. omit on initial call
- returns
- 81 char string with non-givens replaced with valid solution
If (d >= 81), ErrorLevel++ return p ;this is 82nd iteration, so it has successfully finished iteration 81 If InStr( "123456789", SubStr(p, d+1, 1) ) ;this depth is a given, skip through return Sudoku_Solve(p, d+1) m := Sudoku_Constraints(p,d) ;a string of this level's constraints. ; (these will not change for all 9 loops) Loop 9 { If InStr(m, A_Index) Continue NumPut(Asc(A_Index), p, d, "Char") If r := Sudoku_Solve(p, d+1) return r } return 0 }
Sudoku_Constraints( ByRef p, d ) {
- returns a string of the constraints for a particular position
c := Mod(d,9) , r := (d - c) // 9 , b := r//3*27 + c//3*3 + 1 ;convert to 1-based , c++ return "" ; row: . SubStr(p, r * 9 + 1, 9) ; column: . SubStr(p,c ,1) SubStr(p,c+9 ,1) SubStr(p,c+18,1) . SubStr(p,c+27,1) SubStr(p,c+36,1) SubStr(p,c+45,1) . SubStr(p,c+54,1) SubStr(p,c+63,1) SubStr(p,c+72,1) ;box . SubStr(p, b, 3) SubStr(p, b+9, 3) SubStr(p, b+18, 3) }
Sudoku_Display( p ) { If StrLen(p) = 81 loop 81 r .= SubStr(p, A_Index, 1) (!Mod(A_Index, 9) ? "`n" : !Mod(A_Index,3) ? "`t" : "") return r } </lang>