1// Package shikaku implements the Shikaku rectangle-partition puzzle game.2package shikaku34// Clue represents a numbered cell in the grid.5type Clue struct {6 ID int `json:"id"`7 X int `json:"x"`8 Y int `json:"y"`9 Value int `json:"value"` // required rectangle area10}1112// Rectangle represents a player-placed rectangle covering grid cells.13type Rectangle struct {14 ClueID int `json:"clue_id"`15 X int `json:"x"` // top-left16 Y int `json:"y"`17 W int `json:"w"` // dimensions18 H int `json:"h"`19}2021// Area returns the area of the rectangle.22func (r Rectangle) Area() int { return r.W * r.H }2324// Contains reports whether the rectangle covers the cell at (cx, cy).25func (r Rectangle) Contains(cx, cy int) bool {26 return cx >= r.X && cx < r.X+r.W && cy >= r.Y && cy < r.Y+r.H27}2829// Puzzle holds the full state of a Shikaku game.30type Puzzle struct {31 Width, Height int32 Clues []Clue33 Rectangles []Rectangle // player-placed34 clueIndex map[[2]int]int35}3637const unownedRegionID = -13839// FindClueAt returns the clue at position (x, y), or nil.40func (p *Puzzle) FindClueAt(x, y int) *Clue {41 if p.clueIndex == nil {42 p.clueIndex = make(map[[2]int]int, len(p.Clues))43 for i, c := range p.Clues {44 p.clueIndex[[2]int{c.X, c.Y}] = i45 }46 }47 if idx, ok := p.clueIndex[[2]int{x, y}]; ok {48 return &p.Clues[idx]49 }50 return nil51}5253// FindClueByID returns the clue with the given ID, or nil.54func (p *Puzzle) FindClueByID(id int) *Clue {55 if id >= 0 && id < len(p.Clues) && p.Clues[id].ID == id {56 return &p.Clues[id]57 }58 for i := range p.Clues {59 if p.Clues[i].ID == id {60 return &p.Clues[i]61 }62 }63 return nil64}6566// FindRectangleForClue returns the rectangle placed for the given clue ID, or nil.67func (p *Puzzle) FindRectangleForClue(clueID int) *Rectangle {68 for i := range p.Rectangles {69 if p.Rectangles[i].ClueID == clueID {70 return &p.Rectangles[i]71 }72 }73 return nil74}7576// CellOwner returns the clue ID of the rectangle covering (x, y), or -1.77func (p *Puzzle) CellOwner(x, y int) int {78 for _, r := range p.Rectangles {79 if r.Contains(x, y) {80 return r.ClueID81 }82 }83 return -184}8586// Overlaps reports whether the given rectangle overlaps any existing rectangle,87// optionally excluding the rectangle belonging to excludeClueID.88func (p *Puzzle) Overlaps(rect Rectangle, excludeClueID int) bool {89 for _, r := range p.Rectangles {90 if r.ClueID == excludeClueID {91 continue92 }93 if rectsOverlap(rect, r) {94 return true95 }96 }97 return false98}99100func rectsOverlap(a, b Rectangle) bool {101 return a.X < b.X+b.W && a.X+a.W > b.X && a.Y < b.Y+b.H && a.Y+a.H > b.Y102}103104// ValidRectangleForClue reports whether rect is a legal placement for clueID.105func (p *Puzzle) ValidRectangleForClue(rect Rectangle, clueID int) bool {106 clue := p.FindClueByID(clueID)107 if clue == nil {108 return false109 }110 if rect.Area() != clue.Value {111 return false112 }113 if rect.X < 0 || rect.Y < 0 || rect.X+rect.W > p.Width || rect.Y+rect.H > p.Height {114 return false115 }116 if !rect.Contains(clue.X, clue.Y) {117 return false118 }119 if p.Overlaps(rect, clueID) {120 return false121 }122123 clueCount := 0124 for _, c := range p.Clues {125 if rect.Contains(c.X, c.Y) {126 clueCount++127 if c.ID != clueID {128 return false129 }130 }131 }132133 return clueCount == 1134}135136// CandidateRectanglesForClue returns every legal rectangle for the clue.137func (p *Puzzle) CandidateRectanglesForClue(clueID int) []Rectangle {138 clue := p.FindClueByID(clueID)139 if clue == nil {140 return nil141 }142143 area := clue.Value144 candidates := make([]Rectangle, 0, area)145 for h := 1; h <= area; h++ {146 if area%h != 0 {147 continue148 }149 w := area / h150 if w > p.Width || h > p.Height {151 continue152 }153154 minX := max(0, clue.X-w+1)155 maxX := min(clue.X, p.Width-w)156 minY := max(0, clue.Y-h+1)157 maxY := min(clue.Y, p.Height-h)158 for y := minY; y <= maxY; y++ {159 for x := minX; x <= maxX; x++ {160 rect := Rectangle{ClueID: clueID, X: x, Y: y, W: w, H: h}161 if p.ValidRectangleForClue(rect, clueID) {162 candidates = append(candidates, rect)163 }164 }165 }166 }167168 return candidates169}170171func (p *Puzzle) encasedRectangleForClue(clueID int) (Rectangle, bool) {172 clue := p.FindClueByID(clueID)173 if clue == nil || p.FindRectangleForClue(clueID) != nil {174 return Rectangle{}, false175 }176 if p.CellOwner(clue.X, clue.Y) != unownedRegionID {177 return Rectangle{}, false178 }179180 cells := p.unownedRegionFrom(clue.X, clue.Y)181 if len(cells) == 0 {182 return Rectangle{}, false183 }184185 minX, maxX := cells[0][0], cells[0][0]186 minY, maxY := cells[0][1], cells[0][1]187 for _, cell := range cells[1:] {188 minX = min(minX, cell[0])189 maxX = max(maxX, cell[0])190 minY = min(minY, cell[1])191 maxY = max(maxY, cell[1])192 }193194 rect := Rectangle{195 ClueID: clueID,196 X: minX,197 Y: minY,198 W: maxX - minX + 1,199 H: maxY - minY + 1,200 }201 if rect.Area() != len(cells) {202 return Rectangle{}, false203 }204 if !p.ValidRectangleForClue(rect, clueID) {205 return Rectangle{}, false206 }207 return rect, true208}209210func (p *Puzzle) forcedRectangleForClue(clueID int) (Rectangle, bool) {211 clue := p.FindClueByID(clueID)212 if clue == nil || p.FindRectangleForClue(clueID) != nil {213 return Rectangle{}, false214 }215216 if clue.Value == 1 {217 rect := Rectangle{218 ClueID: clueID,219 X: clue.X,220 Y: clue.Y,221 W: 1,222 H: 1,223 }224 if p.ValidRectangleForClue(rect, clueID) {225 return rect, true226 }227 return Rectangle{}, false228 }229230 return p.encasedRectangleForClue(clueID)231}232233func (p *Puzzle) unownedRegionFrom(x, y int) [][2]int {234 if x < 0 || x >= p.Width || y < 0 || y >= p.Height || p.CellOwner(x, y) != unownedRegionID {235 return nil236 }237238 visited := make(map[[2]int]struct{}, p.Width*p.Height)239 queue := [][2]int{{x, y}}240 visited[[2]int{x, y}] = struct{}{}241 cells := make([][2]int, 0, p.Width*p.Height)242243 for len(queue) > 0 {244 cell := queue[0]245 queue = queue[1:]246 cells = append(cells, cell)247248 cx, cy := cell[0], cell[1]249 neighbors := [][2]int{250 {cx - 1, cy},251 {cx + 1, cy},252 {cx, cy - 1},253 {cx, cy + 1},254 }255 for _, next := range neighbors {256 nx, ny := next[0], next[1]257 key := [2]int{nx, ny}258 if nx < 0 || nx >= p.Width || ny < 0 || ny >= p.Height {259 continue260 }261 if p.CellOwner(nx, ny) != unownedRegionID {262 continue263 }264 if _, ok := visited[key]; ok {265 continue266 }267 visited[key] = struct{}{}268 queue = append(queue, key)269 }270 }271272 return cells273}274275// SetRectangle places or replaces the rectangle for a clue.276func (p *Puzzle) SetRectangle(rect Rectangle) {277 for i, r := range p.Rectangles {278 if r.ClueID == rect.ClueID {279 p.Rectangles[i] = rect280 return281 }282 }283 p.Rectangles = append(p.Rectangles, rect)284}285286// RemoveRectangle removes the rectangle for the given clue ID.287func (p *Puzzle) RemoveRectangle(clueID int) {288 for i, r := range p.Rectangles {289 if r.ClueID == clueID {290 p.Rectangles = append(p.Rectangles[:i], p.Rectangles[i+1:]...)291 return292 }293 }294}295296// CluesInRect returns all clues contained within the given rectangle bounds.297func (p *Puzzle) CluesInRect(r Rectangle) []*Clue {298 var result []*Clue299 for i := range p.Clues {300 if r.Contains(p.Clues[i].X, p.Clues[i].Y) {301 result = append(result, &p.Clues[i])302 }303 }304 return result305}306307// autoPlaceForcedRectangles places uniquely forced rectangles until stable.308func (p *Puzzle) autoPlaceForcedRectangles() bool {309 changedAny := false310 for {311 changed := false312 for _, c := range p.Clues {313 rect, ok := p.forcedRectangleForClue(c.ID)314 if !ok {315 continue316 }317318 p.SetRectangle(rect)319 changed = true320 changedAny = true321 }322 if !changed {323 return changedAny324 }325 }326}327328// IsSolved reports whether the puzzle is complete:329// every cell is covered exactly once and each rectangle contains330// exactly one clue whose value equals the rectangle's area.331func (p *Puzzle) IsSolved() bool {332 if len(p.Rectangles) != len(p.Clues) {333 return false334 }335336 // Check each rectangle has exactly one clue with matching area.337 for _, r := range p.Rectangles {338 clue := p.FindClueByID(r.ClueID)339 if clue == nil {340 return false341 }342 if r.Area() != clue.Value {343 return false344 }345 if !r.Contains(clue.X, clue.Y) {346 return false347 }348 // Check no other clue is inside this rectangle.349 clueCount := 0350 for _, c := range p.Clues {351 if r.Contains(c.X, c.Y) {352 clueCount++353 }354 }355 if clueCount != 1 {356 return false357 }358 }359360 // Check all cells are covered exactly once (no gaps, no overlaps).361 covered := make([][]bool, p.Height)362 for y := range p.Height {363 covered[y] = make([]bool, p.Width)364 }365 for _, r := range p.Rectangles {366 for dy := range r.H {367 for dx := range r.W {368 cx, cy := r.X+dx, r.Y+dy369 if cx < 0 || cx >= p.Width || cy < 0 || cy >= p.Height {370 return false371 }372 if covered[cy][cx] {373 return false // overlap374 }375 covered[cy][cx] = true376 }377 }378 }379 for y := range p.Height {380 for x := range p.Width {381 if !covered[y][x] {382 return false383 }384 }385 }386387 return true388}