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. Take the sudoku data table and replace hypotheses with data, if available.
3. 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)).
         1. Test for the rule with the pair of cells, creating a set of plausible hypothesis for one cell conditional on the other cell.
         2. If a set is empty, the condition is implausible; remove the condition and thus that hypothesis from the other cell.
         3. Take the union of plausible hypothesis (which then covers all plausible hypotheses unconditionally.
         4. Do the same comparison for the other cell conditional on the first one.
4. 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.
5. Calculate the number of different solutions still plausible and print it.
6. If the number is smaller than 100, print also the solutions.

Rationale

Data

This table will be expanded by fillna to be a 9*9*9 array (formatted as data.frame). As default, each hypothesis is assumed to be true unless shown otherwise.

Hypotheses(Boolean)

Obs	SudRow	SudCol	Hypothesis	Result
1			1	TRUE
2			2	TRUE
3			3	TRUE
4			4	TRUE
5			5	TRUE
6			6	TRUE
7			7	TRUE
8			8	TRUE
9			9	TRUE
10		1		TRUE
11		2		TRUE
12		3		TRUE
13		4		TRUE
14		5		TRUE
15		6		TRUE
16		7		TRUE
17		8		TRUE
18		9		TRUE
19	1			TRUE
20	2			TRUE
21	3			TRUE
22	4			TRUE
23	5			TRUE
24	6			TRUE
25	7			TRUE
26	8			TRUE
27	9			TRUE

Formula used: Rowarea <- ceiling(SudRow/3), Colarea <- ceiling(SudCol/3)

Areas(-)

Obs	Rowarea	Colarea	SudArea	Result
1	1	1	1
2	1	2	2
3	1	3	3
4	2	1	4
5	2	2	5
6	2	3	6
7	3	1	7
8	3	2	8
9	3	3	9

Formula

+ Show code- Hide code library(OpasnetUtils) areas <- tidy(opbase.data("Op_en5817.areas")) areas <- areas[colnames(areas) != "Result"] hypotheses <- tidy(opbase.data("Op_en5817.hypotheses")) oprint(dropall(hypotheses)) for(i in 1:3) {hypotheses[[i]] <- as.numeric(as.character(hypotheses[[i]]))} hypotheses <- unique(fillna(hypotheses, marginals = c(1, 2, 3))) hypotheses$Rowarea <- as.factor(ceiling(as.numeric(as.character(hypotheses$SudRow))/3)) hypotheses$Colarea <- as.factor(ceiling(as.numeric(as.character(hypotheses$SudCol))/3)) hypotheses <- merge(hypotheses, areas) hypotheses <- hypotheses[!colnames(hypotheses) %in% c("Rowarea", "Colarea")] oprint(hypotheses)

See also

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

Related files

<mfanonymousfilelist></mfanonymousfilelist>