12/16/2023 0 Comments Np complete sudoku rules![]() When I am solving a Sudoku by hand and use this rule, I sometimes use more sophisticated deductions in the expansion phase: if a digit's placements in a square are limited to a single row or column, eliminate placements in the same row or column in other squares, and if a digit's placements in a row or column are limited to a single square, eliminate placements in the same square in other rows or columns. If a contradiction is reached, we eliminate the original placement as a potential location for that digit. In its most simple form, "expand the consequences" means, eliminate positions that conflict with a placed digit, and place a digit whenever it is the only remaining position in its row, column, or square, and "contradiction" means that we have placed two digits in the same row, column, or square, or that we have eliminated all positions in some row, column, or square. To test a position, we try placing the digit there, then expands the consequences of that placement until a contradiction is reached or a complete solution is found. In this rule, which is controversial because it has more the flavor of trial-and-error than deductive reasoning, one tests each potential position for the digit separately. Nishio, on the other hand, handles this example easily. ![]() So my program's rule fails to eliminate the X's as potential placements for the digit 7. This is not detected by the matching algorithm because it only considers rows and columns, not squares. The other two have two 7's in two of the four squares and none in the other two squares, leading to invalid solutions. Unfortunately, only two of the matchings correspond to possible solutions of the puzzle. In the example above, considering only the rows and columns involved in the marked cells, we get a graph with four perfect matchings: By finding a single perfect matching then performing strong connectivity analysis, we can quickly identify the edges that do not belong to a perfect matching, and eliminate the corresponding cells as potential placements for the digit 7. Perfect matchings in this graph correspond to placements of 7's throughout the puzzle that cover each row and each column exactly once. We connect vertices Ri and Cj by an edge in the graph, exactly when cell RiCj is a potential placement for the digit 7. It forms a bipartite graph, having 18 vertices, one for each row and one for each column of the puzzle. The way my program attempts to make deductions like this involves perfect matching in graphs. We would like a deduction rule that quickly comes to this conclusion. We can deduce that the 7's may only be placed at the positions marked Y, and in particular we can immediately place 7's at the Y's in the top two squares. But the X's do not give a consistent solution to the puzzle (the bottom two are on the same row), so none of the 7's can be placed on any X. By a sequence of similar deductions we find that if any 7 is placed on an X, all four squares must have their 7's placed at X's. ![]() If we place a 7 at the X at bottom left, it eliminates the Y at top left,įorcing the 7 in that square to be placed at X as well, and so on. For example, suppose that (by other deduction rules) we have limited the locations for the digit 7 in four squares of a puzzle to the X's and Y's shown in the following diagram (with the 7's in the other five squares placed in positions compatible with these locations): Turns out not.īoth rules have the same purpose: looking only at the cells where a single digit may be placed, determine which of those cells can possibly be used in a solution to the puzzle, and eliminate the others. I had thought the "digit" rule of my Sudoku program was a non-backtracking equivalent of nishio. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |