We'll consume our input as a row-major 81 character string containing digits for given clues and periods for blank cells like so: 5.37.6.7.54.4.2.1.6.6.83.2.4.1.įor each cell containing a clue we'll begin by clearing the appropriate bit in each of the cell's three groups to indicate that the value has already been used, and we'll further initialize a todo list of empty cells. The integers serve as bitvectors where a 1 in the \(i\)th bit position indicates that digit \(i\) remains to be placed in the group and a 0 indicates that digit \(i\) has already been placed in the group. It'll be convenient to keep an integer for each of the 27 groups. To help with determination of local consistency, we'll keep some extra state beyond the array of characters representing digits currently placed. This is a long story, but it begins with a simple thing: a depth-first search where in each recursive call we pick an unassigned cell and try to complete the puzzle for each candidate digit locally consistent with the puzzle's current partial assignment. The initially assigned values are clues.Įlsewhere in Sudoku-land you may see various synonyms for boxes (squares or regions), groups (units or houses), or bands (chutes, stacks, towers, or floors), but box, group, and band are the terms I'll use here. THE PROBLEM Represent a proposed solution to a Sudoku puzzle as int solution new int99 where solutionij k means that the square associated with row i and column j has digit k. There are 27 groups, 6 bands, and 54 intersections. A set of 3 horizontally or vertically adjacent cells within a box is an intersection (of a box with a row or column). The union of 3 horizontally or vertically adjacent boxes is a band. That's to say that each digit 1-9 must occur once and only once within each group. Each row, column, and box forms a group of 9 cells that obeys an exactly-one constraint. In this paper we propose a SAT-based approach: A Sudoku is translated into a propositional formula that is satisfiable if and only if the Sudoku has a solution. It is further divided into 9 3x3 subgrids which we'll call boxes. The Sudoku puzzle is posed as a partially completed 9x9 grid comprising 81 cells. Its also possible to store all possible values for a given square, and. You know the rules, but I'll summarize to define some terms. You could also convert a Su Doku board to a propositional logic expression and solve it. I hope you'll enjoy it too I hope it adds something fresh to the Sudoku blogging genre and, of course, I hope it contributes to reducing the carbon footprint and data center costs of the burgeoning Sudoku puzzle mining industry. Still, this has been an enjoyable project with a nice result. Sudoku has been famously described as a denial of service attack on the human intellect. So, like many before, I've tried to replace time spent solving Sudokus puzzles with time spent writing a Sudoku solver and in so doing have wasted more of it than ever. I've been known to pass time with Sudoku. Judging from the number of websites, apps, and books on the topic, lots of people love it judging from the profusion of github projects and here's-my-Sudoku-solver blog posts (like this one), programmers love it too and judging from the academic attention it has recieved, computer scientists and ML researchers love it just as much as everyone else. append () # The cell at (r,c) has at most one value for v in range ( 1, N + 1 ): for w in range ( v + 1, N + 1 ): cls. \(\definecolor # encoding the fact that the cell at (r,c) has the value v def var ( r, c, v ): assert ( 1 <= r and r <= N and 1 <= c and c <= N and 1 <= v and v <= N ) return ( r - 1 ) * N * N + ( c - 1 ) * N + ( v - 1 ) + 1 # Build the clauses in a list cls = # The clauses: a list of integer lists for r in range ( 1, N + 1 ): # r runs over 1.,N for c in range ( 1, N + 1 ): # The cell at (r,c) has at least one value cls.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |