[gnome-sudoku/vala-port] Improvements to the "Help" and logical solver
- From: Christopher Baines <cbaines src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gnome-sudoku/vala-port] Improvements to the "Help" and logical solver
- Date: Tue, 18 Jun 2013 18:25:26 +0000 (UTC)
commit 9acd0bbfc8b5d8e94cdd567f87401bdc3a7e2d36
Author: Christopher Baines <cbaines src gnome org>
Date: Tue Jun 18 19:22:26 2013 +0100
Improvements to the "Help" and logical solver
Added naked subsets to the help
Added more state to the logical solver to reduce computation
Added colouring of the cells in the grid on hover over the help
src/gnome-sudoku.vala | 88 ++++++++++++++--
src/logical-sudoku-solver.vala | 228 ++++++++++++++++++++++-----------------
src/sudoku-view.vala | 87 +++++++++++----
3 files changed, 271 insertions(+), 132 deletions(-)
---
diff --git a/src/gnome-sudoku.vala b/src/gnome-sudoku.vala
index e1c9f74..efe93a7 100644
--- a/src/gnome-sudoku.vala
+++ b/src/gnome-sudoku.vala
@@ -1,5 +1,6 @@
using Gtk;
using Gee;
+using Gdk;
public class Sudoku : Gtk.Application
{
@@ -91,6 +92,7 @@ public class Sudoku : Gtk.Application
naked_single_items = (Box) builder.get_object ("naked_single_items");
hidden_single_items = (Box) builder.get_object ("hidden_single_items");
+ naked_subset_items = (Box) builder.get_object ("naked_subset_items");
controls_box = (Box) builder.get_object ("number_picker_box");
@@ -221,8 +223,7 @@ public class Sudoku : Gtk.Application
view.show ();
grid_box.pack_start (view);
- LogicalSudokuSolver logical_solver = new LogicalSudokuSolver(ref game.board);
- update_help (logical_solver);
+ update_help ();
number_picker = new NumberPicker(ref game.board);
controls_box.pack_start (number_picker);
@@ -233,7 +234,7 @@ public class Sudoku : Gtk.Application
});
view.cell_value_changed_event.connect ((row, col) => {
- update_help (logical_solver);
+ update_help ();
});
@@ -276,16 +277,22 @@ public class Sudoku : Gtk.Application
});
}
- private void update_help (LogicalSudokuSolver logical_solver)
+ private void update_help ()
{
+ LogicalSudokuSolver logical_solver = new LogicalSudokuSolver(ref game.board);
+
+ view.reset_cell_background_colors ();
+ view.queue_draw ();
+
+ RGBA highlight_color = {0.47, 0.75, 1, 0};
+ RGBA highlight_fixed_color = {0.8, 0.8, 0.9, 0};
+
foreach (Widget w in naked_single_items.get_children())
{
naked_single_items.remove (w);
}
- ArrayList<Cell?> naked_singles = logical_solver.get_naked_singles ();
-
- foreach (Cell? cell in naked_singles)
+ foreach (Cell? cell in logical_solver.naked_singles)
{
var event_box = new Gtk.EventBox ();
@@ -308,7 +315,7 @@ public class Sudoku : Gtk.Application
hidden_single_items.remove (w);
}
- foreach (HiddenSingle? hidden_single in logical_solver.get_hidden_singles ())
+ foreach (HiddenSingle? hidden_single in logical_solver.hidden_singles)
{
var event_box = new Gtk.EventBox ();
@@ -346,12 +353,32 @@ public class Sudoku : Gtk.Application
event_box.enter_notify_event.connect ((event) => {
view.cell_grab_focus (hidden_single.cell.coord.row, hidden_single.cell.coord.col);
- return true;
- });
- label.enter_notify_event.connect ((event) => {
+ if (hidden_single.row) {
+ view.set_row_background_color (hidden_single.cell.coord.row, highlight_color,
highlight_fixed_color);
+ }
+
+ if (hidden_single.col) {
+ view.set_col_background_color (hidden_single.cell.coord.col, highlight_color,
highlight_fixed_color);
+ }
+
+ if (hidden_single.block) {
+ Coord block = game.board.get_block_for (hidden_single.cell.coord.row,
hidden_single.cell.coord.col);
+ view.set_block_background_color (block.row, block.col, highlight_color,
highlight_fixed_color);
+ }
+
view.selected_x = hidden_single.cell.coord.col;
view.selected_y = hidden_single.cell.coord.row;
+
+ view.queue_draw ();
+
+ return true;
+ });
+
+ event_box.leave_notify_event.connect ((event) => {
+ view.reset_cell_background_colors ();
+ view.queue_draw ();
+
return true;
});
@@ -361,6 +388,45 @@ public class Sudoku : Gtk.Application
event_box.show ();
label.show ();
}
+
+ foreach (Widget w in naked_subset_items.get_children())
+ {
+ naked_subset_items.remove (w);
+ }
+
+ foreach (Subset? subset in logical_solver.get_naked_subsets()) {
+ var event_box = new Gtk.EventBox ();
+
+ string description = "naked subset";
+
+ var label = new Gtk.Label (description);
+
+ event_box.enter_notify_event.connect ((event) => {
+ foreach (Cell? cell in subset.eliminated_possibilities) {
+ view.set_cell_background_color(cell.coord.row, cell.coord.col, {1, 0, 0, 0});
+ }
+
+ foreach (Coord? coord in subset.coords) {
+ view.set_cell_background_color(coord.row, coord.col, {0, 1, 0, 0});
+ }
+
+ view.queue_draw ();
+
+ return true;
+ });
+
+ event_box.leave_notify_event.connect ((event) => {
+ view.reset_cell_background_colors ();
+ view.queue_draw ();
+
+ return true;
+ });
+
+ event_box.add (label);
+ naked_subset_items.add (event_box);
+ event_box.show ();
+ label.show ();
+ }
}
private void show_start ()
diff --git a/src/logical-sudoku-solver.vala b/src/logical-sudoku-solver.vala
index 4edcbb4..6163ac1 100644
--- a/src/logical-sudoku-solver.vala
+++ b/src/logical-sudoku-solver.vala
@@ -7,116 +7,132 @@ class LogicalSudokuSolver
{
private SudokuBoard board;
- public LogicalSudokuSolver (ref SudokuBoard board)
- {
- this.board = board;
- }
+ public ArrayList<Cell?> naked_singles = new ArrayList<Cell?> ();
+ public ArrayList<HiddenSingle?> hidden_singles = new ArrayList<HiddenSingle?> ();
+ public ArrayList<Subset?> naked_subsets = new ArrayList<Subset?> ();
+ public ArrayList<Subset?> hidden_subsets = new ArrayList<Subset?> ();
/**
- * Returns cells where there is only one remaining candidate for the cell
+ * An array of coordinates, row_possibilities[1, 1] is the
+ * list of places where 1 can go in this row.
*/
- public ArrayList<Cell?> get_naked_singles ()
- {
- ArrayList<Cell?> naked_singles = new ArrayList<Cell?> ();
- HashMap<Coord?, ArrayList<int>> open_squares = board.calculate_open_squares ();
+ private ArrayList<Coord?>[,] row_possibilities;
- foreach (Coord coord in open_squares.keys)
- {
- if (open_squares[coord].size == 1)
- {
- naked_singles.add(Cell(coord, open_squares[coord].get(0)));
- }
- }
+ /**
+ * An array of coordinates, row_possibilities[1, 1] is the
+ * list of places where 1 can go in this row.
+ */
+ private ArrayList<Coord?>[,] col_possibilities;
- return naked_singles;
- }
+ /**
+ * An array of coordinates, row_possibilities[1, 1] is the
+ * list of places where 1 can go in this row.
+ */
+ private Map<Coord?, ArrayList<ArrayList<Coord?>>> block_possibilities;
- public ArrayList<HiddenSingle?> get_hidden_singles(bool ignore_naked_singles = true)
+ HashMap<Coord?, ArrayList<int>> open_squares;
+
+ public LogicalSudokuSolver (ref SudokuBoard board)
{
- ArrayList<HiddenSingle?> hidden_singles = new ArrayList<HiddenSingle?> ();
- HashMap<Coord?, ArrayList<int>> open_squares = board.calculate_open_squares ();
+ this.board = board;
- for (int row = 0; row < board.rows; row++)
- {
- for (int col = 0; col < board.cols; col++)
+ // Get the open squares, along with the possibilities for these squares
+ open_squares = board.calculate_open_squares ();
+
+ fill_possibility_arrays ();
+
+ // Interate over them
+ foreach (Coord? open_square in open_squares.keys) {
+
+ // If there is only one candidate left, this is a naked single
+ if (open_squares[open_square].size == 1)
{
- if (board[row, col] != 0)
- continue;
+ naked_singles.add(Cell(open_square, open_squares[open_square].get(0)));
+ continue;
+ }
- ArrayList<int> possibilities = open_squares[Coord(row, col)];
+ // For each possibility in the square
+ foreach (var possibility in open_squares[open_square]) {
+ bool unique_in_row = row_possibilities[open_square.row, possibility].size == 1;
+ bool unique_in_col = col_possibilities[open_square.col, possibility].size == 1;
+ bool unique_in_block = block_possibilities[board.get_block_for(open_square.row,
open_square.col)][possibility].size == 1;
- if (ignore_naked_singles && possibilities.size == 1)
+ if (unique_in_row || unique_in_col || unique_in_block) {
+ hidden_singles.add (HiddenSingle(Cell(open_square, possibility), unique_in_row,
unique_in_col, unique_in_block));
continue;
+ }
+ }
+ }
+ }
- foreach (int val in possibilities)
- {
- bool possibility_not_present_in_row = true;
- foreach (Coord coord in board.coords_for_row[row])
- {
- if (coord.row == row && coord.col == col)
- continue;
-
- if (open_squares[coord] == null)
- continue;
-
- if (open_squares[coord].contains(val))
- {
- possibility_not_present_in_row = false;
- break;
- }
- }
- bool possibility_not_present_in_col = true;
- foreach (Coord coord in board.coords_for_col[col])
- {
- if (coord.row == row && coord.col == col)
- continue;
-
- if (open_squares[coord] == null)
- continue;
-
- if (open_squares[coord].contains(val))
- {
- possibility_not_present_in_col = false;
- break;
- }
- }
- bool possibility_not_present_in_block = true;
- foreach (Coord coord in board.coords_for_block[board.get_block_for(row, col)])
- {
- if (coord.row == row && coord.col == col)
- continue;
-
- if (open_squares[coord] == null)
- continue;
-
- if (open_squares[coord].contains(val))
- {
- possibility_not_present_in_block = false;
- break;
- }
- }
+ private void fill_possibility_arrays () {
+ row_possibilities = new ArrayList<Coord?>[board.rows, board.max_val + 1];
+ col_possibilities = new ArrayList<Coord?>[board.cols, board.max_val + 1];
+ block_possibilities = new HashMap<Coord?, ArrayList<ArrayList<Coord?>>> ((GLib.HashFunc) Coord.hash,
(GLib.EqualFunc) Coord.equal);
- if (possibility_not_present_in_row || possibility_not_present_in_col ||
possibility_not_present_in_block)
- {
- hidden_singles.add (HiddenSingle(Cell(Coord(row, col), val),
possibility_not_present_in_row, possibility_not_present_in_col, possibility_not_present_in_block));
- }
+ for (int row = 0; row < board.rows; row++) {
+ for (int col = 0; col < board.cols; col++) {
+ for (int val = 1; val <= board.max_val; val++) {
+ row_possibilities[row, val] = new ArrayList<Coord?> ();
+ col_possibilities[col, val] = new ArrayList<Coord?> ();
}
}
}
- return hidden_singles;
+
+ for (int row = 0; row < board.block_rows; row++) {
+ for (int col = 0; col < board.block_cols; col++) {
+ block_possibilities[Coord(row, col)] = new ArrayList<ArrayList<Coord?>> ();
+ block_possibilities[Coord(row, col)].add(null);
+ for (int val = 1; val <= board.max_val; val++) {
+ block_possibilities[Coord(row, col)].add(new ArrayList<Coord?> ());
+ }
+ }
+ }
+
+ foreach (Coord? open_square in open_squares.keys) {
+ foreach (int val in open_squares[open_square]) {
+ row_possibilities[open_square.row, val].add(open_square);
+ col_possibilities[open_square.col, val].add(open_square);
+ block_possibilities[board.get_block_for(open_square.row,
open_square.col)][val].add(open_square);
+ }
+ }
+ }
+
+ /**
+ * Returns all subsets, with 2 or more elements
+ */
+ private Set<Set<int>> powerset(ArrayList<int> elements) {
+ HashSet<HashSet<int>> powerset = new HashSet<HashSet<int>> ();
+ uint subset_count = 1 << elements.size;
+
+ // Start at 3, because 0, 1 and 2 will be subsets smaller than 2
+ for (uint subset = 3; subset < subset_count; subset++) {
+ HashSet<int> one_set = new HashSet<int> ();
+
+ var element = 0;
+ for (var bits = subset; bits != 0; bits >>= 1) {
+ if ((bits & 1) != 0)
+ one_set.add(elements[element]);
+ element++;
+ }
+
+ if (one_set.size > 1)
+ powerset.add(one_set);
+ }
+
+ return powerset;
}
public ArrayList<Subset?> get_naked_subsets ()
{
- ArrayList<Subset?> subsets = new ArrayList<Subset?> ();
HashMap<Coord?, ArrayList<int>> open_squares = board.calculate_open_squares ();
for (int col = 0; col < board.cols; col++) {
- subsets.add_all(get_naked_subsets_in (board.coords_for_col[col], House.COLUMN, open_squares));
+ get_naked_subsets_in (board.coords_for_col[col], House.COLUMN, open_squares);
}
for (int row = 0; row < board.rows; row++) {
- subsets.add_all(get_naked_subsets_in (board.coords_for_row[row], House.ROW, open_squares));
+ get_naked_subsets_in (board.coords_for_row[row], House.ROW, open_squares);
}
int blocks_across = board.cols / board.block_cols;
@@ -124,17 +140,15 @@ class LogicalSudokuSolver
for (int block_down = 0; block_down < blocks_down; block_down++) {
for (int block_across = 0; block_across < blocks_across; block_across++) {
- subsets.add_all(get_naked_subsets_in (board.coords_for_block[Coord(block_across,
block_down)], House.BLOCK, open_squares));
+ get_naked_subsets_in (board.coords_for_block[Coord(block_across, block_down)], House.BLOCK,
open_squares);
}
}
- return subsets;
+ return naked_subsets;
}
- private ArrayList<Subset?> get_naked_subsets_in (Gee.List<Coord?> coords, House house, HashMap<Coord?,
ArrayList<int>> open_squares)
+ private void get_naked_subsets_in (Gee.List<Coord?> coords, House house, HashMap<Coord?, ArrayList<int>>
open_squares)
{
- ArrayList<Subset?> subsets = new ArrayList<Subset?>();
-
// Try starting a subset from each coord in the list given
foreach (Coord initial_coord in coords)
{
@@ -142,34 +156,44 @@ class LogicalSudokuSolver
if (open_squares[initial_coord] == null || open_squares[initial_coord].size < 2)
continue;
- ArrayList<Coord?> subset_coords = new ArrayList<Coord?> ();
+ ArrayList<Coord?> subset_coords = new ArrayList<Coord?> ((GLib.EqualFunc) Coord.equal);
subset_coords.add (initial_coord);
- int possibilities = open_squares[initial_coord].size;
+ int subset_size = open_squares[initial_coord].size;
foreach (Coord coord in coords)
{
- if (open_squares[coord] == null || open_squares[coord].size != possibilities)
+ if (open_squares[coord] == null || open_squares[coord].size != subset_size || (coord ==
initial_coord))
continue;
// If the possibilites for coord, and initial_coord are the same
- if (open_squares[initial_coord].contains_all(open_squares[coord]))
+ if (open_squares[initial_coord].contains_all(open_squares[coord]) &&
open_squares[coord].contains_all(open_squares[initial_coord]))
{
subset_coords.add (coord);
}
// If this subset is complete
- if (subset_coords.size == possibilities)
+ if (subset_coords.size == subset_size)
{
ArrayList<Cell?> eliminated_possibilities = get_eliminated_possibilities(coords,
subset_coords, open_squares);
- subsets.add(Subset(subset_coords, house, eliminated_possibilities));
+
+ bool equivilent_subset_found = false;
+ foreach (Subset subset in naked_subsets) {
+ if (subset_coords.contains_all(subset.coords) &&
subset.coords.contains_all(subset_coords)) {
+ subset.eliminated_possibilities.add_all(eliminated_possibilities);
+ equivilent_subset_found = true;
+ break;
+ }
+ }
+
+ if (!equivilent_subset_found) {
+ naked_subsets.add(Subset(open_squares[initial_coord], subset_coords,
eliminated_possibilities));
+ }
break;
}
}
}
-
- return subsets;
}
/*
@@ -216,18 +240,24 @@ class LogicalSudokuSolver
*/
public struct Subset
{
+ public ArrayList<int> values;
public ArrayList<Coord?> coords;
- public House house;
public ArrayList<Cell?> eliminated_possibilities;
- public Subset (ArrayList<Coord?> coords, House house, ArrayList<Cell?> eliminated_possibilities)
+ public Subset (ArrayList<int> values, ArrayList<Coord?> coords, ArrayList<Cell?>
eliminated_possibilities)
{
+ this.values = values;
this.coords = coords;
- this.house = house;
this.eliminated_possibilities = eliminated_possibilities;
}
}
+/**
+ * Used to describe the presence of a hidden single.
+ *
+ * The cell denotes the position and value, the row, column and block
+ * denote the houses which this value is the single candidate in.
+ */
public struct HiddenSingle
{
public Cell cell;
diff --git a/src/sudoku-view.vala b/src/sudoku-view.vala
index 4f608bd..d42d3c2 100644
--- a/src/sudoku-view.vala
+++ b/src/sudoku-view.vala
@@ -128,14 +128,7 @@ private class SudokuCellView : Gtk.DrawingArea
this._row = row;
this._col = col;
- if (is_fixed)
- {
- _background_color = { 0.8, 0.8, 0.8, 0.0 };
- }
- else
- {
- _background_color = { 1.0, 1.0, 1.0, 0.0 };
- }
+ // background_color is set in the SudokuView, as it manages the color of the cells
set_can_focus(true);
can_focus = true;
@@ -556,6 +549,9 @@ public class SudokuView : Gtk.AspectFrame
{0.4588235294117647, 0.3137254901960784, 0.4823529411764706, 0.0}
};
+ public const RGBA fixed_cell_color = {0.8, 0.8, 0.8, 0};
+ public const RGBA free_cell_color = {1.0, 1.0, 1.0, 1.0};
+
private int _selected_x = 0;
public int selected_x
{
@@ -620,6 +616,15 @@ public class SudokuView : Gtk.AspectFrame
var cell_row = row;
var cell_col = col;
+ if (cell.is_fixed)
+ {
+ cell.background_color = fixed_cell_color;
+ }
+ else
+ {
+ cell.background_color = free_cell_color;
+ }
+
if (!preview)
{
cell.focus_out_event.connect (() => {
@@ -769,20 +774,7 @@ public class SudokuView : Gtk.AspectFrame
public void stop_dance ()
{
dance_step = -1;
- for (var j = 0; j < game.board.cols; j++)
- {
- for (var i = 0; i < game.board.rows; i++)
- {
- if (cells[i,j].is_fixed)
- {
- cells[i,j].background_color = { 0.8, 0.8, 0.8, 0.0 };
- }
- else
- {
- cells[i,j].background_color = { 1.0, 1.0, 1.0, 0.0 };
- }
- }
- }
+ reset_cell_background_colors ();
}
private RGBA get_next_color (RGBA color)
@@ -810,4 +802,55 @@ public class SudokuView : Gtk.AspectFrame
{
cells[row, col].grab_focus ();
}
+
+ public void set_cell_background_color (int row, int col, RGBA color) {
+ cells[row, col].background_color = color;
+ }
+
+ public void set_row_background_color (int row, RGBA color, RGBA fixed_color = fixed_cell_color) {
+ for (var col = 0; col < game.board.cols; col++) {
+ if (cells[row, col].is_fixed) {
+ cells[row, col].background_color = fixed_color;
+ } else {
+ cells[row, col].background_color = color;
+ }
+ }
+ }
+
+ public void set_col_background_color (int col, RGBA color, RGBA fixed_color = fixed_cell_color) {
+ for (var row = 0; row < game.board.rows; row++) {
+ if (cells[row, col].is_fixed) {
+ cells[row, col].background_color = fixed_color;
+ } else {
+ cells[row, col].background_color = color;
+ }
+ }
+ }
+
+ public void set_block_background_color (int block_row, int block_col, RGBA color, RGBA fixed_color =
fixed_cell_color) {
+ foreach (Coord? coord in game.board.coords_for_block.get(Coord(block_row, block_col))) {
+ if (cells[coord.row, coord.col].is_fixed) {
+ cells[coord.row, coord.col].background_color = fixed_color;
+ } else {
+ cells[coord.row, coord.col].background_color = color;
+ }
+ }
+ }
+
+ public void reset_cell_background_colors () {
+ for (var j = 0; j < game.board.cols; j++)
+ {
+ for (var i = 0; i < game.board.rows; i++)
+ {
+ if (cells[i,j].is_fixed)
+ {
+ cells[i,j].background_color = fixed_cell_color;
+ }
+ else
+ {
+ cells[i,j].background_color = free_cell_color;
+ }
+ }
+ }
+ }
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
