Searching

Open Set

In breadth first the open set is a collection of nodes stored in some, nodes are removed and added to the open set over time, and it is used to move through the graph.

Explored

Suppose that

n

is a node in the graph, we say that

n

is explored, if it's been removed from the open set and it's successors have been added to the open set

Complete

We say that a search algorithm is complete if whenever a solution exists, it is able to find the solution

Sudoku is a popular number puzzle that works as follows: we are given a 9 × 9 square grid; some squares have numbers, while some are blank. Our objective is to fill in the blanks with numbers from 1 − 9 such that each row, column, and the highlighted 3 × 3 squares contain no duplicate entries.

Sudoku puzzles can be solved easily after being modelled as a CSP We will consider the problem of generating Sudoku puzzles. In particular, consider the following procedure:

Sudoku Representation

Start with a completely full valid sudoku grid and iteratively make some squares blank. Continue blanking out squares as long as the resulting puzzle can be completed in at least one way. That is, stop before there are multiple ways to solve the board.

Give the representation of a state in this problem
Using the state representation defined above, specify the initial state and goal state(s)
Define its actions.
Using the state representation and actions defined above, specify the transition function T . (In other words, when each of the actions defined above is applied to a current state, what is the resulting state?)

A state in this problem is a partial valid solution of the Sudoku puzzle with some blank squares, we'll represent blank squares with a zero, so then our state is a matrix $S \in M_{9 \times 9} ([0, \dots 9])$ ,

The initial state is a matrix $X \in M_{9 \times 9} ([1 \dots 9])$

An action removes a number from the grid, so we can take our intermediate matrix $X$ , and obtain a new matrix $X^{'}$ which is obtained by setting one of the non-zero entries of $X$ to be zero. This can be constructively done by subtrating a new matrix which has zeros every except for the place at which we want to make zero, where instead we have the number from the original matrix.

The transition function could be defined as follows $T (X, (i, j)) = X - poke_thru (X, (i, j))$