Sudoku solver

This page is a knowledge crystal of subtype method. The page identifier is Op_en5817
Moderator:Jouni (see all)
This page is a stub. You may improve it into a full page.
Upload data {{#opasnet_base_link:Op_en5817}}

Question

How to describe a sudoku and the sudoku rules in Opasnet so that it can be solved automatically?

Answer

You need the following tables.

Hypotheses

Row	Column	Result	Description
All	All	1,2,3,4,5,6,7,8,9	For all row and column locations it applies that the plausible hypotheses are a single integer between 1 and 9 (unless more information is available).

Area descriptions

Row	Column	Area
1	1	A
1	2	A
1	3	A
1	4	B
…
2	1	A
…
4	1	D
…
9	9	I

Rules of exclusion when comparing two cells.

Property1	Condition1	Property2	Condition2	Rule	Description
Row	Same	Column	Different	Same integer not allowed	Two cells with the same row and different column are not allowed to have the same integer.
Row	Different	Column	Same	Same integer not allowed	Two cells with the different row and same column are not allowed to have the same integer.
Area	Same	Column	Different	Same integer not allowed	Two cells with the same area and different column are not allowed to have the same integer.
Area	Same	Row	Different	Same integer not allowed	Two cells with the same area and different row are not allowed to have the same integer.

The sudoku data (this example is "the most difficult sudoku in the world")

Row	Column
	1	2	3	4	5	6	7	8	9
1	8
2			3	6
3		7			9		2
4		5				7
5					4	5	7
6				1				3
7			1					6	8
8			8	5				1
9		9					4

Procedure

1. Expand the "All" from the Hypothesis table to create a row for the hypothesis of each cell.
2. Compare two cells in the sudoku. Make a for loop the first cell: for(i in 1:nrow(hypothesis)).
   1. Make another for loop for the second cell: for(j in (i+1):nrow(hypothesis)).
      1. Make a third loop for all rules: for(k in 1:nrow(rules)).
      2. Test for the rule with the pair of cells, creating a set of plausible hypothesis for one cell conditional on the other cell.
      3. If a set is empty, the condition is implausible; remove the condition and thus that hypothesis from the other cell.
      4. Take the union of plausible hypothesis (which then covers all plausible hypotheses unconditionally.
      5. Do the same comparison for the other cell conditional on the first one.
3. If a unique solution was not found and if the current set of hypotheses is not the same as the previous set, save the current set as "previous set" and go to number 2.
4. Calculate the number of different solutions still plausible and print it.
5. If the number is smaller than 100, print also the solutions.

See also

• file:Sudoku solver.ANA (a draft solver using Analytica)

Related files

<mfanonymousfilelist></mfanonymousfilelist>