# Ga for sudoku

Disponível somente no TrabalhosFeitos
• Páginas : 13 (3011 palavras )
• Publicado : 14 de fevereiro de 2013

Amostra do texto

Evolutionary Computation
2012-2013

GA Sudoku Solver

Student: Nuno Carvalho nº18652
Instructor: Fernando Lobo

Contents
1.

Introduction ............................................................................................................ 1

2.

Genetic Algorithm.................................................................................................. 2
2.1.

Population ...................................................................................................... 2

2.2.

Selection Method ............................................................................................ 3

2.3.

Genetic Operators .......................................................................................... 32.3.1.

Crossover ................................................................................................ 3

2.3.2.

Bit Flip ..................................................................................................... 4

2.4.

Fitness Function ............................................................................................. 4

3.

Analysis of Results................................................................................................ 4

4.

Reflexion................................................................................................................ 7

5.

Conclusion ............................................................................................................. 7

6.

Bibliography........................................................................................................... 8

i

Figures Index
Figure 1 – Sudoku ........................................................................................................ 1
Figure 2 – Hyper Sudoku .............................................................................................. 1
Figure 3 – SudoKube.................................................................................................... 1
Figure 4 – Developed Sudoku....................................................................................... 2
Figure 5 – Start up population with locked values ......................................................... 3

Tables Index
Table 1 – Population size 100....................................................................................... 4
Table 2 – Population size 500 with two point crossover ................................................ 5
Table 3 – Pc = 0.8 (all other parameters remain unchanged) ........................................ 5
Table 4 – Pm = 1 / (81-input) ........................................................................................ 5
Table 5 –Reboot 250, tournament size 5 ..................................................................... 6
Table 6 – Reboot 250 Tournament size 10 ................................................................... 6
Table 7 – Reboot 250 Tournament size 10 keeping 2 bests.......................................... 6
Table 8 – Different parameters for different input values............................................... 7

ii

1. Introduction
Sudoku is a puzzle that consists in placing numbers from 1 to 9 in each of its cells.
There are several variations of Sudoku as Hyper Sudoku or SudoKube (and each with
variations). The Sudoku consists of a 9x9 square, this being constituted by nine 3x3
squares. The goal of Sudoku is to solve the puzzle, such that all nine rows, nine
columns andnine squares are numbered 1 to 9, without repeating any numbers both
rows and columns in the square.
Sudoku was invented by Howard Garns retired architect of 74 years. In 1974 it was
brought to Japan by Nikoli (largest Japanese puzzles company) and it was there that
earned the name Sudoku, an abbreviation of Suuji dokushin ni wa kagiru which means
the digits must remain single. And in 1986,...