3. (50 marks) Design a Genetic Algorithm for a variant of the SUDOKU puzzle of v

Question

3. (50 marks) Design a Genetic Algorithm for a variant of the SUDOKU puzzle of variable size N x N. Initial conditions of the puzzle should be a distribution of numbers that respect the rule that in each of the N sub-squares each integer 1,.., N appears only once (see figure for an example 4x4 SUDOKU puzzle) A) (15 marks) Determine a representation and B) (15 marks) fitness function for searching for a correct solution by a GA. C) (10 marks) Design mutation and D) (10 marks) crossover operators that attempt to permute the numbers such that - starting from the initial configuration- the puzzle can be solved. 2 2 4

Explanation / Answer

Initialization: Store the given values in each chromosome, and then randomly generate values such that each row is a valid permutation of the values 1 through N.

Fitness: Determined by the number of "out of place" values in each row, column, and square grid, added together.

Fitness Function: Typical roulette wheel selection

Selection: Random, but weighted using the roulette wheel.

Mutation: randomly choose a row, and then randomize the ordering of that row (leaving the given values in their correct locations)

Crossover: Randomly choose various rows from two parents, which creates one child. (I've also implemented a crossover (over a 9x9 sudoku) that randomly chooses 3 rows at a time from the two parents - in an effort to preserve good mini-grids). The following are two example children, one from each crossover method:

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.